【Codeforces 464A】No to Palindromes!

【链接】 我是链接,点我呀:)
【题意】

题意

【题解】

因为原序列没有任何长度超过2的回文串。
所以,我们在改变的时候,只要时刻保证改变位置s[i]和s[i-1]以及s[i-2]都不相同就好。
因为只改变一个位置的话是不会产生长度超过3的回文串的
我们按照从后到前,从小到大的顺序,尝试增加第i位的字符就好。
只要找到一个位置idx可以增加一下,那么后面我们只要按照之前的规则,
让idx+1~len依次让每一位从‘a‘开始到‘a‘+p-1进行枚举构造出来一个最小字典序的符合要求的字符串就好.
(如果idx+1~len不能构造出来,那么会发现a[idx]不论改成什么都还是一样的,因为我们在考虑的时候,肯定会满足a[idx-1]和a[idx]不同,而后面也是如此
所以a[idx]是什么对于后面来说已经不重要了,没有影响,所以不用担心会漏解)
(main函数记得加上Public。。。)

【代码】

import java.util.*;

public class Main{
    
    static int n,p;
    static int a[] = new int[1010];
    
    static boolean dfs(int dep) {
        if (dep==0) return false;
        for (int i = a[dep]+1;i <= p;i++) {
            if (dep-1>=1 && a[dep-1]==i) continue;
            if (dep-2>=1 && a[dep-2]==i) continue;
            a[dep] = i;
            return true;
        }
        if (!dfs(dep-1)) return false;
        a[dep] = 1;
        for (int i = a[dep];i<=p;i++) {
            if (dep-1>=1 && a[dep-1]==i) continue;
            if (dep-2>=1 && a[dep-2]==i) continue;
            a[dep] = i;
            return true;
        }
        return false;
    }
    
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s;
        n = in.nextInt();p = in.nextInt();
        s = in.next();
        for (int i = 1;i <= n;i++) {
            a[i] = (int)(s.charAt(i-1)-'a'+1);
        }
        if (dfs(n)) 
            for (int i = 1;i <= n;i++) 
                System.out.print((char)(a[i]+'a'-1));
        else 
            System.out.println("NO");
    }
}