「CF464A」No to Palindromes!

2014年9月8日5,2933

Paul hates palindromes. He assumes that string s is tolerable if each its character is one of the first p letters of the English alphabet and sdoesn’t contain any palindrome contiguous substring of length 2 or more.

Paul has found a tolerable string s of length n. Help him find the lexicographically next tolerable string of the same length or else state that such string does not exist.

Input

The first line contains two space-separated integers: n and p (1 ≤ n ≤ 1000; 1 ≤ p ≤ 26). The second line contains string s, consisting ofn small English letters. It is guaranteed that the string is tolerable (according to the above definition).

Output

If the lexicographically next tolerable string of the same length exists, print it. Otherwise, print “NO” (without the quotes).

Sample test(s)

input

3 3
cba

3 3

cba

output

NO

input

3 4
cba

3 4

cba

output

cbd

cbd

input

4 4
abcd

4 4

abcd

output

abda

abda

Note

String s is lexicographically larger (or simply larger) than string t with the same length, if there is number i, such that s₁ = t₁, …, s_i = t_i, s_i + 1 > t_i + 1.

The lexicographically next tolerable string is the lexicographically minimum tolerable string which is larger than the given one.

A palindrome is a string that reads the same forward or reversed.

题解

题意是就是找一个字典序大于s且最小的串，每个字母在p的范围内，串的任意部分都不能是回文

按照KuribohG的做法。。。（由于我很逗写了不知道什么傻逼玩意）

串的任意部分都不能是回文=串中任意连续3个字符互不相同

而要求字典序最小，应该保持前面的尽量多字符是不改动的

那么只要从后往前枚举每一位，如果某一位a[x]改为k（k>a[x]）后与a[x-1],a[x-2]都不同，那么a[1]~a[x-1]就可以确定了

再从x+1开始贪心

举个例子

5 4

abdcb

发现将第二位改成c后与前面的俩位不同，即可以确定ac为开头，可以证明一定能得到解，剩下的几位贪心即可

acbac为最优解

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<vector>
#include<queue>
#define pa pair<int,int>
#define inf 1000000000
#define ll long long 
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
char a[100010],tmp;
int n,k,p;
char add(int x)
{
    for(char i=a[x]+1;i<k+'a';i++)
        if(i!=a[x-1]&&i!=a[x-2])return i;
    return 0;
}
int main()
{
    n=read();k=read();
    scanf("%s",a);
    for(p=n-1;p>=0;p--)
    {
        tmp=add(p);
        if(tmp){a[p]=tmp;break;}
    }
    if(p==-1){puts("NO");return 0;}
    for(int i=p+1;i<n;i++)
    {
        a[i]='a'-1;
        a[i]=add(i);
    }
    printf("%s\n",a);
    return 0;
}

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

#include<map>

#include<set>

#include<vector>

#include<queue>

#define pa pair<int,int>

#define inf 1000000000

#define ll long long

using namespace std;

inline int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

char a[100010],tmp;

int n,k,p;

char add(int x)

{

for(char i=a[x]+1;i<k+'a';i++)

if(i!=a[x-1]&&i!=a[x-2])return i;

return 0;

}

int main()

{

n=read();k=read();

scanf("%s",a);

for(p=n-1;p>=0;p--)

{

tmp=add(p);

if(tmp){a[p]=tmp;break;}

}

if(p==-1){puts("NO");return 0;}

for(int i=p+1;i<n;i++)

{

a[i]='a'-1;

a[i]=add(i);

}

printf("%s\n",a);

return 0;

}

« 「BZOJ1034」[ZJOI2008] 泡泡堂BNB 「BZOJ3709」[PA2014] Bohater »

欧阳茹芯

懂了，谢谢。。。。。。。。。。。。。。。。。

欧阳茹芯

没懂

hzwer

一定是我逗了。。。我重新写了。。。

hzwer.com _ Home | http://hzwer.com

「CF464A」No to Palindromes!

分类目录

热门文章

Myfriends

近期评论