hdu 4023 Game
题意：Alice还有Bob 轮流在已知的15中俄罗斯方块上放置瓷砖，Alice放置的是垂直的2*1的矩形，Bob放置的是水平的1*2的矩形，Alice 先开始放，最后没位置可以放者输，输出最后的胜者；
分析：题目看似博弈，却是一道贪心+模拟（其实我一开始也死命的认为是博弈，而且，因为博弈还没怎么搞过，就直接跳过了，是看了大牛的提示才知道的）；
有这样十五种俄罗斯方块：
很明显，各种方块对俩人而已是有利也有弊的，俩个人都有自己想优先选择放置的方块。
（1,2），都是对于自己稳定的
(3,4) (5,6) 前者对B最有利，后者对A最有利
（7,8），（9,10），前者对B最不利，后者对A最不利
（11,12,13,14），对A，B利害相同
（15）对自己最有利，对对方最不利
Alice的贪心顺序是：（15），（5,6），（3,4），（11,12,13,14），（7,8），（9,10）
Bob的贪心顺序是：（15），（3,4），（5,6），（11,12,13,14），（9,10），（7,8）
知道贪心的顺序之后，模拟也是得小心翼翼呀，orz
用变量ans[0],ans[1]分别记录Alice 和 Bob各自稳定的步数（就是肯定是只有他们各自可以放置的位置数，所以没有先放置），用变量now模拟过程，记录轮到谁放置了。之后按照贪心顺序模拟即可；
这里有一个 需要十分注意的地方：ans记录的是稳定步数而非可走的步数，（就是在这里WA了好多次），因为这里变量now已经模拟了（交换了放置顺序了).
最后剩余的稳定的步数最多者胜，相等则轮到谁谁就输了
#include
using namespace std; int s[16],ans[2]; int main() { int ta,tb,cas,T=0; cin>>cas; while(cas--) { for(int i=1;i<=15;i++) scanf("%d",&s[i]); ans[0]=s[1]*2; ans[1]=s[2]*2; int now=0; if(s[15]!=0) { if(s[15]%2!=0)//为奇数时，Alice会有一步是稳定的 { ans[0]++; now^=1; } } ta=s[5]+s[6]; tb=s[3]+s[4]; if(ta>tb)//差值要俩个人进行瓜分，ta>tb时， { ta-=tb; ans[0]+=ta/2;//Alice的稳定步数能增加差值的一半 if(ta%2==1) { if(!now)//若差值为奇数，而且，轮到Alice先拿，则Alice的稳定步数可增加1 ans[now]++; now^=1; } } else if(tb>ta) { tb-=ta; ans[1]+=tb/2; if(tb%2==1) { if(now) ans[now]++; now^=1; } } ta=s[11]+s[12]+s[13]+s[14]; now^=ta&1;//这里很重要，若为奇数，则轮到下一个人放置，稳定步数不增加 ta=s[7]+s[8]; tb=s[9]+s[10]; if(ta>tb)//和 上面类似，这种情况下，Bob每走一步，Alice就会多一步稳定步数 { ta-=tb; ans[0]+=ta/2; if(ta%2==1) { if(now) ans[!now]++; now^=1; } } else if(tb>ta) { tb-=ta; ans[1]+=tb/2; if(tb%2==1) { if(!now) ans[!now]++; now^=1; } } printf("Case #%d: ",++T); if(ans[0]==ans[1]) { if(now)puts("Alice"); else puts("Bob"); } else if(ans[0]>ans[1]) puts("Alice"); else puts("Bob"); } return 0; }
延伸阅读
最新评论