Codeforces 464A No to Palindromes!(構造)

Codeforces 464A No to Palindromes!(構造)

題目鏈接：Codeforces 464A No to Palindromes!

題目大意：給定n和m，以及一個字符串s，s不存在長度大於2的回文子串，現在要求輸出一個字典比s大的字符串，並

且說同樣不存在長度大於2的回文子串。

解題思路：直接去構造即可，從最後一位開始，每次只要考慮該字符是否和前兩個字符相同即可。

#include 
#include 
#include 

using namespace std;

const int maxn = 1005;
int N, P;
char s[maxn];

bool check (int v) {
    if (v >= 1 && s[v] == s[v-1])
        return false;
    if (v >= 2 && s[v] == s[v-2])
        return false;
    return true;
}

bool solve (int v) {

    while(true) {
        if (v >= N)
            return true;

        if (v < 0)
            return false;

        if (s[v] - 'a' == P - 1) {
            s[v] = 'a' - 1;
            v--;
        } else {

            int k = (s[v] - 'a' + 1) % P;
            s[v] = 'a' + k;

            if (check(v))
                v++;
        }
    }
    return false;
}

int main () {
    scanf("%d%d%s", &N, &P, s);
    if (!solve(N-1))
        printf("NO\n");
    else
        printf("%s\n", s);
    return 0;
}