首页 > 代码库 > Gym 100712I Bahosain and Digits（开关翻转问题）
Gym 100712I Bahosain and Digits（开关翻转问题）
http://codeforces.com/gym/100712/attachments
题意：
给出一串数字，每次选择连续的k个数字加上任意数（超过10就取余），最后要使得所有数字都相等，求最大的k。
思路：
开关翻转问题。
算法具体可以参考《挑战程序竞赛》常用技巧篇。
这道题目就是在枚举k的同时再枚举一下最后要转换成的数字即可。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<sstream> 6 #include<vector> 7 #include<stack> 8 #include<queue> 9 #include<cmath>10 #include<map>11 using namespace std;12 typedef long long ll;13 typedef pair<int,long long> pll;14 const int INF = 0x3f3f;15 const int maxn=1000+5;16 17 int n,k;18 int a[maxn];19 int b[maxn];20 int f[maxn];21 char str[maxn];22 23 bool calc(int k)24 {25 memcpy(b,a,sizeof(a));26 for(int t=0;t<10;t++) //枚举最后转换的数27 {28 memset(f,0,sizeof(f));29 int sum=0;30 for(int i=0;i+k<=n;i++)31 {32 if(((b[i]+sum)%10)!=t)33 f[i]=((t-b[i]-sum)%10+10)%10;34 sum+=f[i];35 if(i-k+1>=0) sum-=f[i-k+1];36 }37 38 39 bool flag=true;40 for(int i=n-k+1;i<n;i++)41 {42 if(((b[i]+sum)%10)!=t)43 {44 flag=false;45 break;46 }47 if(i-k+1>=0) sum-=f[i-k+1];48 }49 if(flag) return true;50 }51 return false;52 }53 54 int main()55 {56 //freopen("input.txt","r",stdin);57 int T;58 scanf("%d",&T);59 while(T--)60 {61 getchar();62 scanf("%s",str);63 64 n=strlen(str);65 for(int i=0;i<n;i++) a[i]=str[i]-‘0‘;66 67 for(int k=n;k>=1;k--)68 {69 if(calc(k))70 {71 printf("%d\n",k);72 break;73 }74 }75 }76 return 0;77 }
Gym 100712I Bahosain and Digits（开关翻转问题）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。