首页 > 代码库 > Codeforces 464A No to Palindromes!(构造)

Codeforces 464A No to Palindromes!(构造)

题目链接:Codeforces 464A No to Palindromes!

题目大意:给定n和m,以及一个字符串s,s不存在长度大于2的回文子串,现在要求输出一个字典比s大的字符串,并

且说同样不存在长度大于2的回文子串。

解题思路:直接去构造即可,从最后一位开始,每次只要考虑该字符是否和前两个字符相同即可。

#include <cstdio>
#include <cstring>
#include <algorithm>

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;
}

Codeforces 464A No to Palindromes!(构造)