【codeforces 709C】Letters Cyclic Shift

时间:2022-05-21 22:08:45

【题目链接】:http://codeforces.com/contest/709/problem/C

【题意】



让你改变一个字符串的子集(连续的一段);

->这一段的每个字符的字母都变成之前的一个;

即b->a或是a>z;

然后使得剩下的字符串的字典序最小;

【题解】



优先更改前面的字符;

所以遇到第一个不是a的字符->改!

从那个字符开始只要不是a就一直改就好;

hack点;

有说

exactly once->也就是说



aaa

不能全都不改;

把最后那个a改成z(损失最小)

永远不要低估CF的C题。。



【完整代码】

#include <bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define ps push_back
#define fi first
#define se second
#define rei(x) scanf("%d",&x)
#define rel(x) scanf("%lld",&x)
#define ref(x) scanf("%lf",&x) typedef pair<int, int> pii;
typedef pair<LL, LL> pll; const int dx[9] = { 0,1,-1,0,0,-1,-1,1,1 };
const int dy[9] = { 0,0,0,-1,1,-1,1,-1,1 };
const double pi = acos(-1.0);
const int N = 1e5+1000; char s[N];
int len; int main()
{
//freopen("F:\\rush.txt", "r", stdin);
bool fi = false;
scanf("%s", s + 1);
len = strlen(s + 1);
rep1(i, 1, len){
if (s[i] == 'a') continue;
int j = i;
while (j + 1 <= len && s[j + 1] != 'a') j++;
rep1(k, i, j) s[k]--;
fi = true;
break;
}
if (!fi) s[len]='z';
printf("%s", s + 1);
//printf("\n%.2lf sec \n", (double)clock() / CLOCKS_PER_SEC);
return 0;
}