2020-2021:teams:wangzai_milk:一些敲简单的博弈论
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:wangzai_milk:一些敲简单的博弈论 [2020/05/22 21:29] infinity37 [题目分析] |
2020-2021:teams:wangzai_milk:一些敲简单的博弈论 [2020/05/22 21:30] (当前版本) infinity37 |
||
|---|---|---|---|
| 行 159: | 行 159: | ||
| if(n%(p+q)>p||n%(p+q)==0)printf("WIN\n"); | if(n%(p+q)>p||n%(p+q)==0)printf("WIN\n"); | ||
| else printf("LOST\n"); | else printf("LOST\n"); | ||
| - | } | ||
| - | } | ||
| - | </code> | ||
| - | </hidden> | ||
| - | \\ | ||
| - | =====HDU3032-Nim or not Nim?===== | ||
| - | ====题目大意==== | ||
| - | 给定n堆石子，现在玩一个规则稍有不同的nim游戏，我们一次可以从一堆石子中取走若干个，也可以将一堆石子分为较小的两堆，问先手是否有必胜策略。 | ||
| - | ====数据范围==== | ||
| - | $n\leq 10^6$,$s_i\leq 10^8$ | ||
| - | ====题目分析==== | ||
| - | 好，大范围继续sg函数打表找规律。 | ||
| - | sg函数这样设计，求值为i的sg函数时，把从0~i-1的局面的sg函数值标vis,然后把sg(1)^sg(i-1)，sg(2)^sg(i-2)……等一系列局面的函数值标vis，然后每次取当前没被标vis的最小自然数即可。 | ||
| - | 发现最后的sg(4k) = 4k-1,sg(4k+1) = 4k+1,sg(4k+2) = 4k+2,sg(4k+3) = 4k+4 | ||
| - | 然后是否有先手策略只需要把所有游戏的sg异或起来看是否为0即可 | ||
| - | ====代码==== | ||
| - | <hidden> | ||
| - | <code c++> | ||
| - | #include <stdio.h> | ||
| - | int main() | ||
| - | { | ||
| - | int cas; | ||
| - | scanf("%d",&cas); | ||
| - | while(cas--) | ||
| - | { | ||
| - | int n,x,ans = 0; | ||
| - | scanf("%d",&n); | ||
| - | while(n--) | ||
| - | { | ||
| - | scanf("%d",&x); | ||
| - | if(x%4==0)x = x-1; | ||
| - | else if(x%4==3)x = x+1; | ||
| - | ans = ans^x; | ||
| - | } | ||
| - | if(ans)printf("Alice\n"); | ||
| - | else printf("Bob\n"); | ||
| } | } | ||
| } | } | ||
2020-2021/teams/wangzai_milk/一些敲简单的博弈论.1590154164.txt.gz · 最后更改: 2020/05/22 21:29 由 infinity37
