华师一附中OI组

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

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

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

输入输出样例
输入样例#1：
ABBAABBA
输出样例#1：
2
作者: admin    时间: 2018-5-5 19:52
一个串要是长度为偶数并且回文那么他可以由字串得到，这个子串递归判断，直到不是回文或者长度为奇数。
bool check(string s)  判断是否长度为奇数，或者不是回文
string get(string s)
{
  if (!check(s)) return s;
  else return (s的一半)
}
下面就不需要我再写下去了吧
作者: 张笑宇    时间: 2018-5-5 19:54
  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. }
复制代码
作者: 黄煦喆    时间: 2018-5-5 20:04
  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. }
复制代码
作者: 黄诗绮    时间: 2018-5-5 20:09
  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. }  
复制代码
作者: 王令欧    时间: 2018-5-5 20:32
  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. }
复制代码
作者: 王令欧    时间: 2018-5-5 20:38
  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    时间: 2019-3-15 15:44
  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);  ///第二段

  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. }
复制代码




欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2