Gym 100712I Bahosain and Digits（开关翻转问题）

http://codeforces.com/gym/100712/attachments

题意：

给出一串数字，每次选择连续的k个数字加上任意数（超过10就取余），最后要使得所有数字都相等，求最大的k。

思路：

开关翻转问题。

算法具体可以参考《挑战程序竞赛》常用技巧篇。

这道题目就是在枚举k的同时再枚举一下最后要转换成的数字即可。

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cstdio>

 #include<sstream>

 #include<vector>

 #include<stack>

 #include<queue>

 #include<cmath>

 #include<map>

 using namespace std;

 typedef long long ll;

 typedef pair<int,long long> pll;

 const int INF = 0x3f3f;

 const int maxn=+;

 int n,k;

 int a[maxn];

 int b[maxn];

 int f[maxn];

 char str[maxn];

 bool calc(int k)

 {

     memcpy(b,a,sizeof(a));

     for(int t=;t<;t++)   //枚举最后转换的数

     {

         memset(f,,sizeof(f));

         int sum=;

         for(int i=;i+k<=n;i++)

         {

             if(((b[i]+sum)%)!=t)

                 f[i]=((t-b[i]-sum)%+)%;

             sum+=f[i];

             if(i-k+>=)  sum-=f[i-k+];

         }

         bool flag=true;

         for(int i=n-k+;i<n;i++)

         {

             if(((b[i]+sum)%)!=t)

             {

                 flag=false;

                 break;

             }

             if(i-k+>=)  sum-=f[i-k+];

         }

         if(flag)  return true;

     }

     return false;

 }

 int main()

 {

     //freopen("input.txt","r",stdin);

     int T;

     scanf("%d",&T);

     while(T--)

     {

         getchar();

         scanf("%s",str);

         n=strlen(str);

         for(int i=;i<n;i++)  a[i]=str[i]-'';

         for(int k=n;k>=;k--)

         {

             if(calc(k))

             {

                 printf("%d\n",k);

                 break;

             }

         }

     }

     return ;

 }