2020-2021:teams:legal_string:王智彪:博弈论
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:王智彪:博弈论 [2021/08/12 21:13] 王智彪 |
2020-2021:teams:legal_string:王智彪:博弈论 [2021/09/14 11:20] (当前版本) 王智彪 |
||
|---|---|---|---|
| 行 147: | 行 147: | ||
| 比如 $k=3$ ： | 比如 $k=3$ ： | ||
| - | 由上，只考虑单枚硬币向上的情况。显然 $sg[1]=sg[2]=0,sg[3]=mex(sg[2]^sg[1])=1$ | + | 由上，只考虑单枚硬币向上的情况。显然 $sg[1]=sg[2]=0,sg[3]=mex(sg[2]$ ^ $sg[1])=1$ |
| $N=3t$ 时，先手必赢， $sg[3t]=1$ ，其余必输， $sg[3t+1]=sg[3t+2]=0$ 。 | $N=3t$ 时，先手必赢， $sg[3t]=1$ ，其余必输， $sg[3t+1]=sg[3t+2]=0$ 。 | ||
| - | 因为 $3t$ 翻完之后，会变成 $3t-1$ 和 $3t-2$ 这两种情况的异或和，也就是 $sg[3t]=mex(sg[3t-1]^sg[3t-2])=1$ ，对于 $3t+1$ ，$sg[3t+1]=mex(sg[3t]^sg[3t-1])=mex(1)=0$ ，对于 $3t+2$ ，同理。 | + | 因为 $3t$ 翻完之后，会变成 $3t-1$ 和 $3t-2$ 这两种情况的异或和，也就是 $sg[3t]=mex(sg[3t-1]$ ^ $sg[3t-2])=1$ ，对于 $3t+1$ ，$sg[3t+1]=mex(sg[3t]$ ^ $sg[3t-1])=mex(1)=0$ ，对于 $3t+2$ ，同理。 |
| 推广到别的值也成立。 | 推广到别的值也成立。 | ||
| 行 466: | 行 466: | ||
| printf("%s\n",flag?"Grammy":"Alice"); | printf("%s\n",flag?"Grammy":"Alice"); | ||
| } | } | ||
| + | } | ||
| + | return 0; | ||
| + | } | ||
| + | |||
| + | </code> | ||
| + | |||
| + | </hidden> | ||
| + | |||
| + | 2.[[https://ac.nowcoder.com/acm/contest/11166/A|2021牛客1A]] | ||
| + | |||
| + | 题目大意：给定两堆石子，有两个人，每次可以在两堆中分别取 $k$ 和 $s×k$ 个石子，其中 $k＞0,s≥0$ 。谁先取完谁赢，问先后手谁必胜。石子数量都不超过 $5000$ 。 | ||
| + | |||
| + | 这个数据范围大概率是筛出来的，仿照前面的威佐夫博弈和线性筛思想打个表就好了，对于必败态，能到达必败态的都是必胜态。 | ||
| + | |||
| + | <hidden 题解> | ||
| + | |||
| + | <code cpp> | ||
| + | |||
| + | #include <bits/stdc++.h> | ||
| + | using namespace std; | ||
| + | typedef long long ll; | ||
| + | |||
| + | const int maxn=5000; | ||
| + | bool dp[5010][5010]; | ||
| + | |||
| + | void get_ab() { | ||
| + | for(int i=0;i<=maxn;i++) { | ||
| + | for(int j=0;j<=maxn;j++) { | ||
| + | if(!dp[i][j]) { | ||
| + | for(int k=1;k<=maxn;k++) { | ||
| + | if(i+k>maxn&&j+k>maxn) break; | ||
| + | for(int s=0;s<=maxn;s++) { | ||
| + | if(i+k*s>maxn&&j+k*s>maxn) break; | ||
| + | if(i+k*s<=maxn&&j+k<=maxn) dp[i+k*s][j+k]=true; | ||
| + | if(i+k<=maxn&&j+k*s<=maxn) dp[i+k][j+k*s]=true; | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | |||
| + | int main() { | ||
| + | get_ab(); | ||
| + | int t,a,b; | ||
| + | scanf("%d",&t); | ||
| + | while(t--) { | ||
| + | scanf("%d %d",&a,&b); | ||
| + | if(dp[a][b]) puts("Alice"); | ||
| + | else puts("Bob"); | ||
| + | } | ||
| + | return 0; | ||
| + | } | ||
| + | |||
| + | </code> | ||
| + | |||
| + | </hidden> | ||
| + | |||
| + | ps:这玩意本地跑得太慢了，还是牛客的机器好用 $×$ | ||
| + | |||
| + | 3.[[https://ac.nowcoder.com/acm/problem/15066|小牛再战]] | ||
| + | |||
| + | 题意：共有 $n$ 堆石子，两个人轮流取石子，每次只能选择 $n$ 堆石子中的一堆取一定数量（至少一个）的石子，取过之后，还可以将这堆石子中剩余的石子随意取几个放在其他任意堆上，取完石子的人获胜，一堆石子没有子之后是不能放的。问先手能不能赢。 | ||
| + | |||
| + | 题解：给出结论：当所有堆都有配对的堆（指石子数一样的两堆石子）的时候，先手必败，不然先手必胜。 | ||
| + | |||
| + | 因为如果都配对了，先手做什么后手只需要拿另一堆石子开刀做几乎完全一样的事情就可以继续使石子都配对，这样先手必败，不完全一样的事情是比如 $a,b$ 两堆石子配对数量一样， $a$ 拿走之后又取了一堆之后消失了，这样 $b$ 还给 $a$ 的那部分可以归到取走里，这样还是配对的。 | ||
| + | |||
| + | 如果不完全配对，我们选择出现奇数次中最大的石子堆，比如现在是 $2\ 6\ 8\ 9$ ，然后拿 $9$ 这一堆，至少拿一个变成 $8$ ，然后我们把 $6$ 这堆补到 $8$ ，然后 $8$ 变成 $6$ ，再接着找更少的，如果最开始奇数的堆数是偶数，就把自己保留到最少的那堆石子数，不然剩下的也取走，这样保证所有都配对，后手必败，所以先手必胜。 | ||
| + | |||
| + | <hidden 代码> | ||
| + | |||
| + | <code cpp> | ||
| + | |||
| + | #include <bits/stdc++.h> | ||
| + | using namespace std; | ||
| + | typedef long long ll; | ||
| + | |||
| + | int n,tong[101]; | ||
| + | |||
| + | int main() { | ||
| + | while(~scanf("%d",&n)&&n) { | ||
| + | memset(tong,0,sizeof(tong)); | ||
| + | for(int i=1,tmp;i<=n;i++) { | ||
| + | scanf("%d",&tmp); | ||
| + | tong[tmp]++; | ||
| + | } | ||
| + | int flag=0; | ||
| + | for(int i=1;i<=100;i++) { | ||
| + | if(tong[i]&1) { | ||
| + | flag=1; | ||
| + | break; | ||
| + | } | ||
| + | } | ||
| + | if(flag) { | ||
| + | puts("Win"); | ||
| + | }else puts("Lose"); | ||
| } | } | ||
| return 0; | return 0; | ||
2020-2021/teams/legal_string/王智彪/博弈论.1628773996.txt.gz · 最后更改: 2021/08/12 21:13 由 王智彪
