CVBB ACM Team

到此差别页面的链接

--- 2020-2021:teams:legal_string:王智彪:博弈论 [2021/08/11 21:26]
王智彪
+++ 2020-2021:teams:legal_string:王智彪:博弈论 [2021/09/14 11:20] (当前版本)
王智彪
@@ 行 147: / 行 147: @@
 比如 $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$ 。
-因为 $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$ ，同理。
 推广到别的值也成立。
@@ 行 301: / 行 301: @@
 又比如一个根节点，有三个儿子， $len1=0,len2=1,len3=2$ （指链长），这个异或和肯定不为 $0$ ，但是先手必败，注意到都加一的异或和好像是 $0$ ，然后这么猜想一下 $×$ ，就能猜到结论了：父亲的 $sg$ 值是所有儿子 $sg+1$ 异或起来。然后树形 $dp$ 一下就好了。复杂度是 $O(N)$ 的。
+证明如下：
+注意到 $sg$ 值一样的游戏是可以相互转化的，如果我们求出来儿子的 $sg$ 值（类似于归纳法），我们就将其等价于一个长度为此 $sg$ 值的链，然后注意到父亲到儿子还有一条边，这边的 $sg$ 值就是儿子 $sg$ 值加一，然后所有的游戏互相独立，所以就是异或起来就可以了。
+===== 图删边游戏 =====
+刚才的树变成了图，其余规则不变。
+相比于树，图多了一些环，有些是奇环，有些是偶环。
+对于偶环，删掉一个边之后，剩下的两个链长度不同奇偶，所以异或之后的值不可能为 $0$ ，所以 $sg$ 值必为 $0$ ，所以等效于一个点的情况（ $sg$ 值也为 $0$ ）
+对于奇环，删掉一个边之后，剩下的两个链长度同奇偶，所以异或的 $sg$ 值不可能为奇数，又因为可以拆成两个长度相同的链，所以 $mex$ 值必为 $1$ ，所以相当于一个长度为 $1$ 的链。剩下就变成上一个问题了。
 ===== 威佐夫博弈 =====
@@ 行 335: / 行 349: @@
 </hidden>
+这里引申出一个贝蒂定理：如果 $a,b$ 是正无理数，且 ${\frac 1 a}+{\frac 1 b}=1$ ，则 $(int)[na]$ 和 $(int)[nb]$ 可以取遍所有的正整数。这个是高中数竞的内容这里不证明了。在这里 $a={\frac 1 {fi}},b={\frac 1 {fi^{2}}}$ 。所以包含了所有的必败解。
+===== 对称性构造 =====
+现在有 $n$ 个硬币围成一圈，每个硬币放在一个凹槽里，操作是每次可以选 $1$ 到 $k$ 个连续硬币取走。取完的赢，问先后手谁赢。
+分类讨论：
+. $k≥n$ ，先手必胜，直接全部取走就可以了。
+. $k==1$ ，根据 $n$ 的奇偶性， $n$ 奇先手赢，偶后手赢
+. 其余的 $k$ ，都是后手赢。
+关于第三种情况，为什么？
+先手显然不会一下子取走一大半，这时后手可以把剩下的都取走。
+那么不妨设先手取走一小部分，然后后手只需要在剩下圆弧的中间取走一个或两个（根据剩余数量的奇偶性而定），然后剩余两个部分是完全相同的就可以了，这时两边是对称的，先手怎么做，后手在另一堆怎么做就可以了，于是后手必胜，证毕。
+===== 二分图博弈 =====
+两个人在二分图上玩游戏，每次一个人沿边移动棋子，棋子待过的点不能再走，不能走的输，问谁赢。
+结论：考虑二分图最大匹配，如果最大匹配一定包含起点，先手胜，此外后手胜利。然后只需要算一下包含和不包含这个点的最大匹配相不相等即可。
+然后如果最大匹配一定包含这个点，对于先手，沿着最大匹配走，如果后手能走到另一个点结束，先手走不动，说明那个点完全可以代替这个点，则这个点并不是最大匹配所必须包含的，然后后手走完先手必然还能走，如果这个点没有匹配的，也说明起点不是最大匹配所必须包含的，也矛盾，所以走到的这个点必然可以进行匹配，则先手可以继续走，周而复始，后手早晚会走不动，所以先手必胜，证毕。
+反之，如果可以不包含这个点，这个点走出去的点，一定在最大匹配中，不然加上这两个点最大匹配更大了，矛盾，则由上，后手必胜，所以先手必败，证毕。
+===== 斐波那契博弈 =====
+一堆石子有 $n$ 个，两人轮流取，先取者第一次可以取任意多个，但是不能取完，以后每次取的石子数不能超过上次取石子数的二倍，取完者赢。
+结论：先手胜当且仅当 $n$ 不是斐波那契数。
+因为 $i=2$ 时，先手只能取 $1$ 颗，显然必败，结论成立。
+假设当取到斐波那契的第 $k$ 项都已经成立：
+当为 $k+1$ 项时，可以拆分为 $f_{k}+f_{k-1}$
+如果拿走的石子数大于等于 $f_{k-1}$ ，则可以直接拿走剩下的，因为 $f_{k}≤2f_{k-1}$
+不然，我就先玩完 $f_{k-1}$ 的游戏，由归纳法知，一定是我结束了 $f_{k-1}$ 的游戏，所以接下来剩 $f_{k}$ ，又是你先玩，并且，我这一下最多拿走 ${\frac 2 3}f_{k-1}$ ，所以你最多拿 ${\frac 4 3}f_{k-1}＜f_{k}$ ，这个可以由归纳法证明，所以你一次拿不完，由归纳法知你输了，所以 $k+1$ 的情况也递归出来了，所以得证。
+不是斐波那契数列的情况由某定理可知，我可以将其分为若干个斐波那契项之和，每次取尽量大的。因为每次都取尽可能大的，所以这些斐波那契项必不相邻，所以相邻的倍数差两倍以上。然后先手取完这个最小的斐波那契数那么多。后手显然只能在倒数第二堆里取，且取不完，然后根据上面的结论，我一定可以取走这一堆中的最后一个石子，然后你又要面对下一堆...，这样每一堆的最后一个石子都是我取走的，所以最后也是我取走的，所以先手必胜，得证。
+===== 代码练习 =====
+.[[https://codeforces.com/gym/103119/problem/G|2020ACM-ICPC澳门区域赛G]]
+题目大意：给定一个长度为 $n,1≤n≤200000$ 的数组和 $m,1≤m≤200000$ 个操作，每个数的范围为 $[0,255]$ 。
+操作 $1$ 是在数组末尾添加一个数，操作 $2$ 是再给一个位置，问从这个位置按照规则两人博弈谁能获得胜利。
+博弈规则是，每次只能选下标比当前数大的数字并且这个数字的二进制要和原来数的二进制不同的位数不能超过 $1$ ，跳到那个位置，谁不能跳谁输。
+注意到数字较小，我们可以对值进行操作。又发现对于出现了很多次的同一个数字，如果我们当前所在位置不是这个数最后一次出现的位置，则这个位置是必胜态，因为如果这个数出现的最后一个位置是必败态，则我们可以跳到这个位置，于是现在这个位置必胜。如果最后那个位置是必胜态，那说明后面必存在必败态，我们只需要到达那个必败态就可以了。
+综上，如果不是这个值最后一次出现的位置，都是必胜态。
+然后对于这个值最后一次出现的位置，我们看看他能到哪些值，这些值都是可以预处理的，然后因为上面的结论，我们不可能选择去能到达值的非最终位置的，因为相对于我来说是必败的，所以我们也是去这些值的最后位置，所以我们只需要记录每个值最后一次出现的位置就可以了。
+然后对于查询的位置，先看是不是最后一个位置，不是的话直接输出先手必胜。是最后一个位置就 $dfs$ 一下能到达哪些位置，然后记忆化搜索一下，看看有没有必败态就可以了。
+<hidden 代码>
+<code cpp>
+const int maxn=400100,maxm=260;
+vector<int> nxt[260];
+int n,m;
+int las[maxm],a[maxn],vis[maxm];
+bool ok[maxm];
+bool dfs(int pos) {
+	if(vis[a[pos]]) return ok[a[pos]];
+	vis[a[pos]]=true;
+	bool flag=false;
+	for(int i=0;i<nxt[a[pos]].size();i++) {
+		if(las[nxt[a[pos]][i]]<las[a[pos]]) continue;
+		flag|=(!dfs(las[nxt[a[pos]][i]]));
+	}
+	return ok[a[pos]]=flag;
+}
+int main() {
+	scanf("%d %d",&n,&m);
+	for(int i=0;i<=255;i++) {
+		for(int j=0;j<8;j++) {
+			nxt[i].push_back(i^(1<<j));
+		}
+	}
+	for(int i=1;i<=n;i++) {
+		scanf("%d",&a[i]);
+		las[a[i]]=i;
+	}
+	for(int i=1,op,key;i<=m;i++) {
+		scanf("%d %d",&op,&key);
+		if(op==1) {
+			a[++n]=key;
+			las[a[n]]=n;
+		}else {
+			if(las[a[key]]!=key) {
+				puts("Grammy");
+				continue;
+			}
+			memset(vis,0,sizeof(vis));
+			memset(ok,0,sizeof(ok));
+			bool flag=dfs(key);
+			printf("%s\n",flag?"Grammy":"Alice");
+		}
+	}
+	return 0;
+}
+</code>
+</hidden>
+.[[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:这玩意本地跑得太慢了，还是牛客的机器好用 $×$
+.[[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;
+}
+</code>
+</hidden>

CVBB ACM Team

用户工具

站点工具

页面工具