首页 > 代码库 > hdu 5090 Game with Pearls (额,, 想法题吧 / 二分图最大匹配也可做)
hdu 5090 Game with Pearls (额,, 想法题吧 / 二分图最大匹配也可做)
题意:
给你N个数,a1,,,,an。代表第i个管子里有ai个珍珠。
规定只能往每根管里增加k的倍数个珍珠。
如果存在一套操作,操作完毕后可以得到1~N的一个排列,则Jerry赢,否则Tom赢。
问谁赢。
思路:
将a1...an从小到大排序,可知道每根管里的数只能增不能减。将最后的1...N中的每个数一定是由小于等于它的数加上若干个K得到来的。
额..直接看代码吧
代码:
int a[1005];int m,n,k;int main(){ //freopen("test.in","r",stdin); cin>>m; while(m--){ scanf("%d%d",&n,&k); mem(a,0); rep(i,1,n){ int x; scanf("%d",&x); a[x]+=1; } int win=1; a[k]+=(a[0]); rep(i,1,n){ if(a[i]==0){ win=0; break; } --a[i]; //消掉一根管 if(a[i]!=0 && i+k<=n) a[i+k]+=(a[i]); //有a[i]个珍珠的管子的珍珠数都加K。 } if(!win) puts("Tom"); else puts("Jerry"); } //fclose(stdin);}
hdu 5090 Game with Pearls (额,, 想法题吧 / 二分图最大匹配也可做)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。