HDU 6020 MG loves apple （乱搞（）） _apple

幽沉谢世事，俯默窥唐虞。这篇文章主要讲述HDU 6020 MG loves apple （乱搞？）相关的知识，希望能为你提供帮助。

MG loves apple Accepts: 20 Submissions: 693 Time Limit: 3000/1500 MS (java/Others) Memory Limit: 262144/262144 K (Java/Others)问题描述
MGMG是一个财富爆表的男孩子。他拥有N(1< =N< =100000)N(1< =N< =100000)个苹果，每个苹果上标有一个数字00~99，代表它的价值。一个合法的数字是不含有前导零的，这nn个苹果恰好排成了一个合法的NN位数。MGMG拥有拿去KK个苹果的权利（0< =K< 0< =K< NN）。他想知道是否存在方案，使得恰好拿去KK个苹果后，序列中剩下的苹果排成的合法数字模33等于零。数据保证所有NN之和不超过10000001000000.MGMG认为这件事非常容易，不屑于用计算机解决，于是运用他高超的人类智慧开始进行计算。作为一名旁观者，你也想挑战MGMG智慧，请你写个程序，计算答案。

输入描述
第一行一个整数TT，代表数据组数（1 < =T< =601< =T< =60）。接下来，对于每组数据—— 第一行两个个整数NN,KK，表示苹果序列长度，以及需要拿去的苹果个数. 接下来一行NN个整数XX，表示每个苹果的价值（0< =X< =90< =X< =9）。

输出描述
对于每一组数据，输出一行。若方案存在，则输出“yes”，否则输出“no”。（输出不包含引号）

输入样例
2 5 2 11230 4 2 1000

输出样例
yes no

【分析】
写这个主要是我昨天WA了7次没A。。
怎么说，打法太容易出bug。。
【表示不知道别人是怎么做的。。。
为了保证没有前导0，我们枚举一个不为0的开头，于是问题变成了询问在a0个0，a1个1，a2个2中选x个数，他们加上y能不能模3等于0。
这个东西啊，我是不敢枚举什么的。我们可以先随便选x个数，然后判断，不行的话，交换1个或者两个选了和没选的数，再判断。
显然交换的数的个数不会超过2个的哦。
这里我就暴力枚举交换的东西了。
【HDU 6020 MG loves apple （乱搞（））】【主要是我昨天没有枚举最前面的数，而是贪心先删掉后k个再交换，然后前面交换时的前导0没有了保证，就搞了很久。。。
【还是ORZ那些秒A的人

文章图片

1 #include< cstdio> 2 #include< cstdlib> 3 #include< cstring> 4 #include< iostream> 5 #include< algorithm> 6 using namespace std; 7 #define Maxn 100010 8 9 int mymax(int x,int y) {return x> y?x:y; } 10 int mymin(int x,int y) {return x< y?x:y; } 11 12 int f[Maxn][3]; 13 int b[3],c[3]; 14 15 bool check(int a0,int a1,int a2,int x,int y) 16 { 17// if(x==0) return y==0; 18// if(x==1) return (y==0& & a0)||(y==1& & a1)||(y==2& & a2); 19int h=0; 20b[0]=b[1]=b[2]=c[0]=c[1]=c[2]=0; 21b[0]=mymin(a0,x); c[0]=a0-b[0],x-=b[0]; 22b[1]=mymin(a1,x); c[1]=a1-b[1],x-=b[1],h=(h+b[1])%3; 23b[2]=mymin(a2,x); c[2]=a2-b[2],x-=b[2],h=(h+b[2]*2)%3; 24if((h+y)%3==0) return 1; 25 26for(int i=0; i< 3; i++) if(b[i]) 27for(int j=0; j< 3; j++) if(c[j]) 28if(((h-i+j+y)%3+3)%3==0) return 1; 29 30for(int i=0; i< 3; i++) if(b[i]) 31{ 32b[i]--; 33for(int ii=0; ii< 3; ii++) if(b[ii]) 34{ 35for(int j=0; j< 3; j++) if(c[j]) 36{ 37c[j]--; 38for(int jj=0; jj< 3; jj++) if(c[jj]) 39{ 40if(((h-i-ii+j+jj+y)%3+3)%3==0) return 1; 41} 42c[j]++; 43} 44} 45b[i]++; 46} 47return 0; 48 } 49 50 int a[Maxn]; 51 char s[Maxn]; 52 53 int main() 54 { 55int T; 56scanf("%d",& T); 57while(T--) 58{ 59int n,k; 60scanf("%d%d",& n,& k); 61scanf("%s",s+1); 62for(int i=1; i< =n; i++) a[i]=s[i]-‘0‘; 63if(k==n-1) 64{ 65bool ok=0; 66for(int i=1; i< =n; i++) if(a[i]%3==0) ok=1; 67if(ok) printf("yes\n"); 68else printf("no\n"); 69continue; 70} 71memset(f,0,sizeof(f)); 72for(int i=1; i< =n; i++) 73for(int j=0; j< 3; j++) f[i][j]=f[i-1][j]+(a[i]%3==j); 74k=n-k; 75bool ok=0; 76for(int i=1; i< =n-k+1; i++) if(a[i]!=0) 77{ 78if(check(f[n][0]-f[i][0],f[n][1]-f[i][1],f[n][2]-f[i][2],k-1,a[i]%3)) {ok=1; break; } 79} 80if(ok) printf("yes\n"); 81else printf("no\n"); 82} 83return 0; 84 }

View Code
2017-04-02 08:51:33