hdoj - 5202 Rikka with string (BestCoder Round #37 ($))

http://acm.hdu.edu.cn/showproblem.php?pid=5202

字符串处理的题，要细心。

给定一个只包含小写字母和问号的字符串，让我们还原出本来的字符串，把问号替换成任意字符，如果有多种可能输出字典序最小的，原字符串不能是回文串。

首先判断有没有非法字符，然后是否包含问号，如果没有包含则判断是否是回文串，满足则表示不能还原。

否则把所有问号都替换成‘a'，但是可能构成回文，然后继续替换，直到不是回文为止。

 #include <iostream>

 #include <cstdio>

 #include <cmath>

 #include <vector>

 #include <cstring>

 #include <string>

 #include <algorithm>

 #include <string>

 #include <set>

 #include <functional>

 #include <numeric>

 #include <sstream>

 #include <stack>

 #include <map>

 #include <queue>

 #define CL(arr, val)    memset(arr, val, sizeof(arr))

 #define ll long long

 #define inf 0x7f7f7f7f

 #define lc l,m,rt<<1

 #define rc m + 1,r,rt<<1|1

 #define pi acos(-1.0)

 #define L(x)    (x) << 1

 #define R(x)    (x) << 1 | 1

 #define MID(l, r)   (l + r) >> 1

 #define Min(x, y)   (x) < (y) ? (x) : (y)

 #define Max(x, y)   (x) < (y) ? (y) : (x)

 #define E(x)        (1 << (x))

 #define iabs(x)     (x) < 0 ? -(x) : (x)

 #define OUT(x)  printf("%I64d\n", x)

 #define lowbit(x)   (x)&(-x)

 #define Read()  freopen("a.txt", "r", stdin)

 #define Write() freopen("dout.txt", "w", stdout);

 #define N 100005

 using namespace std;

 bool palindrome(char *str)

 {

     int len=strlen(str);

     for(int i=;i<len/;i++)

     {

         if(str[i]!=str[len-i-]) return ;

     }

     return ;

 }

 char s[];

 int f[];

 int main()

 {

    //Read();

     int n;

     while(scanf("%d",&n)!=EOF)

     {

         getchar();

         gets(s);

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

         bool flag=;

         for(int i=;i<strlen(s);i++)

         {

             if(!((s[i]>='a'&&s[i]<='z')||s[i]=='?'))  {flag=;break;}

         }

         //printf("%d\n",flag);

         if(flag) {printf("QwQ\n");continue;}

         for(int i=;i<strlen(s);i++)

         {

             if(s[i]=='?') {flag=;break;}

         }

         if(!flag&&palindrome(s)) {printf("QwQ\n");continue;}

         int j=;

         memset(f,,sizeof(f));

         for(int i=;i<strlen(s);i++)

         {

             if(s[i]=='?')

             {

                 s[i]='a';

                 f[j++]=i;

             }

         }

         j--;

         flag=;

         if(palindrome(s))

         {

             s[f[j]]='b';   //从后往前替换  注意 a??aa

             while(palindrome(s))

             {

                 if(j==) {flag=;break;}

                 j--;

                 s[f[j]]='b';

                 s[f[j+]]='a';

             }

         }

         if(flag) printf("QwQ\n");

         else

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

     }

     return ;

 }

巴特西

hdoj - 5202 Rikka with string (BestCoder Round #37 ($))

最新文章

热门文章