2020-2021:teams:wangzai_milk:一些敲简单的博弈论
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:wangzai_milk:一些敲简单的博弈论 [2020/05/22 21:28] infinity37 创建 |
2020-2021:teams:wangzai_milk:一些敲简单的博弈论 [2020/05/22 21:30] (当前版本) infinity37 |
||
|---|---|---|---|
| 行 147: | 行 147: | ||
| $n,p,q\leq 65536$ | $n,p,q\leq 65536$ | ||
| ====题目分析==== | ====题目分析==== | ||
| - | 看到这么大的数据范围，我们必然是要求sg函数打表然后找规律了，每次把-[p,q]之间的sg值都标为vis,然后每次取最小的没出现过的自然数为当前局面的sg值，发现如果有n%(p+q)<=p的话那么其sg函数值一定是0，然后这个问题就可以完美解决啦 | + | 看到这么大的数据范围，我们必然是要求sg函数打表然后找规律了，每次把-[p,q]之间的sg值都标为vis,然后每次取最小的没出现过的自然数为当前局面的sg值，发现如果有n%(p+q)$\leq$p的话那么其sg函数值一定是0，然后这个问题就可以完美解决啦 |
| ====代码==== | ====代码==== | ||
| <hidden> | <hidden> | ||
| 行 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/一些敲简单的博弈论.1590154100.txt.gz · 最后更改: 2020/05/22 21:28 由 infinity37
