P2799 国王的魔镜

admin

https://www.luogu.org/problemnew/show/P2799
题目描述
国王有一个魔镜，可以把任何接触镜面的东西变成原来的两倍——只是，因为是镜子嘛，增加的那部分是反的。比如一条项链，我们用AB来表示，不同的字母表示不同颜色的珍珠。如果把B端接触镜面的话，魔镜会把这条项链变为ABBA。如果再用一端接触的话，则会变成ABBAABBA（假定国王只用项链的某一端接触魔镜）。给定最终的项链，请编写程序输出国王没使用魔镜之前，最初的项链可能的最小长度。

输入输出格式
输入格式：
只有一个字符串，由大写英文字母组成（字母数<=100000），表示最终的项链。

输出格式：
只有一个整数，表示国王没使用魔镜前，最初的项链可能的最小长度。

输入输出样例
输入样例#1：
ABBAABBA
输出样例#1：
2

admin

一个串要是长度为偶数并且回文那么他可以由字串得到，这个子串递归判断，直到不是回文或者长度为奇数。
bool check(string s)  判断是否长度为奇数，或者不是回文
string get(string s)
{
  if (!check(s)) return s;
  else return (s的一半)
}
下面就不需要我再写下去了吧

张笑宇

1. #include<iostream>
   
2. using namespace std;
   
3. string s;
   
4. int l,i;
   
5. bool b=true;
   
6. int main()
   
7. {
   
8.     cin>>s;
   
9.     l=s.size();
   
10.     while (b)
    
11.     {
    
12.         if (l%2==1) b=false;///如果长度为奇数，就舍去
    
13.         else
    
14.         {
    
15.             for (i=1;i<=l/2;i++)
    
16.             {///从头至尾搜索
    
17.                 if (s[i-1]!=s[l-i])  b=false;
    
18.             }///发现错的就舍去
    
19.             if (b) l=l/2;///如果可以再对折
    
20.         }
    
21.     }
    
22.     cout<<l;
    
23.     return 0;
    
24. }

复制代码

黄煦喆

1. #include<iostream>
   
2. #include<algorithm>
   
3. using namespace std;
   
4. string s;
   
5. int r,ans;
   
6. void ms(int r)
   
7. {
   
8.     while(r%2==0)
   
9.     {
   
10.         //cout<<r<<endl;
    
11.         for(int i=0; i<r/2; i++)
    
12.             if(s[i]!=s[r-i-1])
    
13.         {
    
14.             ans=r;
    
15.             return;
    
16.         }
    
17.         r/=2;
    
18.         ans=r;
    
19.     }
    
20. }
    
21. int main()
    
22. {
    
23.     cin>>s;
    
24.     ans=r=s.size();
    
25.     ms(r);
    
26.     cout<<ans;
    
27.     return 0;
    
28. }
    

复制代码

黄诗绮

1. #include<iostream>  
   
2. #include<cstring>  
   
3. using namespace std;  
   
4. int main()  
   
5. {  
   
6.     char a[100002];  
   
7.     int l,i;   
   
8.     cin>>a;  
   
9.     l=strlen(a);     
   
10.     while(1)   
    
11.     {  
    
12.         if(l%2==1){   
    
13.             cout<<l<<endl;  
    
14.             return 0;  
    
15.         }  
    
16.         for(i=0;i<l;i++)   
    
17.         {  
    
18.             if(a[i]!=a[l-i-1]){  
    
19.             cout<<l<<endl;  
    
20.             return 0;  
    
21.             }  
    
22.         }  
    
23.         l/=2;
    
24.     }  
    
25. }  

复制代码

王令欧

1. #include <stdio.h>//王令欧
   
2. #include <string.h>
   
3. int main()
   
4. {
   
5.         int len,i,j,ls;
   
6.         char a[100001];
   
7.         scanf("%s",a);
   
8.         len=strlen(a);
   
9.         while(1)
   
10.         {
    
11.                 for(i=0;i<=len/2-1;i++)
    
12.                 {
    
13.                         if(len-i-2==i)
    
14.                         {
    
15.                                 len=len/2;
    
16.                                 for(j=i+1;j<=len+i;j++)
    
17.                                 {
    
18.                                         a[j]='0';
    
19.                                 }
    
20.                         }
    
21.                 }
    
22.                 for(i=0;i<=len/2-1;i++)
    
23.                         if(a[i]!=a[len-i-1])
    
24.                                 break;
    
25.                 if(a[i]!=a[len-i-1])
    
26.                         break;
    
27.         }
    
28.         for(i=0;i<=len-1;i++)
    
29.                 printf("%c",a[i]);
    
30.         return 0;
    
31. }

复制代码

王令欧

1. #include <stdio.h>//王令欧
   
2. #include <string.h>
   
3. int main()
   
4. {
   
5.         int len,i,j,ls;
   
6.         char a[100001];
   
7.         scanf("%s",a);//输入
   
8.         len=strlen(a);
   
9.         while(1)
   
10.         {
    
11.                 for(i=0;i<=len/2-1;i++)
    
12.                 {
    
13.                         if(len-i-2==i)
    
14.                         {
    
15.                                 len=len/2;
    
16.                                 for(j=i+1;j<=len+i;j++)
    
17.                                 {
    
18.                                         a[j]='0';
    
19.                                 }//留下一半
    
20.                         }
    
21.                 }
    
22.                 for(i=0;i<=len/2-1;i++)
    
23.                         if(a[i]!=a[len-i-1])
    
24.                                 break;
    
25.                 if(a[i]!=a[len-i-1])//如果不回文了，就跳出循环
    
26.                         break;
    
27.         }
    
28.         printf("%d",len);
    
29.         return 0;
    
30. }

复制代码

admin

1. #include  <iostream>
   
2. using namespace std;
   
3. int work(string s)
   
4. {
   
5.    int l=s.size();
   
6.    if (l%2==1) return l;  ///单数长度则不能分解
   
7.    int x=l/2;
   
8.    string s1=s.substr(0,x);  ///第一段
   
9.    string s2=s.substr(x,x);  ///第二段
   
10. 
    
11.    string s3="";
    
12.    ///cout<<s1<<' '<<s2<<' '<<s3<<endl;
    
13.    for (int i=0;i<=x-1;i++) s3=s2[i]+s3;
    
14.    if (s1==s3) return work (s1);else return l;
    
15. }
    
16. int main()
    
17. {
    
18.     string s;
    
19.     cin>>s;
    
20.     cout<<work(s);
    
21.     return 0;
    
22. }
    

复制代码