SG函数
作用
对于一个状态i为先手必胜态当且仅当SG(i)!=0。
转移
那怎么得到SG函数尼。
SG(i)=mex(SG(j))(状态i可以通过一步转移到j)
首先说一下mex。一个集合的mex是最小的没有出现在这个集合里的非负整数。
其实想一下这个也是挺明显的。状态i是先手必败态当前仅当i转移到的状态都是先手必胜态。同样,只要当前状态可以转移到一个先手必败态,那么当前就是先手必胜态。
小定理
对于两个独立的游戏A,B,他们的SG函数=SG(A) ^ SG(B)
这个比较难描述,看一下后面的题就明白了。
真模板题
先来娱乐一下
题面
给一个有向无环图,一开始在某个节点有个棋子,Alice和Bob轮流操作,每次可以把石子移动一步。最后无法移动者失败。问是否存在先手必胜策略。
思路
SG函数的定义题。
出度为0的点的SG函数为1。每个点可以转移到的状态是可以走到的节点。直接在DAG上dp即可。
Nim游戏
博弈论入门必学。
Alice,Bob和一些石子的故事
level 1
有n堆石子,第i堆石子有a[i]个,Alic和Bob轮流选择一堆从里面拿走任意多个石子(不能不拿),最后无法操作者失败,问是否存在先手必胜态。
思路
这就是上面那个小定理的应用了。考虑只有一堆石子的情况,肯定是先手必胜态。SG函数肯定是石子个数(显然)。
那么整个游戏的SG函数就是每个子游戏(只有一堆石子的情况)SG函数的异或之和。
所以这个题只要判断所有石子个数异或和是不是0即可。
level 2
有一堆共n个石子,Alice和Bob轮流从这堆石子里面取1到k个,不能取者输。问是否存在先手必胜策略
思路
状态i可以转移到的状态就是i-j(1<=j<=k)
所以SG(i)=mex(SG(i-j)) (1<=j<=k)
假设k=3
则SG(0)=0,SG(1)=1,SG(2)=2,SG(3)=3,SG(4)=0,SG(5)=1...
可以发现,到4的时候开始重新从0开始。仔细想一下就能发现为啥了。这就相当于拿个长度为k的窗口在这个序列里面滑动。新进来的数的SG函数就是刚好从窗口的出去的那个。
所以只要判断所以当前游戏的SG函数就是n%(k+1)
level 3
有一堆n个石子,Alice和Bob轮流这堆石子里面取石子,每次可以取l-r个,问是否存在先手必胜态。
思路
找规律!!
假设l=3,r=7
SG=[0,0,0,1,1,1,2,2,2,3,0,0.....]
发现SG(i)=i%(l + r) / l
dyh:sg函数的取值不容易直接思考,并且如果找到了规律 ⼀般都可以⽤数学归纳法证明。
level 4
有n堆石子,第i堆石子有a[i]个,Alice和Bob轮流操作,每次可以从一堆石子里面取任意多个,也可以把一堆石子分成两堆。不能操作者输。问是否存在先手必胜态。
思路
SG(i)=mex(SG(i - j),SG(i-j) ^ SG(j))
SG(i-j)是从石子里面取j个,SG(i-j)^SG(j)是将石子分成j和i-j两堆。
level 5
有1堆石子,Alice和Bob轮流操作,每次可以从一堆里面取当前个数的因数个(不能是本身),不能操作者(剩下一个)输。问是否存在先手必胜态。
思路
SG(i) = mex(SG(i-k)) (k|i)
找规律可以发现
SG(i) = __builtin_ctz(i)
也就是i的末尾0的个数
level 6
有1堆石子,Alice和Bob轮流操作,每次可以从一堆里面取与当前个数互质的数字个石子,不能操作者输,问是否存在先手必胜态
思路
SG(i)=mex(SG(i-j)) (gcd(i,j)=1)
打表如下
发现,对于偶数,SG为0.
对于奇数,SG为最小质因子的编号(就是最小质因子是第几个质数)
杂题
小题题
给定一个n*m的网格,第一行和第一列的元素标记着为胜或者为负,在某个位置有一个石子,Alice和Bob轮流操作,每次可以把这个石子往左或者往上移动一步。问是否存在先手必胜策略。
思路
先建个图,就成了一个DAG上的dp。找规律可以发现对角线上的SG函数都是相同的。
CF388C
有n排石子,每排有若干堆。Ciel可以选择一排,拿走这一排的第一堆石子。Jiro可以选择一排,拿走这一排的最后一堆石子。两个人都想要让自己的石子数量最多。问两个人最后的石子数量。Ciel先手。
思路
先考虑Ciel,他肯定可以保证自己至少得到每排石子的左半边。只要按照下面的原则做就可以:
第一个石子先随便选,如果Jiro和自己拿同一排,那就随便再选一个。
如果Jiro没和自己拿同一排,那就去和Ciel拿同一排。
考虑Jiro,同样可以保证自己至少得到每排石子的右半边。只要每次都和Ciel选同一排即可。
综上,就可以确定Ciel和Jiro分别拿了左半边和右半边。
对于奇数排的中间那一堆,从大到小从Ciel开始轮流选就行了。
/* * @Author: wxyww * @Date: 2019-03-06 19:55:16 * @Last Modified time: 2019-03-06 19:58:43 */ #include<cstdio> #include<iostream> #include<cstdlib> #include<cmath> #include<ctime> #include<bitset> #include<cstring> #include<algorithm> #include<string> #include<queue> #include<vector> using namespace std; typedef long long ll; const int N = 1000; ll read() { ll x=0,f=1;char c=getchar(); while(c<'0'||c>'9') { if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c<='9') { x=x*10+c-'0'; c=getchar(); } return x*f; } ll ans1,ans2; int m; ll a[N]; bool cmp(int x,int y) { return x > y; } int main() { int n = read(); for(int i = 1;i <= n;++i) { int k = read(); int z = k >> 1; for(int j = 1;j <= z;++j) ans1 += read(); if(k & 1) a[++m] = read(); for(int j = 1;j <= z;++j) ans2 += read(); } sort(a + 1,a + m + 1,cmp); for(int i = 1;i <= m;++i) { if(i & 1) ans1 += a[i]; else ans2 += a[i]; } printf("%I64d %I64d\n",ans1,ans2); return 0; }