[关闭]
@CQUPTacm 2017-03-19T15:05:07.000000Z 字数 10083 阅读 1150

萌新集中营第三期

题解

题目

A Hidden Password (ZOJ - 1729)

题意：

    给一个长度为L(5<=L<=100000)的字符串，一次循环左移操作即将当前字符串最左端(第0位)的字符移至字符串最右端(第L位)，然后将这L个字符全部往左移动一位，即第1位移向第0位、第2位移向第1位、...、第L位移向L-1位，此时从第0位到第L-1位就是新的字符串。问循环左移多少次后，得到的字符串字典序最小，如果有多个答案，输出最小的那个。
    T组数据。

题解：

    裸的字符串最小表示法。
    ps：把原字符串接在自己的后面，可以省很多事。
    时间复杂度o(n)，空间复杂度o(n)。

代码：

  1. #include<iostream>
  2. #include<cstdio>
  3. using namespace std;
  4. char s[200005];
  5. int main()
  6. {
  7.     int T;
  8.     int len,flag1,flag2,k;
  9.     scanf("%d",&T);
  10.     while(T--)
  11.     {
  12.         scanf("%d",&len);
  13.         scanf("%s",s);
  14.         for(int i=0;i<len;i++)
  15.             s[i+len]=s[i];
  16.         s[len+len]=0;
  17.         flag1=0;
  18.         flag2=1;
  19.         while(flag1<len && flag2<len)
  20.         {
  21.             k=0;
  22.             while(k<len && s[flag1+k]==s[flag2+k]) k++;
  23.             if(k==len)
  24.                 break;
  25.             else
  26.             {
  27.                 if(s[flag1+k]<s[flag2+k])
  28.                     flag2=flag2+k+1;
  29.                 else
  30.                     flag1=flag1+k+1;
  31.                 if(flag1==flag2)
  32.                     flag2++;
  33.             }
  34.         }
  35.         printf("%d\n",min(flag1,flag2));
  36.     }
  37.     return 0;
  38. }

B Shape Number (HDU - 4162)

题意：

    按照原题的图，'0'~'7'这八个字符按逆时针顺序分别表示八个方向，给出一条路线，表示每个点通向下一个点的绝对方向，保证最后一个点通向第一个点，点的个数N不超过300000。现在要求把绝对方向改为相对方向，相对方向为上一个点通往当前点的方向逆时针转向当前点通往下一个点的方向需要转过的方向个数，比如从方向2转向方向4相对方向就为2，从方向7转向方向2相对方向就为3。然后输出所有从某个点出发以相对方向表示的路线里，字典序最小的一个路线。
    多组数据。

题解：

    题目有点绕。
    先把绝对方向转化成相对方向。然后就是裸的最小表示法了。
    ps：注意第一个点的相对方向是最后一个点的绝对方向转向第一个点的绝对方向。如果转过的方向是负数要+8。
    时间复杂度o(N)，空间复杂度o(N)。

代码：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<cstdlib>
  5. #include<algorithm>
  6. using namespace std;
  7. char s[300005],ss[600005];
  8. int main()
  9. {
  10.     int len,flag1,flag2,k,ans;
  11.     while(~scanf("%s",s))
  12.     {
  13.         len=strlen(s);
  14.         for(int i=0;i<len;i++)
  15.         {
  16.             ss[i]=(s[i]-s[(len+i-1)%len]+8)%8+'0';
  17.             ss[i+len]=ss[i];
  18.         }
  19.         ss[len+len]=0;
  20.         flag1=0;
  21.         flag2=1;
  22.         while(flag1<len && flag2<len)
  23.         {
  24.             k=0;
  25.             while(k<len && ss[flag1+k]==ss[flag2+k]) k++;
  26.             if(k==len)
  27.                 break;
  28.             else
  29.             {
  30.                 if(ss[flag1+k]<ss[flag2+k])
  31.                     flag2=flag2+k+1;
  32.                 else
  33.                     flag1=flag1+k+1;
  34.                 if(flag1==flag2)
  35.                     flag2++;
  36.             }
  37.         }
  38.         ans=min(flag1,flag2);
  39.         for(int i=0;i<len;i++)
  40.             printf("%c",ss[ans+i]);
  41.         printf("\n");
  42.     }
  43.     return 0;
  44. }

C 剪花布条 (HDU - 2087)

题意：

    中文题。

题解：

    实际上求的是串1中有多少个不重叠的串2。将串2作为模式串，串1作为主串，用kmp找主串中有多少个模式串。因为要求不能重叠，所以找到一个后，已匹配的模式串长度要清零。
    设串1长度为n，串2长度为m，则时间复杂度o(n+m)，空间复杂度o(n+m)。

代码：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<cstdlib>
  5. #include<algorithm>
  6. using namespace std;
  7. char sa[1005],sb[1005];
  8. int nex[1005];
  9. void prekmp(char s[])
  10. {
  11.     nex[0]=nex[1]=0;
  12.     int l=strlen(s);
  13.     int j=0;
  14.     for(int i=1;i<l;i++)
  15.     {
  16.         while(j>0 && s[i]!=s[j]) j=nex[j];
  17.         if(s[i]==s[j])
  18.             j++;
  19.         nex[i+1]=j;
  20.     }
  21.     return ;
  22. }
  23. int kmp(char s1[],char s2[])
  24. {
  25.     int ans=0;
  26.     int l1=strlen(s1),l2=strlen(s2);
  27.     prekmp(s1);
  28.     int j=0;
  29.     for(int i=0;i<l2;i++)
  30.     {
  31.         while(j>0 && s1[j]!=s2[i]) j=nex[j];
  32.         if(s1[j]==s2[i]) j++;
  33.         if(j==l1)
  34.         {
  35.             j=0;
  36.             ans++;
  37.         }
  38.     }
  39.     return ans;
  40. }
  41. int main()
  42. {
  43.     while(1)
  44.     {
  45.         scanf("%s",sa);
  46.         if(sa[0]=='#')
  47.             break;
  48.         scanf("%s",sb);
  49.         printf("%d\n",kmp(sb,sa));
  50.     }
  51.     return 0;
  52. }

D Power Strings (POJ - 2406)

题目：

    定义字符串的乘法等于把这两个拼接起来，比如字符串s1="abc"、s2="def"，那么s1*s2="abc"+"def"="abcdef"，于是字符串的n次幂就等于n个字符串本身的拼接，比如s1="ab"，那么s1^4="abababab"。现在给一个只包含小写字母的字符串，长度N不超过1000000，问如果把它表示为某个字符串的幂，幂次最高是多少。
    多组数据。最后一行以一个单独的'.'作为结束标志，这个字符串不进行处理。

题解：

    找到最短的字符串，满足原串为这个最短字符串多次拼接而成，那么答案就是原串长度除以最短字符串的长度。如何找这个最短字符串呢？我们会发现，如果原串由n(n>1)个最短字符串拼接而成，那么将原串的前缀与后缀进行匹配，最长匹配长度就等于n-1个最短字符串的长度。于是对原串进行一次kmp的预处理，看原串长度与原串后缀和前缀的最长匹配长度的差是不是原串长度的因数，如果不是说明原串不能表示为某个字符串的幂，否则这个差就是最高幂次对应的字符串。
    时间复杂度o(N)，空间复杂度o(N)。

代码：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<cstdlib>
  5. #include<algorithm>
  6. using namespace std;
  7. char sa[1000005];
  8. int nex[1000005];
  9. int prekmp(char s[])
  10. {
  11.     nex[0]=nex[1]=0;
  12.     int l=strlen(s);
  13.     int j=0;
  14.     for(int i=1;i<l;i++)
  15.     {
  16.         while(j>0 && s[i]!=s[j]) j=nex[j];
  17.         if(s[i]==s[j])
  18.             j++;
  19.         nex[i+1]=j;
  20.     }
  21.     return nex[l];
  22. }
  23. int main()
  24. {
  25.     int l,ans;
  26.     while(~scanf("%s",sa))
  27.     {
  28.         if(sa[0]=='.')
  29.             break;
  30.         l=strlen(sa);
  31.         ans=l-prekmp(sa);
  32.         if(l%ans==0)
  33.             printf("%d\n",l/ans);
  34.         else
  35.             printf("1\n");
  36.     }
  37.     return 0;
  38. }

E Shortest Prefixes (POJ - 2001)

题目：

    给出多个只含有小写字母的单词，一个字符串能表示一个单词要满足以下两个条件之一：(1)这个字符串等于单词本身；(2)这个字符串是这个单词的前缀并且不是其他任何一个单词的前缀。单词个数n不超过1000并且不小于2，单个单词的长度l不超过20。

题解：

    根据这些单词建一棵字典树，每个节点储存经过的单词个数。查询的时候记录查询层数，当查询到某个节点经过的单词个数为1时说明已经查到可以表示这个单词的前缀了，就可以直接返回；或者已经查到这个单词本身了，也可以直接返回。根据查询层数输出这个单词对应长度的前缀即可。
    ps：单词个数不小于2保证了一开始不用特判根节点。用到了内存池的概念，记得节点个数的上限应该为n*l而不是n。
    时间复杂度o(n*l)，空间复杂度o（31*n*l）。

代码：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<cstdlib>
  5. #include<algorithm>
  6. using namespace std;
  7. struct Node
  8. {
  9.     int val;
  10.     int son[30];
  11. }tre[20005];
  12. int nums=1,snum=0;
  13. int cnt;
  14. char s[1005][25];
  15. void add(int now,char c[])
  16. {
  17.     tre[now].val++;
  18.     if(c[0])
  19.     {
  20.         if(!tre[now].son[c[0]-'a'])
  21.             tre[now].son[c[0]-'a']=nums++;
  22.         add(tre[now].son[c[0]-'a'],c+1);
  23.     }
  24.     return;
  25. }
  26. void ask(int now,char c[])
  27. {
  28.     cnt++;
  29.     if(tre[now].val!=1 && c[0])
  30.         ask(tre[now].son[c[0]-'a'],c+1);
  31.     return;
  32. }
  33. int main()
  34. {
  35.     while(~scanf("%s",s[snum]))
  36.     {
  37.         add(0,s[snum]);
  38.         snum++;
  39.     }
  40.     for(int i=0;i<snum;i++)
  41.     {
  42.         printf("%s ",s[i]);
  43.         cnt=-1;
  44.         ask(0,s[i]);
  45.         for(int j=0;j<cnt;j++)
  46.             printf("%c",s[i][j]);
  47.         printf("\n");
  48.     }
  49.     return 0;
  50. }

F Phone List (POJ - 3630)

题目：

    给出n(1<=n<=10000)个电话号码，每个电话号码由不超过10个数字组成，问是否有某个电话号码是另一个电话号码的前缀。
    t(1<=t<=40)组数据。

题解：

    把电话号码看成字符串，实际上就是看是否有一个字符串是另一个字符串的前缀。建一棵字典树，每个节点储存经过的字符串个数。有两种情况可以断定有一个字符串是另一个字符串的前缀：(1)作为前缀的那个字符串先输入了，那么当前的字符串在添加到字典树上的过程中，肯定会经过前缀的结尾字符；(2)如果作为前缀的那个字符串后输入，那么当前字符串的结尾字符所在的那个节点，一定被前面的字符串经过了。我们把所有结尾字符所在的节点打上标记，判断这两种情况存不存在即可。
    ps：因为是多组数据，所以要做好初始化。我的代码是在字典树上新加入节点的时候才初始化这个节点。
    时间复杂度o(t*10*n)，空间复杂度o(10*n)。

代码：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<cstdlib>
  5. #include<algorithm>
  6. using namespace std;
  7. struct Node
  8. {
  9.     int val;
  10.     int son[15];
  11. }tre[100005];
  12. int nums;
  13. bool flag;
  14. char s[15];
  15. int newnode()
  16. {
  17.     tre[nums].val=0;
  18.     memset(tre[nums].son,0,sizeof(tre[nums].son));
  19.     return nums++;
  20. }
  21. void add(int now,char c[])
  22. {
  23.     if(tre[now].val==-1)
  24.     {
  25.         flag=1;
  26.         return;
  27.     }
  28.     tre[now].val++;
  29.     if(c[0])
  30.     {
  31.         if(!tre[now].son[c[0]-'0'])
  32.             tre[now].son[c[0]-'0']=newnode();
  33.         add(tre[now].son[c[0]-'0'],c+1);
  34.     }
  35.     else
  36.     {
  37.         if(tre[now].val==1)
  38.             tre[now].val=-1;
  39.         else
  40.         {
  41.             flag=1;
  42.             return;
  43.         }
  44.     }
  45.     return;
  46. }
  47. int main()
  48. {
  49.     int t,n;
  50.     scanf("%d",&t);
  51.     while(t--)
  52.     {
  53.         nums=0;
  54.         newnode();
  55.         flag=0;
  56.         scanf("%d",&n);
  57.         while(n--)
  58.         {
  59.             scanf("%s",s);
  60.             add(0,s);
  61.         }
  62.         if(flag)
  63.             printf("NO\n");
  64.         else
  65.             printf("YES\n");
  66.     }
  67.     return 0;
  68. }

G Best Reward (HDU - 3613)

题意：

    用26个字母表示26种宝石，给出每种宝石的价值v(-100<=v<=100)，将一个由N(500000)个宝石组成的项链分成都不为空的两部分，如果某部分表示成字符串不是回文串，则这部分的价值为0，否则这部分的价值为他所包含的宝石的总价值。问这两部分价值的和的最大值。
    T(1<=T<=10)组数据。

题解：

    分别求出原串的每个前缀和后缀是不是回文串，并且预处理每一段的宝石的价值和，然后枚举分隔点就可以知道所有方案的价值了，从中取最大的即可。有很多种做法，这里提供的是exkmp的做法。
    exkmp是求串s1的每一个后缀的串s2的最长相同前缀，如果我们把原串作为s2，原串的相反串作为s1，令l表示原串的长度，那么我们会发现，如果原串的前k个字符是一个回文串，则s2的最后k个字母和s1的最长相同前缀就为k，通过求出s1每个后缀和s2的最长相同前缀，就可以判断对应的s2前缀是不是回文串。同理，也可以类似的判断原串的任意后缀是不是回文串。
    ps：因为宝石的价值可能是负的，所以最后的答案也可能是负的，注意预处理。
    时间复杂度o(T*l)，空间复杂度o(l)。

代码：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<algorithm>
  5. using namespace std;
  6. char sa[500005],sb[500005];
  7. int ex1[500005],ex2[500005],nex[500005];
  8. int val[30],valsum[500005];
  9. void getnex(char s[])
  10. {
  11.     int i=0,j,po,l=strlen(s);
  12.     nex[0]=l;
  13.     while(i+1<l && s[i]==s[i+1]) i++;
  14.     i++;
  15.     nex[1]=i;
  16.     po=1;
  17.     for(i=2;i<l;i++)
  18.     {
  19.         if(i+nex[i-po]<po+nex[po])
  20.             nex[i]=nex[i-po];
  21.         else
  22.         {
  23.             j=nex[po]+po-i;
  24.             if(j<0)
  25.                 j=0;
  26.             while(i+j<l && s[j]==s[j+i]) j++;
  27.             nex[i]=j;
  28.             po=i;
  29.         }
  30.     }
  31.     return ;
  32. }
  33. void exkmp(char s1[],char s2[],int ex[])
  34. {
  35.     getnex(s2);
  36.     int i=0,j,po,l1=strlen(s1),l2=strlen(s2);
  37.     while(i<l1 && i<l2 && s1[i]==s2[i]) i++;
  38.     ex[0]=i;
  39.     po=0;
  40.     for(i=1;i<l1;i++)
  41.     {
  42.         if(i+nex[i-po]<ex[po]+po)
  43.             ex[i]=nex[i-po];
  44.         else
  45.         {
  46.             j=ex[po]+po-i;
  47.             if(j<0) j=0;
  48.             while(j<l2 && i+j<l1 && s1[j+i]==s2[j]) j++;
  49.             ex[i]=j;
  50.             po=i;
  51.         }
  52.     }
  53.     return ;
  54. }
  55. int main()
  56. {
  57.     int t,ans,ans1,ans2,l;
  58.     scanf("%d",&t);
  59.     while(t--)
  60.     {
  61.         ans=-66666666;
  62.         for(int i=0;i<26;i++)
  63.             scanf("%d",val+i);
  64.         scanf("%s",sa);
  65.         valsum[0]=val[sa[0]-'a'];
  66.         l=strlen(sa);
  67.         sb[l]=0;
  68.         sb[l-1]=sa[0];
  69.         for(int i=1;i<l;i++)
  70.         {
  71.             valsum[i]=valsum[i-1]+val[sa[i]-'a'];
  72.             sb[l-1-i]=sa[i];
  73.         }
  74.         exkmp(sb,sa,ex1);
  75.         exkmp(sa,sb,ex2);
  76.         for(int i=0;i<l-1;i++)
  77.         {
  78.             if(ex1[l-i-1]==i+1)
  79.                 ans1=valsum[i];
  80.             else
  81.                 ans1=0;
  82.             if(ex2[i+1]==l-i-1)
  83.                 ans2=valsum[l-1]-valsum[i];
  84.             else
  85.                 ans2=0;
  86.             ans=max(ans,ans1+ans2);
  87.         }
  88.         printf("%d\n",ans);
  89.     }
  90.     return 0;
  91. }

H Clairewd’s message (HDU - 4300)

题意：

    给一个从小写字母到小写字母的密文密码的对照表，第1个字母为明文'a'的密文，第2个字母为明文'b'的密文，...以此类推。然后给出一个字符串，长度L不超过100000，字符串前一部分是完整的密文，后一部分(可能不存在)是不一定完整的明文。求密文+明文，如果有多种可能性，输出总长度最小的那种。
    T(T<=100)组数据。

题解：

    假设明文的长度为n，所给的字符串s1长度为m，则s1的前n个字符是完整的密文，后m-n个字符是明文的前m-n个字符。于是把s1全部当做密文按照对照表解密为s2，则s2的前m-n个字符和s1的后m-n个字符是一样的。题目要求长度最小，实际上就是求最小的n。于是我们用exkmp去求s1的每一个后缀和s2的最长相同前缀，找到第一个s1后缀等于最长相同前缀的地方，就能找到符合条件的最小的n。
    ps：注意要保证m-n<=n。
    时间复杂度o(T*L)，空间复杂度o(L)。

代码：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<algorithm>
  5. using namespace std;
  6. char sa[100005],sb[100005],sval[26],skey[30];
  7. int ext[100005],nex[100005];
  8. void getnex(char s[])
  9. {
  10.     int i=0,j,po,l=strlen(s);
  11.     nex[0]=l;
  12.     while(i+1<l && s[i]==s[i+1]) i++;
  13.     i++;
  14.     nex[1]=i;
  15.     po=1;
  16.     for(i=2;i<l;i++)
  17.     {
  18.         if(i+nex[i-po]<po+nex[po])
  19.             nex[i]=nex[i-po];
  20.         else
  21.         {
  22.             j=nex[po]+po-i;
  23.             if(j<0)
  24.                 j=0;
  25.             while(i+j<l && s[j]==s[j+i]) j++;
  26.             nex[i]=j;
  27.             po=i;
  28.         }
  29.     }
  30.     return ;
  31. }
  32. void exkmp(char s1[],char s2[],int ex[])
  33. {
  34.     getnex(s2);
  35.     int i=0,j,po,l1=strlen(s1),l2=strlen(s2);
  36.     while(i<l1 && i<l2 && s1[i]==s2[i]) i++;
  37.     ex[0]=i;
  38.     po=0;
  39.     for(i=1;i<l1;i++)
  40.     {
  41.         if(i+nex[i-po]<ex[po]+po)
  42.             ex[i]=nex[i-po];
  43.         else
  44.         {
  45.             j=ex[po]+po-i;
  46.             if(j<0) j=0;
  47.             while(j<l2 && i+j<l1 && s1[j+i]==s2[j]) j++;
  48.             ex[i]=j;
  49.             po=i;
  50.         }
  51.     }
  52.     return ;
  53. }
  54. int main()
  55. {
  56.     int t,temp,ans,l;
  57.     scanf("%d",&t);
  58.     while(t--)
  59.     {
  60.         scanf("%s",sval);
  61.         for(int i=0;i<26;i++)
  62.             skey[sval[i]-'a']='a'+i;
  63.         scanf("%s",sa);
  64.         l=strlen(sa);
  65.         ans=l;
  66.         sb[l]=0;
  67.         for(int i=0;i<l;i++)
  68.             sb[i]=skey[sa[i]-'a'];
  69.         exkmp(sa,sb,ext);
  70.         for(int i=0;i<l;i++)
  71.         {
  72.             if(ext[i]+i==l && i>=ext[i])
  73.             {
  74.                 ans=i;
  75.                 break;
  76.             }
  77.         }
  78.         for(int i=0;i<ans;i++)
  79.             printf("%c",sa[i]);
  80.         for(int i=0;i<ans;i++)
  81.             printf("%c",sb[i]);
  82.         printf("\n");
  83.     }
  84.     return 0;
  85. }

I 最长回文 (HDU - 3068)

题意：

    中文题。

题解：

    最长回文其实有很多种做法，比如用exkmp。这里提供一个Manacher的解法。
    ps:用scanf("%s")进行输入可以无视空行之类的问题。预处理了字符串，可以不用判断回文长度双数或者单数的情况了。
    时间复杂度o(120*len)，空间复杂度o(len)。

代码：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<algorithm>
  5. using namespace std;
  6. char sa[110005],ss[220005];
  7. int pla[220005];
  8. int manac(char s[])
  9. {
  10.     int l=strlen(s),ans=0;
  11.     for(int i=0;i<l;i++)
  12.     {
  13.         ss[i*2]='#';
  14.         ss[i*2+1]=s[i];
  15.     }
  16.     ss[l*2]='#';
  17.     l=l*2+1;
  18.     int mr=0,p=0;
  19.     for(int i=0;i<l;i++)
  20.     {
  21.         if(mr>i)
  22.             pla[i]=min(mr-i,pla[2*p-i]);
  23.         else
  24.             pla[i]=0;
  25.         while(i-pla[i]-1>=0 && i+pla[i]+1<l && ss[i-pla[i]-1]==ss[i+pla[i]+1]) pla[i]++;
  26.         if(i+pla[i]>mr)
  27.         {
  28.             mr=i+pla[i];
  29.             p=i;
  30.         }
  31.         ans=max(ans,pla[i]);
  32.     }
  33.     return ans;
  34. }
  35. int main()
  36. {
  37.     while(~scanf("%s",sa))
  38.         printf("%d\n",manac(sa));
  39.     return 0;
  40. }

J Ball Blasting Game (UVA - 12378)

题意：

    给一个长度L不超过100000的字符串，选择其中一个字母，则相连接的所有相同的字母都会消除，然后左右两边的字符会接在一起，如果接在一起的字符是相同的，那么相连接的所有相同的字母都会消除，重复这个过程直到所有字母都消除或者接在一起的字符不相同。问最大消除次数是多少。
    T(T<=100)组数据。

题解：

    实际上就是看某种字母左右两端有多少相同的字母段。把原串进行处理，相同的一段字母视为一个字母，那么从某个字母开始消除的次数就等于(以他为中心的回文串的长度+1)/2。
    时间复杂度o(T*L)，空间复杂度o(L)。

代码：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<algorithm>
  5. using namespace std;
  6. char sa[100005],ss[100005];
  7. int pla[100005];
  8. int manac(char s[])
  9. {
  10.     int l=strlen(s),ans=0;
  11.     int mr=0,p=0;
  12.     for(int i=0;i<l;i++)
  13.     {
  14.         if(mr>i)
  15.             pla[i]=min(mr-i,pla[2*p-i]);
  16.         else
  17.             pla[i]=0;
  18.         while(i-pla[i]-1>=0 && i+pla[i]+1<l && ss[i-pla[i]-1]==ss[i+pla[i]+1]) pla[i]++;
  19.         if(i+pla[i]>mr)
  20.         {
  21.             mr=i+pla[i];
  22.             p=i;
  23.         }
  24.         ans=max(ans,pla[i]);
  25.     }
  26.     return ans;
  27. }
  28. int main()
  29. {
  30.     int t,l;
  31.     char c;
  32.     scanf("%d",&t);
  33.     while(t--)
  34.     {
  35.         scanf("%s",sa);
  36.         c=0;
  37.         l=0;
  38.         for(int i=0;sa[i];i++)
  39.         {
  40.             if(sa[i]!=c)
  41.             {
  42.                 ss[l++]=sa[i];
  43.                 c=sa[i];
  44.             }
  45.         }
  46.         ss[l]=0;
  47.         printf("%d\n",manac(ss)+1);
  48.     }
  49.     return 0;
  50. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注