17-10-05模拟赛

T1:考虑数据合法性与美丽串的定义，可知其要求每个字符与其前两个字符不同。

考虑从后往前贪心，找该字母后第一个可以替换的字母，若未找到则向前查找，对于替换字母后的字母贪心构造。

Code:

#include<cstdio>
#include<cstring>
#include<algorithm>
#define MN 100005
using namespace std;
inline int in(){
    int x=0;bool f=0; char c;
    for (;(c=getchar())<'0'||c>'9';f=c=='-');
    for (x=c-'0';(c=getchar())>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0');
    return f?-x:x;
}
char ch[MN],s[MN];
int n,p,pos,ps;
bool vis[30];
inline int dfs(int x){
    if (x<0) return -2;
    for (int i=0;i<p;++i) vis[i]=0;
    for (int i=1;i<=2;++i) if (x-i>=0) vis[s[x-i]-'a']=1;    
    for (int i=(s[x]-'a'+1);i<p;++i) if (!vis[i]) {pos=x;ch[x]=i+'a';break;}
    return pos==-1?dfs(x-1):pos;
}
int main()
{
    n=in();p=in();pos=-1;
    scanf("%s",s);ps=dfs(n-1);
    if (ps==-2) {printf("NO");return 0;}
    for (int i=0;i<ps;++i) ch[i]=s[i];
    for (int j=ps+1;j<n;++j){
        for (int i=0;i<p;++i) vis[i]=0;
        for (int i=1;i<=2;++i) if (j-i>=0) vis[ch[j-i]-'a']=1;
        for (int i=0;i<p;++i) if (!vis[i]) {ch[j]=i+'a';break;}
        if (!ch[j]) {printf("NO");return 0;}
    }printf("%s",ch);return 0;
}