请善用目录导航（大纲）公平组合游戏ICG若—个游戏满足:由两名玩家交替行动;在游戏进程的任意时刻，可以执行的合法行动与轮到哪名玩家无关;不能行动的玩家判负;则称该游戏为一个公平组合游戏。NIM博弈属于公平组合游戏，但城建的棋类游戏，比如围棋，就不是公平组合游戏。因为围棋交

题意简述有\(n\)堆石子，第\(i\)堆石子有\(a_i\)个。两个人博弈，每次可以选择以下两种操作之一：拿走石子数目最大的那堆石子（若有多个只拿一堆）在每堆石子中都拿走一个石子无法操作的人胜利，求谁必胜（先手First后手Second）\(n\le10^5,a_i\le10^9\)。分析操作二不会改变

[SBCOI2020]时光的流逝题目背景时间一分一秒的过着，伴随着雪一同消融在了这个冬天，或许，要是时光能停留在这一刻，该有多好啊。......“这是...我在这个小镇的最后一个冬天了吧。”“嗯，你可不能这辈子都呆在这个小镇吧。外面的世界很大呢，很大很大...”“唔...外面的世界...突然

Link奇偶判定性CF1919A发现交换相当于两人共用一个大小为\(a+b\)的钱包，判断奇偶性即可。Submissionpb的游戏1必败态：\(N=1\)。发现若\(N\)是奇数，则其只能分为奇数和一个偶数，则后手可以选择奇数必胜。后手可以接着分割为两个奇数，先手必败。反之先手分为两个奇数，后手

Nim游戏\(n=2\)的时候可以用一个巧妙的方法证明：如果两堆石子一样多，则后手可以通过在另一堆上一直模仿先手的行为获胜；如果两堆石子不一样多，则先手可以在第一次取时把两堆变成一样多。结论中出现异或的原因（异或的定义为）：\[a\oplus0=a\]\[a\oplusa=0\]\[a\oplusb=

博弈论Nim游戏对于\(n=2\)，\(a_1=a_2\)，后手可以“模仿”先手，使得后手必胜。对于\(a_1\nea_2\)，先手可以让自己进入“模仿期”，使得先手必胜。结论：若\(\oplusa_i=0\)，先手必败，否则必胜。很神奇的东西，证明需要群论知识。发现石子的合并满足上面四条性质，所以石子的合并就是异

博弈论Nim游戏Problem1有\(n\)堆石子，第\(i\)堆中有\(a_i\)枚石子，每次可以挑一堆石子，取走至少一枚石子，不能操作者输，问先手必胜还是后手必胜。后手可以一直模仿先手的行动，故当条件一致时，即所有\(a_i\)的异或和为\(0\)，则后手必胜；否则先手必胜（先手可以将石子转化为条

传送门[AGC014D]BlackandWhiteTree给出一颗\(N\)个节点组成的树，每个节点都可以被染成白色或者黑色；有高桥（先手）和青木（后手）两个人————高桥可以把任意一个点染成白色，青木则可以把任意一个点染成黑色，每个点只可染色一次。重复上述操作直到所有点都被染色后，只执行一次执行

题目链接：https://codeforces.com/contest/1942/problem/E题目大意：输入一个\(l\)和一个\(n\)，其中\((1\leql\leq10^6,2n<=l)\)，表示有\(l\)个不同的空位（分别是\([1,l]\)）和\(2n\)头完全一样的牛。Alice和Bob分别有\(n\)头牛，并且他们的牛是间隔排列的。每一次

题目跳转思路：这道题可能跟博弈论有一点关系，没有学习过博弈论做起来应该问题也不大。思考一个问题，先手必胜的前提是什么？有关更多的内容可以前往：浅谈有向无环图先手必胜的前提是，在任何一种局面下，先手都有至少一种操作可以使后手处于必败的局面。若先手进行任何操作后，后手都可以

Description非负整数\(x,y\)的最大公约数记为\(\gcd(x,y)\)，规定\(\gcd(x,0)=\gcd(0,x)=x\)。黑板上写了\(N\)个整数\(A_1,A_2,...,A_N\)，这\(N\)个数的最大公约数是\(1\)。Takahashi和Aoki在玩游戏，有一个变量\(G\)初值为\(0\)，他们轮流进行以下操作：从黑板上选择

P4311士兵占领考虑先把棋盘放满，判掉无解，并把问题转化为拿走最多的棋子。这个问题就一眼最大流了，对于行和列分别建M,N个节点，源点向行节点连流量为该行最多可删个数的边，列节点向汇点连该列最多可删个数的边，对于每个可放士兵的(i,j),从行节点i向列节点j连一条流量为1的边，跑最大流

平等博弈问题的基本模型：一个状态DAG上的移动。解决博弈论的重要方法：打表。博弈论问题一般有一些方向：观察先手怎么做，后手怎么做。一般是一些显然的贪心策略。结合SG函数。结合已有模型。FergusonGame两堆石子，每次可以清空一堆，拆另一堆为两堆，无法操作者输。分

一些用处不多的姿势：perfectinformation:双方做决策时知道当前局面处于什么状态以及可能向什么状态转移。（如围棋你知道当前局面以及可以知道对手下一步可以走的位置）complete information;博弈双方知道各自的目的。（如狼人杀显然不是，你不知道对方的身份以及对方取得成功的条件）im

首先，我们需要了解\(Nim\)游戏是什么东西。\(Nim\)游戏指：两个人，有\(n\)堆数，每堆有\(a_i\)个，每次可以且仅可以取一堆中的若干个数，求问先手有没有必胜策略（当然两个人都足够聪明）。首先，先研究显然的必胜策略。比如，我们要得到\(0\)这个数，那么当你取完时还剩下\(0\)个。然

浅谈Nim游戏首先，我们需要了解\(Nim\)游戏是什么东西。\(Nim\)游戏指：两个人，有\(n\)堆数，每堆有\(a_i\)个，每次可以且仅可以取一堆中的若干个数，求问先手有没有必胜策略（当然两个人都足够聪明）。首先，先研究显然的必胜策略。比如，我们要得到\(0\)这个数，那么当你取完时还

终于从学考中解脱出来了，做题纪要回归！11月下半个月发生的事情：考了个NOIP，游记在这，然后全力备战学考了，所以半个月没做题。本文大部分题的题单To-doList#2。题单的第一个题在上一篇做题纪要的最后。目录2023.12.10P9353[JOI2023Final]ModernMachine2023.12.11GYM102896F

2023/12/1博弈论巴什博弈（只有一堆n个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取m个。最后取光者得胜。）P/N分析N为先手必胜态，P为先手必败态那么首先对于石子为0时，该状态无路可走，所以先手必败，P点对于1~3，可以走到0点，让后手的状态为P，既然对手必败了，那么我们先手

题解建出原图的圆方树。由于原图无重边，不妨把桥看作二元环建树，这样圆点只与方点直接相连。圆方树定某一圆点为根后，若点\(u\)是圆点，定义点\(u\)的子仙人掌为点\(u\)子树中的圆点在原图的导出子图，定义该子仙人掌的根为点\(u\)；若点\(u\)是方点，定义点\(u\)的子仙人掌为点

【笔记】博弈论0基本概念&性质0.1博弈论1SG函数ps.通过SG函数来理解三个基本模型，也是不错的选择。1.2定义\(\text{SG}(x)=\text{mex}\{\text{SG}(y_i)\}\)（其中\(y_i\)为\(x\)的后继状态）1.3SG定理由\(n\)个博弈图组成的游戏，设起点（即每个连通分量内入

NOIP2023模拟3联测24-博弈树目录NOIP2023模拟3联测24-博弈树题目大意思路code题目大意\(Alice\)和\(Bob\)又开始玩游戏了：给定一颗\(n\)个节点的树，\(Alice\)和\(Bob\)随机选择一个节点作为起点放上棋子，由Alice先手。轮到一方后可以将这颗棋子移动到树上任意一点，每次

ABC209EShiritori题解原题：洛谷AT_abc209_e分析博弈，可重复选，一眼图论，将每个单词的前三个字符向后三个字符连边，并用后三个字符代表这个单词。看一下样例。5eaaaabaa12eaaaacaa13daaaaaaa45eaaaadaa14daaaafaa46我们得到的有向图：当一方说完

首先偶数是可以忽略的，因为拿了不影响奇偶性，并且序列中只有偶数或没有数均为先手必败，所以两人拿多少也都没有关系。考虑奇数的个数，如果有奇数个奇数，先手直接拿完获得胜利。否则先手可以先拿奇数个奇数，剩下仍然有奇数个奇数，而后手只能拿偶数个奇数，这就保证了下一轮的奇数个数变成

C-NotEqual285求长度为n，两两不同，且满足\(1\lea_i\lec_i\)的数组的数量数组c排序，答案就是\(\prod\limits_i(c_i-(i-1))\)，其中\(i-1\)个位置被前面占了D-Collision686给定一棵树，q次询问，一个人从u走向v，另一个人从v走向u，同时同速。问两人在点上还是在边上

题目大意有\(n\)个杯子，第\(i\)个杯子里装有\(W_i\)升水，且有\(n\)对正整数\(l_i,r_i\)。Yuri和Muri两人在玩一个游戏：两人轮流进行操作，最先不能进行操作者输。一次操作定义为：操作者选择一个杯子\(i\)，从中喝掉\(x_i\)升水。对于两个人，都要满足\(x_i\in[l_i,\min(r_