《博弈论（取石子游戏）dp+分析.docx》由会员分享，可在线阅读，更多相关《博弈论（取石子游戏）dp+分析.docx（8页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、博弈论(取石子游戏)dp+分析题目描述给定一个有NN个节点的有向无环图，图中某些节点上有棋子，两名玩家交替移动棋子。玩家每一步可将任意一颗棋子沿一条有向边移动到另一个点，无法移动者输掉游戏。对于给定的图和棋子初始位置，双方都会采取最优的行动，询问先手必胜还是先手必败。输入格式第一行，三个整数N,M,KN,M,K，NN表示图中节点总数，MM表示图中边的条数，KK表示棋子的个数。接下来M行，每行两个整数X,YX,Y表示有一条边从点XX出发指向点YY。接下来一行，KK个空格间隔的整数，表示初始时，棋子所在的节点编号。节点编号从11到NN。输出格式若先手胜，输出win，否则输出lose。数据范围1 W
2、NW2000,1 WNW2000,1 WMW6000,1 WMW6000,1WKWN1WKWN输入样例：6 8 42 12 41 41 54 51 33 53 61 2 4 6输出样例：win这题咋没人写题解嘞qwqqwqSG函数首先定义mexmex函数，这是施加于一个集合的函数，返回最小的不属于这个集合的非负整数例：mex(1,2)=0,mex(0,1)=2,mex(0,1,2,4)=3mex(1,2)=0,mex(0,1)=2,mex(0,1,2,4)=3在一张有向无环图中，对于每个点uu，设其所有能到的点的SGSG函数值集合为集合AA，那么uu的SGSG函数值为 mex(A)mex(A)
3、，记做 SG(u)=mex(A)SG(u)=mex(A)例图：例图解释：SG(5)=mex(0)=0SG(5)=mex(0)=0SG(3)=mex(SG(5)=mex(0) = 1SG(3)=mex(SG(5)=mex(0) = 1SG(4)=mex(SG(5),SG(3)=mex(0,1)=2SG(4)=mex(SG(5),SG(3)=mex(0,1)=2SG(2)=mex(SG(3)=mex(1)=0SG(2)=mex(SG(3)=mex(1 )=0SG(1)=mex(SG(2),SG(4)=mex(0,2) = 1SG(1)=mex(SG(2),SG(4)=mex(0,2)=1那么SGS
4、G函数的定义说完了，这题和SGSG函数又有什么关系呢？下面先说本题做法，再证明该方法正确性。做法：求出每个棋子所在的点的SGSG函数值，将所有值异或起来。若异或值不为00，则输出win，否则输出lose 证明：首先，由于这是一张有向无环图，所以游戏最后一定会结束，也就是说每个棋子最后都会移动到一个点上，且该点没有任何能到达的点。 那么根据定义，结束状态的所有点的SGSG函数值异或起来为00,做法对于结束状态可行。所以接下来，只要证明出任何一种每个棋子所在点的SGSG函数值异或起来非00的情况，一定能通过一次移动棋子，到达一个每个棋子所在点的SGSG函数值 异或起来为00的情况任何一种每个棋子所
5、在点的SGSG函数值异或起来为00的情况，一定不能通过一次移动棋子，到达一个每个棋子所在点的SGSG函数值 异或起来为 00 的情况 那么做法就是对的证明1:设每个棋子所在点的SGSG函数值分别为a1,a2,ana1,a2,an设 x=a1 XOR a2 XOR XOR anx=a1 XOR a2 XOR XOR an,设 xx 的最高位为第 kk 位，那么在 a1,a2,ana1,a2,an 中， 定有一个值的第kk位为11设该值为aiai，那么由于xx的第kk位和aiai的第kk位都是11,且第kk位是xx的最高位，所以ai XOR xai XOR x 一定小于aiai 又因为aiai是其
6、中一个棋子所在点的SGSG函数值，那么根据SGSG函数值的定义，该点能到达的所有点中，一定存在一个点的SGSG 函数值为 ai XOR xai XOR x那么我们就可以将该点上的棋子，移到一个SGSG函数值为ai XOR xai XOR x的点上去移完之后，原来每个棋子所在点的SGSG函数异或值就变为了 a1 XOR a2 XOR XOR a-1 XOR (ai XOR x) XOR ai+1XOR ana1 XOR a2 XOR XOR ai-1 XOR (ai XOR x) XOR ai+1 XOR an二 (a1 XOR a2 XOR XOR an) XOR x=x XOR x=0=(a
7、1 XOR a2 XOR XOR an) XOR x=x XOR x=01证毕证明 2：反证法，设将点uu上的棋子移动到点vv上后，每个棋子所在点的SGSG函数值仍然为00那就说明SG(u)=SG(v)SG(u)=SG(v),不符合SGSG函数的定义，不成立2 证毕所以做法是正确的。那么如何求出每个点的SGSG函数值呢？记忆化搜索就好啦每层记忆化搜索中，如果该点的SGSG函数值已经被计算出，那就直接返回该值。否则用一个setset记录每个点能到的所有点的SGSG 函数值集合，然后从00开始遍历，找到第一个setset里面没有的数，将该值记录在该点上并返回。时间复杂度最坏情况下，每个点都会被遍历
8、一次，时间复杂度为O(n)O(n)。对于每个点，我们会将其所能到达的所有点扔到一个set中。而每个点能到达的点的数量，取决于从该点出发的边的数量。所以总共我们会往set中插入mm次。但是对于每个set，我们至多只会往其中插入n - 1个数。所以对于set的总复杂度为O(mlogn)O(mlocn)o那么本题的总时间复杂度即为O(n+mlogn)O(n+mlogn)。C+C+代码include include include include include jsing namespace std;onst int N = 2005;onst int M = 6005;nt n, m, k;nt
9、hN, eM, neM, idx;/ 邻接表存图nt sgN;/存所有被计算过的点的SG函数值nt res;nline void add(int u, int v)/加边函数。从点u向点v连一条有向边e + idx = v;neidx = hu;hu = idx;nt SG(int u)if (sgu) return sgu;如果当前sgu不是-1,那么说明该点的SG函数值已经被计算过了，直接返回set S;/否则要建一个集合S,存该点能到的所有点的SG函数值for (int i = hu; i; i = nei) /遍历点u能到达的所有点S.insert(SG(ei); for (int i
10、 = 0; ; i + )if (!S.count(i) sgu = i;/计算该点的SG函数值，并放入集合S/从0开始枚举所有非负整数/如果该值没有在S中出现过/那么将该值记录在sgu中并返回return i;nt main()读入题目中N, M, Kfor (int i = 0; i m; i + ) / 读入 M 条边并建图 int u, v;add(u, v);memset(sg, -1, sizeof sg); /先将sg数组中的所有值初始化成-1,表示没有记录过 while (k - )/读入K个棋子所在的点int u;res A= SG(u);如果res不为0,那么输出win否则
11、输出losereturn 0;简单情况:所有堆的石子个数11设b=堆数+石子总数-1b=堆数+石子总数-1先手必胜= bb是奇数对于任何一个奇数，一定存在一个偶数后继对于任何一个偶数,所有后继必然是奇数又当b=1b=1时，有b=1(堆数)+1(石子总数)-1 = 1b=1 (堆数)+1(石子总数)-1 = 1则最终状态一定是奇数证明思路：奇数出发(自己)-能到偶数(对手)-必回奇数(自己)-剩1(自己)-自己赢奇数:堆数11 =合并两堆(堆数-1) b-偶数堆数=1,3=1,3 =取1石子(石子数-1)b-偶数即任何一个奇数状态都可以转移到某一个偶数状态偶数:堆数11 =合并两堆(堆数-1)
12、b-奇数取一子1该堆22 b-奇数2该堆=2=2 b-奇数该堆剩12.1总共堆数=1 = 1则奇对手赢2.2总共堆数11则奇对手一定在之后把这剩1的堆给合并假设剩两堆22数的堆+奇数个数的堆(b=2+b=2+奇-1+2=1+2=偶)拿完后1+1+奇奇对手合并两堆-最后只剩11堆偶数给偶对手(b=1+b=1+偶-1-1)一般情况:有堆的石子个数=1=1石子个数=1= 1的堆个数=aabb其他个数(1)(1)的堆个数+其他堆石子总数-1 -1f(a,b)=H|f(a-1,b)，从a中取1个 f(a,b-1)，从b中取1个 f(a,b-1),合并b中2个 f(a-2,b+3),合并a中2个(b 堆石
13、子数+2,堆数+1)f(a-1,b+1),合并a中1个b中1个(b堆石子数+1,a个数-1)f(a,b)=(f(a-1,b),从a中取1个 f(a,b-1),从b中取1个 f(a,b-1),合并b中2个 f(a-2,b+3),合并a中2个(b 堆石子数+2,堆数 +1)f(a-1,b+1),合 并a中1个b中1个(b堆石子数+1,a个数-1)#include #include #includeusing namespace std;const int N = 55, M = 50050;int fNM;int dp(int a, int b)int &v = fab;if (v != -1)
14、return v;/简单情况if (!a) return v = b % 2;/ 一般情况/上一次取完后b中只有1堆且只有1个石子b=1+1-1=1这堆并入a中 if (b = 1) return dp(a + 1,0);/有a从a中取1个if (a & !dp(a - 1, b) return v = 1;/有b从b中取1个or合并b中2个if (b & !dp(a, b - 1) return v = 1;/合并a中2个if (a = 2 & !dp(a - 2, b + (b ? 3 : 2) return v = 1;/合并a中1个b中1个if (a & b & !dp(a - 1,
15、b + 1) return v = 1;return v = 0;int main()memset(f, -1, sizeof f);int T;cin T;while (T -)int n;cin n;int a = 0, b = 0;for (int i = 0; i x;if (x = 1) a + ;/ b=0 时加1 堆+加x石子=0 + 1+x-1=x/ b!=0时加1堆+加x石子=原来的+x+1else b += b ? x + 1 : x;return 0;在研究过Nim游戏及各种变种之后，Orez又发现了一种全新的取石子游戏，这个游戏是这样的: 有n堆石子，将这n堆石子摆成一
16、排。游戏由两个人进行，两人轮流操作，每次操作者都可以从最左或最右的一堆中取出若干颗石子，可以将那一堆全部取掉，但不能不取，不能 操作的人就输了。Orez问：对于任意给出的一个初始局面，是否存在先手必胜策略。输入格式第一行为一个整数T,表示有T组测试数据。对于每组测试数据，第一行为一个整数n,表示有n堆石子，第二行为n个整数ai ,依次表示每堆石子的数目。输出格式对于每组测试数据仅输出一个整数0或1,占一行。其中1表示有先手必胜策略，0表示没有。数据范围1WTW10,1 WnW1000,1WaiW109输入样例：143 1 9 4输出样例：0假设当前ijij堆固定oi joleftijlefti
17、j表示我在左边放多少个石子先手必败leftijleftij必然存在且唯一唯一：反证：假设有两个取值L1L2L1L 2使得先手必败当左边先放L2L2并先手拿完后剩L1L1个给对手的局面时自己就不是必败了同理可以求一个rightijrightij表示我在右边放多少个石子先手必败最后答案：left2n=a1left2n=a1leftijleftij递推i j-1第堆（石子个数x）则我们希望求的是假设ij已经固定了，我们在左边放多少个可以使得？i j-1第堆是必败的定义：左边放LL时,Li j-1 必败右边放RR时,i j-1R必败情况1:R=xR=x i j-1xleftij=0leftij=0情况
18、2：xL且 xRx L且xR xi j-1xleftij=xleftij=x不管先手怎么取必然在取完后某一此后某一边剩0个石子，另一边剩yy个石子0 yWx0yWx0i j-1y此时由于 xL,xRxL,xR 0yWx0yWxWyL,yRyL,yRLR 则有 RxWLRxWLx-1 i j-1 x此时右边取xx左边取x-1x-1leftij=x-1leftij=x-1 时必败先手取右边首先先手一定不能把右边取RR假设先手把右边取RR后手把左边取完则先手必败如果先手把右边取到xRxRxR时，后手立即把左边取到比右边少11的x-1x-1 由于右边RR则右边xx最小取到11左边xx最小取到00则必然
19、会将右边取到RR（情况1）或者RR以下（情况2） -必败先手取左边如果先手把左边取到xRxR时,后手就把右边边取到x+1x+1 （情况3.1）如果先手把左边取到xRxRR右边R+1R+1后手保证左边比右边少一个（情况3）, 一旦左边或者右边有一个RLRL 则有L WxRLWxL+1L+1时,后手就把右边边取到LL后手永远保证左边比右边多11如果先手把左边取到LL时，后手就把右边取完，先手必败如果先手把左边或右边取到 LL,后手就保证左右两边一样多，先手必败后手保证左边比右边多一个（情况3.2）, 一旦左边或者右边有一个 LL且 xRx L且xRleftij=xleftij=x意味着只要xL且x
20、RxL且xR左边和右边取一样多就行4.1LRLR0 时先手取完后LL后手保证左右两边相同一旦先手把某一边个数取到（R,L（R,L后手保证左边比右边少一个（情况3.1）一旦先手把某一边个数取到R,L）R,L）后手保证右边比左边多一个一旦先手把某一边个数取到（,R）（,R）后手保证右边和左边一样多4.2RLRL时对称先手取完后RR后手保证左右两边相同一旦先手把某一边个数取到（L,R（L,R后手保证右边比左边少一个（情况3.2）一旦先手把某一边个数取到L,R）L,R）后手保证左边比右边多一个一旦先手把某一边个数取到（,L）（,L）后手保证右边和左边一样多#include#includeusing n
21、amespace std;const int N = 1010;int n;int aN;int lNN, rNN;int main()int T;cin T;while(T-)cin n;for (int i = 1; i ai;/长度for (int len = 1; len = n; len + )/左右端点i右端点jfor (int i = 1; i + len - 1 x x x/只要先手取哪一堆后手在另一堆取一样多的石子 则只要先手取得这堆有，后手取得另一堆也一定有， /直到先手取得那堆取完,后手把另一堆取完先手必败 if (len = 1) lij = rij = ai;else
22、int L = lij - 1, R = rij - 1, X = aj;/情况1if (R = X) lij = 0;/情况2情况4else if (X L & X L & X R) lij = X;/情况3.1情况4.1else if (L R) lij = X - 1;/情况3.2情况4.2else lij = X + 1;/与上述情况对称的四种情况L = li + 1j, R = ri + 1j, X = ai;if (L = X) rij = 0;else if (X L & X L & X R) rij = X; else if (R L) rij = X - 1;else rij = X + 1;return 0;!