信息学奥赛一本通T1461-Beads-题解（C++代码）

解题思路:通过第一层循环将串分为1-n个子窜的n/2种不同情况，通过2，3，4层循环将sum个子串记录下来，判断后面的第sum+1个子串与前面的sum各子串相比较是否等价，判断结束后记录子窜个数和对应的K值通过于max比较记录当前最大不同子串的K值；反回一层循环继续执行

注意事项:循环设计层数较多且每个循环涉及多个变量，时间效率较低

参考代码:

#include <iostream>

using namespace std; 

void jisuan(int *x){

int max=0;//记录最大K 

int mark=0;//判断是否与前面的子串相等价 

int l=0;

int a;

cin>>a; 

int *p=new int[a/2];//存储最大子串数对应的K值 

x=new int[a];

for(int n=0;n<a;n++) cin>>x[n];

for(int j=1;j<=a/2;j++){

int sum=1;//记录不同的子串数 

for(int i=j;i+j<=a;i+=j){//向后移动进行比较 

for(int s=1;s<=i/j;s++){//与前面s个子窜相比较 

     mark=0;

for(int f=1,k=i;f<=j;f++,k++){//正向判定字串与子串见是否等价 

if(x[k]!=x[k-j*s]) {

mark=1;

break;

}

}

if(mark==1){

for(int F=1,K=i,n=1;n<=j;F+=2,K++,n++){//判定子串是否反转等价 

if(x[K]!=x[K-j*(s-1)-F]){

mark=2;

break;

}

}

if(mark==1) mark=0;

}

if(mark==0) break;

}

if(mark==1||mark==2) sum++;

mark=0;

}

if(sum>max){

max=sum;

l=1;

p[l-1]=j;

}

else if(sum==max){

l++;

p[l-1]=j;

}

}

cout<<max<<' '<<l<<endl;

for(int v=0;v<l;v++) cout<<p[v]<<' ';

} 

int main(int argc, char** argv) {

int *p;

jisuan(p);

return 0;

}