51Nod - 1523 构造

题意：

一个字符串是非回文的，当且仅当，他只由前p个小写字母构成，而且他不包含长度大于等于2的回文子串。

给出长度为n的非回文串s。请找出字典序比s大的，而且字典序要最小的长度为n的非回文。

单组测试数据。第一行有两个整数n 和p (1≤n≤1000; 1≤p≤26)。第二行包含一个字符串s，它的长度是n。输入保证他是非回文的。Output
输出字典序比s大的且字典序要最小的长度为n的非回文，如果不存在输出NO。Input示例
样例输入13 3cba样例输入23 4cbaOutput示例
样例输出1NO样例输出2cbd
思路：
构造题。这道题关键是题目给出的串不会存在回文串，细想一下，就需要任意位置i满足str[i]!=str[i-1]&&str[i]!=str[i-2]，只有这样才能保证得到的串不存在回文串。要求字典序最小，那么首先要找到最靠末尾的一个位置i，字符可以增大，且满足str[i]!=str[i-1]&&str[i]!=str[i-2]，然后将这个位置的字符增大，剩下的，就是将i+1到n的位置的字符重写，要求是满足以上条件且字典序最小即可。
代码：
#include <cstdio>#include <cstring>using namespace std;const int MAXN = 1005;char str[MAXN];int main() {	int n, p;	scanf("%d%d%s", &n, &p, str + 1);	for (int i = n; i >= 1; i--) {		int x = str[i] - 'a';		if (x < p - 1) {			int y = -1;			for (int j = x + 1; j < p; j++) {				char c = 'a' + j;				if (i > 1 && c == str[i - 1]) continue;				if (i > 2 && c == str[i - 2]) continue; 				y = j;				break;			}			if (y == -1) continue;			str[i] = 'a' + y;			//PRintf("%d : %c/n", i, 'a' + y);			if (i == n) {				puts(str + 1);				return 0;			}			for (int j = i + 1; j <= n; j++) {				for (int k = 0; k < p; k++) {					char c = 'a' + k;					if (j > 1 && c == str[j - 1]) continue;					if (j > 2 && c == str[j - 2]) continue; 					str[j] = c;					break;				}			}			puts(str + 1);			return 0;		}	}	puts("NO");	return 0;}