花大力气写的模拟。。。等搜索练好了再回来做,另外把测试数据发一下。。
/* ID:linyvxi1 PROG:beads LANG:C++ */ #include <stdio.h> #include <string.h> int main() { FILE* fin=fopen("beads.in","r"); FILE* fout=fopen("beads.out","w"); int n; char str[400]; fscanf(fin,"%d",&n); fscanf(fin,"%s",str); bool flag1=false,flag2=false; int i=0,j=strlen(str)-1; char stat=str[0]; //while(i<=j&&(str[i]==str[i+1]||str[i+1]=='w'||str[i]=='w')) while(i<=j&&(str[i]==stat||str[i]=='w')) i++; stat=str[strlen(str)-1]; // while(j>=0&&(str[j]==str[j+1]||str[j]=='w'||str[j+1]=='w')) while(j>=0&&(str[j]==stat||str[j]=='w')) j--; int max,temp=0; if(i>=j){ fprintf(fout,"%d\n",strlen(str)); return 0; }//如果全相同。。。 else max=i+strlen(str)-1-j; for(i=1;i<=strlen(str)-1;i++){ int n=i,m=i-1,k; k=i-1; while(str[k]=='w') k++; stat=str[k]; // stat=str[i-1]; while(m>=0&&(str[m]==stat||str[m]=='w'))//标志位 m--;//左边是i-1-m个 k=n; while(str[k]=='w') k++; stat=str[k]; while(n<=strlen(str)-1&&(str[n]==stat||str[n]=='w')) n++;//右边是n-i个 if(m!=-1&&n!=strlen(str)){//如果都没数到头 int num=i-1-m+n-i; if(num>max) max=num; } // stat=str[i-1]; else if(m==-1&&n!=strlen(str)){//如果左边到头了右边没到头 k=i-1; while(str[k]=='w') k++; stat=str[k]; if(str[strlen(str)-1]==stat||str[strlen(str)-1]=='w'){//如果左边还能继续往下走 m=strlen(str)-1; while(str[m]==stat||str[m]=='w') m--;//右边是n-i个 //int sum=n-i+1+i-0+1+strlen(str)-1-m+1; int sum=n-i+strlen(str)-1-m+i; if(sum>max) max=sum; } else { int sum=i+n-i; if(sum>max) max=sum; } } // stat=str[i]; else if(m!=-1&&strlen(str)==n){//如果左边没到头右边到头了 k=i; while(str[k]=='w') k++; stat=str[k]; if(str[0]=='w'||str[0]==stat){//如果右边还能继续走下去 n=0; while(str[n]==stat||str[n]=='w') n++;//又走了n个 // int sum=n-0+1+i-1-m+1+strlen(str)-1-i+1; int sum=n+i-1-m+strlen(str)-1-i+1; if(sum>max) max=sum; } else{ // int sum=i-1-m+1+strlen(str)-1-i+1; int sum=i-1-m+strlen(str)-i; if(sum>max) max=sum; } } else{//两边都到头了 max=strlen(str); break; } } fprintf(fout,"%d\n",max); }
Here are the test data inputs:
------- test 1 ---- 29 wwwbbrwrbrbrrbrbrwrwwrbwrwrrb ------- test 2 ---- 3 rrr ------- test 3 ---- 77 rwrwrwrwrwrwrwrwrwrwrwrwbwrwbwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwr ------- test 4 ---- 17 wwwwwwwwwwwwwwwww ------- test 5 ---- 50 bbrrrbrrrrrrrrbrbbbrbrrbrrrrbbbrbrbbbbbrbrrrbbrbbb ------- test 6 ---- 8 rrwwwwbb ------- test 7 ---- 200 rrrrrrrrrrrrrrrrrrrrbbbbbbbbbbbbbbbbbbbbrrrrrrrrrrrrrrrrrrrrbbbbbbbbbbbbbbbbbbbbrrrrrrrrrrrrrrrrrrrrbbbbbbbbbbbbbbbbbbbbrrrrrrrrrrrrrrrrrrrrbbbbbbbbbbbbbbbbbbbbrrrrrrrrrrrrrrrrrrrrbbbbbbbbbbbbbbbbbbbb ------- test 8 ---- 350 rrbbrbbbwbwwbwbbbbwwrrbbwbrwbrwbbbrbrwrwbrwwwrrbbrrwrbbrwbwrwwwrbrwwwwwrwbwwwrrbrrbbbrbrbbbrbbbrbbwbbbbbrbrrbrwwbrrrrwbwrwrbbwbwrbrbrwwbrrbwbrwwbwwwbrbwrwbwbrbbbwrbwwrrrbwbwbbbbbrrwwwrbrwwrbbwrbbrbbrbwrrwwbrrrbrwbrwwrbwbwrrrbwrwrrbrbbwrwrbrwwwrwbwrrwwwwrrrwrrwbbwrwwrwrbwwbwrrrrbbwrbbrbwwwwwbrbbrbbrbrwbbwbwwbbbbbwwwrbwwbbbwrwwbbrrwrwbwrrwwwrrrwrrwww ------- test 9 ---- 333 rwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwbrwb