196D The Next Good String

题目大意

给定n和一个字符串，求一个新字符串使得这个字符串不存在长度大于等于n的回文子串且在字典序大于原串的情况下最小。

分析

我们知道如果有一个长度为n+2的回文串，那它一定由一个长度为n的回文串构成，所以我们只寻找长度为n和n+1的回文串。我们枚举每个位置的字母使最终字符串满足条件即可，有一些处理详见代码（注意判断回文串的相减部分）。

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<algorithm>

#include<cctype>

#include<cmath>

#include<cstdlib>

#include<queue>

#include<ctime>

#include<vector>

#include<set>

#include<map>

#include<stack>

using namespace std;

#define uli unsigned long long

const uli HASH = ;

uli hsh[],h1[],h2[];

char s[],ans[];

int n,m;

inline bool add(int x){

      while(s[x]=='z'){

          s[x]='a';

          x--;

      }

      if(x<)return ;

      s[x]++;

      return ;

}

inline bool ok(int le,int ri){

      if(le<)return ;

      if((h1[ri]-h1[le-]*hsh[ri-le+])*hsh[le-]==h2[ri]-h2[le-])

        return ;

      return ;

}

inline bool dfs(int wh,int is){

      if(wh==n)return ;

      for(ans[wh]=(is?s[wh]:'a');ans[wh]<='z';ans[wh]++){

          h1[wh+]=h1[wh]*HASH+(ans[wh]-'a');

          h2[wh+]=h2[wh]+(ans[wh]-'a')*hsh[wh];

          if(ok(wh-m+,wh+)&&ok(wh-m+,wh+)&&

          dfs(wh+,is&(ans[wh]==s[wh])))

            return ;

      }

      return ;

}

int main(){

      int i,j,k;

      scanf("%d",&m);

      scanf("%s",s);

      n=strlen(s);

      hsh[]=;

      for(i=;i<=n+;i++)

        hsh[i]=hsh[i-]*HASH;

      if(m==||!add(n-)){

          puts("Impossible");

          return ;

      }

      if(dfs(,)){

          for(i=;i<n;i++)cout<<ans[i];

        puts("");

      }else puts("Impossible");

      return ;

}

巴特西

196D The Next Good String

最新文章

热门文章