POJ1704 Georgia and Bob

深藏阁楼爱情的钟 2022-10-02 15:59 255阅读 0赞

1332167-20190318141010776-1480049737.png

有个很毒瘤的事就是位置不是按顺序给出的……

发现每次我们能够把一个棋子向左挪且不能越过下一个。那么考虑两个棋子之间的间隙，就是一个阶梯博弈了。

ContractedBlock.gif ExpandedBlockStart.gif

  1. 1 #include <cstdio>
  2.  2 #include <algorithm>
  3.  3 
  4.  4 const int N = 100010;
  5.  5 
  6.  6 int a[N], b[N];
  7.  7 
  8.  8 inline void solve() {
  9.  9     int n;
  10. 10     scanf("%d", &n);
  11. 11     for(int i = 1; i <= n; i++) {
  12. 12         scanf("%d", &a[i]);
  13. 13     }
  14. 14     std::sort(a + 1, a + n + 1);
  15. 15     for(int i = 1; i <= n; i++) b[i] = a[i] - a[i - 1] - 1;
  16. 16     int ans = 0;
  17. 17     for(int i = n; i >= 1; i -= 2) {
  18. 18         ans ^= b[i];
  19. 19     }
  20. 20     if(ans) {
  21. 21         printf("Georgia will win\n");
  22. 22     }
  23. 23     else printf("Bob will win\n");
  24. 24     return;
  25. 25 }
  26. 26 
  27. 27 int main() {
  28. 28     int T;
  29. 29     scanf("%d", &T);
  30. 30     while(T--) {
  31. 31         solve();
  32. 32     }
  33. 33 
  34. 34     return 0;
  35. 35 }

AC代码

转载于:https://www.cnblogs.com/huyufeifei/p/10551889.html

发表评论

表情：
评论列表 （有 0 条评论，255人围观）

还没有评论，来说两句吧...

相关阅读