http://codeforces.com/contest/465/problem/C
Codeforces Round #265 (Div. 2) C
Codeforces Round #265 (Div. 1) A
http://codeforces.com/contest/464/problem/A
|
C. No to Palindromes!
time limit per test
1 second memory limit per test
256 megabytes input
standard input output
standard output Paul hates palindromes. He assumes that string s is tolerable if each its character is one of the first p letters of the English alphabet and s doesn't contain any palindrome contiguous substring of length 2 or more. Paul has found a tolerable string s of length n. Help him find the lexicographically next tolerable string of the same length or else state that such string does not exist. Input
The first line contains two space-separated integers: n and p (1 ≤ n ≤ 1000; 1 ≤ p ≤ 26). The second line contains string s, consisting of n small English letters. It is guaranteed that the string is tolerable (according to the above definition). Output
If the lexicographically next tolerable string of the same length exists, print it. Otherwise, print "NO" (without the quotes). Sample test(s)
Input
3 3 Output
NO Input
3 4 Output
cbd Input
4 4 Output
abda Note
String s is lexicographically larger (or simply larger) than string t with the same length, if there is number i, such that s1 = t1, ..., si = ti, si + 1 > ti + 1. The lexicographically next tolerable string is the lexicographically minimum tolerable string which is larger than the given one. A palindrome is a string that reads the same forward or reversed. |
题意：
给出一个由n个字符，由前p个小写英文字母组成的字符串，这个字符串长度不小于2的子串都不回文。求字典序大于这个的 字典序最小的符合这个条件的字符串，若没有则输出NO。
题解：模拟。
把字符串当成p位数字，+1然后进位，判断是否符合规则。
规则是不回文，考虑回文长度为2，则相邻的数字不能相同；考虑回文长度为3，则隔一个的数字不能相同；考虑更高长度的情况，发现如果没有长度为2或者3的，就没有更高长度的情况了。所以我们只用判相邻的和隔一个的等不等。
然后只这样的话final system test会跪，有数据会TLE。因为可能会加一加很多次都是回文的，我们要让这种情况一次直接加很多，不慢慢加一加一。我们发现加一进位只会改变低的若干位，回文判断只用判断这若干位，找到出现回文的最高位，如果这位不改变则再加一也会有回文，所以我们要让这位改变，最简单的就是把比它低的位全部置为最高的数字，下次加一就可以怒变了。这样就能A了。
代码：
//#pragma comment(linker, "/STACK:102400000,102400000")
#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<stack>
#include<queue>
using namespace std;
#define ll long long
#define usll unsigned ll
#define mz(array) memset(array, 0, sizeof(array))
#define minf(array) memset(array, 0x3f, sizeof(array))
#define REP(i,n) for(i=0;i<(n);i++)
#define FOR(i,x,n) for(i=(x);i<=(n);i++)
#define RD(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d%d",&x,&y)
#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define WN(x) printf("%d\n",x);
#define RE freopen("D.in","r",stdin)
#define WE freopen("1biao.out","w",stdout)
#define mp make_pair
#define pb push_back
const double eps=1e-;
const double pi=acos(-1.0); char s[];
int n,p; int farm(){
int i,j;
int prei=n-;
while(){
j=n-;
s[j]++;///最后一位加一
while(j> && s[j]>='a'+p){///进位
s[j]-=p;
s[j-]++;
j--;
}
//printf("%d %s\n",j,s);
if(j== && s[j]>='a'+p)return ;///最高位都超上限了，爆炸
bool cant=;
int st=min(j,prei);///只观察改变了的位是否符合要求
for(i=st;i<n;i++){
if(i>= && s[i]==s[i-]){cant=;break;}
if(i>= && s[i]==s[i-]){cant=;break;}
}
if(cant){
prei=i;
for(j=i+;j<n;j++) ///第i位不符合要求，我们需要让第i位改变，
///最简单的就是把之后的为都置为最高数字，让它下次加会进位
s[j]='a'+p-;
continue;
}
return ;
}
} int main(){
scanf("%d%d ",&n,&p);
gets(s);
int ans=farm();
if(ans==)puts("NO");
else{
puts(s); }
return ;
}