博弈补充练习
Nim or not Nim
类似于 NIM 游戏，有 \(n\) 堆石子，不过每个回合玩家可以从某个堆中删除任意数量的对象，也可以将堆分成两个较小的石堆，拿走最后一个石子的人获胜。
还是一个裸的求 sg 函数的题，但由于范围过大，肯定不能每次来求sg函数值。
于是需要打表。
发现当 \(x % 4 == 0\) 时，sg(x) = x - 1，当 \(x % 4 == 3\) 时，sg(x) = x + 1，其余情况下，sg(x) = x。
于是就做完了。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int getsg(int x){
if(x % 4 == 0)return x - 1;
else if(x % 4 == 3)return x + 1;
return x;
}
int main(){
int T;
scanf("%d",&T);
while(T--){
int a,n,ans = 0;
scanf("%d",&n);
for(int i = 0; i < n; i++){
scanf("%d",&a);
ans = ans ^ getsg(a);
}
if(ans == 0)printf("Bob\n");
else printf("Alice\n");
}
return 0;
}
[AGC017D] Game on Tree
有一棵 \(N\) 个节点的树，节点标号为 \(1,2,?,N\)，边用 \((x_i,y_i)\)表示。 Alice 和 Bob 在这棵树上玩一个游戏，Alice先手，两人轮流操作：
选择一条树上存在的边，把它断开使树变成两个连通块。然后把不包含 \(1\) 号点的联通块删除
当一个玩家不能操作时输，你需要算出：假如两人都按最优策略操作，谁将获胜。
样例1：
5
1 2
2 3
2 4
4 5
如图：
首先注意每棵树默认根节点为 \(1\)，就不需要傻傻地统计点的度数来找根了。。。。
这个题也算是 \(NIM\) 游戏的翻版，区别就是将模型转换到图上了。
对于一个存在分岔的节点，可以类比 \(NIM\) 游戏中通过异或将多组游戏合并为一个等价的游戏的结果。如图中的节点 \(2\)，分别断开 \(2-3\) 和 \(2-4\) 两条边，就相当于拆成了两个子游戏，将两个游戏的结果异或起来就行了。
类似上述思路，递归处理整个图即可。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e5;
int n;
vector<int> g[MAXN + 5];
int getsg(int u,int fa){
int ans = 0;
for(int i = 0; i < g[u].size(); i++){
int v = g[u][i];
if(v == fa)continue;
int get = getsg(v,u);
ans ^= (get + 1);//加上删去的边
}
return ans;
}
int main(){
scanf("%d",&n);
for(int i = 1; i < n; i++){
int u,v;
scanf("%d%d",&u,&v);
g[u].push_back(v);
g[v].push_back(u);
}
int ans = 0;
ans ^= (getsg(1,1));
if(ans)cout << "Alice";
else cout << "Bob";
}
P2964 [USACO09NOV]A Coin Game S
小 A 和小 B 在玩游戏。
初始时，有 \(n\) 个硬币被摆成了一行，从左至右第 \(i\) 个硬币的价值为 \(c_i\)。
游戏的规则是，两人交替从这堆硬币的左侧连续取出若干硬币，然后将取出的硬币的价值累加至自己获得的累计价值中。若对方上次操作取出了 \(k\) 个硬币，那么本次自己最多取出 \(k \times 2\) 个硬币。当没有硬币可取时，游戏结束。
游戏开始时，由小 A 先动手取硬币，最多取出 \(2\) 个硬币。
请求出当双方都尽可能使自己的累计价值最大的情况下，小 A 能获得的累计价值最大是多少。
一道博弈\(dp\)的题，刚接触这类题好像总是不太好下手。因为不明白该怎么转移才能保证“双方都采用最优策略”。
现在看来，陷入这种思维陷阱的原因就是总是站在你所要求得答案的玩家的角度进行思考，又因为两个玩家的操作是交错的，如此就造成了局限性，使你在转移的时候无法顾及另一方也满足他的最优策略。
解决方法就是不要只站在一个人的角度思考整盘游戏，应站在当前进行操作的人的位置思考整个游戏。后文还会详细解释这个思路。
同时，博弈\(dp\)类的题目常常会采用 逆向\(dp\) 的思维方式，这个题就是一个例子。
思考题目，感觉 \(dp\) 过程中描述状态的重要的两个因子就是：
- 当前最多能拿的硬币数量。
- 剩余的硬币序列的最前面一个硬币的下标是从哪里开始的。
定义状态为 \(dp[i][j]\) 表示当 \(i\) 以前所有硬币都拿完时，此时最多能拿多少个硬币所能获得的最大价值。
这个思维就是上文所提到的站在游戏双方的角度进行思考。如果不是这样，那么 \(dp\) 维度中就会引入当前游戏决策者这一维，十分不利于构建转移方程，也就使得我们陷入了上文提到的思维陷阱。
然而现在似乎出现了个问题，假设我们从前往后进行 \(dp\)，过程中每个人每一步所拿的硬币数量对于正在进行 \(dp\) 的我们是未知的，小 A 就不一定是拿走最后那个硬币的人，那么又怎么才能确定小 A 所获得的最大价值对应哪个 \(dp\) 状态呢？
故这里就要采用逆向\(dp\)。我们不思考每个人从前往后拿硬币所能得到的最大价值，转而思考每个人从后往前放置等价值硬币所最多能放置的最大价值。这需要稍微修改一下 \(dp\) 状态。首先将原硬币序列逆向，定义 \(dp[i][j]\) 表示前 \(i\) 个硬币被放置，下一步操作最多能放置 \(j\) 个，即这次操作最多能放置 \(2 * j\) 个硬币时所能取得的最大价值。由于已经将硬币序列反向了，就可以直接正着 \(dp\) 过去了，这也符合刚才的思路。如此就能保证最后的答案就在 \(dp[n][2]\) 这个状态中。
下面思考怎么转移状态。
首先记录一个硬币序列的前缀和 \(sum[i]\)。可以确定的是，每次放置硬币的最大数量不超过 \(n\)。当前最多放置 \(2 * j\) 个硬币。
因此可以直接枚举一个范围在 \(1~2 * j\) 的 \(k\)。又因为我们将硬币序列反向后 \(dp\)，就相当于也把操作序列反向了。于是存在：
又引入了一个 \(k\)，就相当于有三维了，时间复杂度为 \(O(n^3)\)。怎么优化呢。
首先 \(i\) \(j\) 这两维肯定是要枚举的，考虑优化 \(k\) 这一维。
\(dp[i][j?1]\) 是枚举 \(k\) 从等于 \(1\) 到等于 \(2×(j?1)\) ，在 \(2×(j?1)\) 个 \(sum[i]?dp[i?k][k]\) 中取一个 \(max\) 值。
\(dp[i][j]\) 是枚举 \(k\) 从等于 \(1\) 到等于 \(2×j\) ，在 \(2×j\) 个 \(sum[i]?dp[i?k][k]\) 中取一个 \(max\) 值。
所以可知 \(dp[i][j]\) 是严格包含 \(dp[i][j?1]\) 的，我们只需要在 \(dp[i][j?1]\) 的基础上继续枚举 \(k=2×j?1\) 和 \(k=2×j\) 这两种状态即可。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e3;
int n,a[MAXN + 5],sum[MAXN + 5],dp[MAXN + 5][MAXN + 5];
int main(){
scanf("%d",&n);
for(int i = 1; i <= n; i++){
scanf("%d",&a[i]);
}
for(int i = n; i >= 1; i--){
sum[n - i + 1] = sum[n - i] + a[i];
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
int k = 2 * j - 1;
dp[i][j] = dp[i][j - 1];
if(k <= i)dp[i][j] = max(dp[i][j],sum[i] - dp[i - k][k]);
if(k + 1 <= i)dp[i][j] = max(dp[i][j],sum[i] - dp[i - k - 1][k + 1]);
}
}
cout << dp[n][1];
}
Varacious Steve
Steve 和他的一个朋友在玩游戏,游戏开始前，盒子里有 \(n\) 个甜甜圈，两个人轮流从盒子里抓甜甜圈，每次至少抓 \(1\) 个，最多抓 \(m\) 个。
最后一次将当盒子的甜甜圈抓完的人是这一轮游戏胜利者，他可以将所有抓到的甜甜圈吃完，另外一个人是这轮的失败者，他抓到的所有甜甜圈要重新放到盒子里。
下一轮游戏由上一轮的失败者开始抓，游戏继续。直到若干轮后，所有的甜甜圈被吃完，游戏结束。
游戏的目标是吃到尽量多的甜甜圈。游戏最开始，由Steve先抓，两个人均采用最优策略，请问Steve最多可以吃到多少甜甜圈。
也是一道博弈 \(dp\) 呢，只不过用了记搜便于转移罢了。
分析怎样描述 \(dp\) 状态，有如下因子：
- 当前回合一共有多少个甜甜圈供游戏。
- 该回合决策者已经拿了多少个甜甜圈。
- 上一回合的决策者已经拿了多少个甜甜圈。
于是构建三维 \(dp[i][j][k]\)，每一维描述从上到下的三个因子之一。（虽然代码中没这么写）同样的，这也是站在每个操作者的角度进行 \(dp\)。
具体细节见代码注释。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e2;
int s[MAXN + 5][MAXN + 5][MAXN + 5],n,m,T;//s就是dp数组
int get(int tot,int l,int r){//分别对应三维状态，l为当前决策者拿了多少个甜甜圈
if(tot == 0)return 0;
if(s[tot][l][r])return s[tot][l][r];
int ans = 0;
for(int i = 1; i <= min(m,tot - l - r); i++){
if(tot - l - r - i == 0)ans = max(ans,tot - get(r,0,0));//如果拿完了，就新开一把游戏
else ans = max(ans,tot - get(tot,r,l + i));//没拿完的话就继续
}
return s[tot][l][r] = ans;
}
int main(){
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
memset(s,0,sizeof s);
int ans;
ans = get(n,0,0);
cout << ans << "\n";
}
}
Play Game
Alice 和 Bob 正在玩游戏。有两堆卡片。每堆牌有 \(N\) 张牌，每张牌都有一个分数。他们轮流从两堆中捡起最上面或最下面的牌，这张牌的分数将添加到他的总分中。Alice 和 Bob 都足够聪明，他们会捡起牌来获得尽可能多的分数。你知道 Alice 如果先拿起来能得到多少分数吗？
分析 \(dp\) 状态组成因子：
- 牌堆1被拿走若干张牌后当前的左端点 \(l1\) 和右端点 \(r1\)
- 牌堆2被拿走若干张牌后当前的左端点 \(l2\) 和右端点 \(r2\)
四维的状态，仍采用记忆化搜索。对每一堆牌记录一个前缀和 \(sum\)，便于转移时快速查找区间和
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 20;
int sum1[MAXN + 5],sum2[MAXN + 5],dp[MAXN + 5][MAXN + 5][MAXN + 5][MAXN + 5],n,a[MAXN + 5],b[MAXN + 5],T;
int dfs(int l1,int r1,int l2,int r2){
bool emp1 = l1 > r1,emp2 = l2 > r2;
if(emp1 && emp2)return 0;
if(dp[l1][r1][l2][r2] != -1)return dp[l1][r1][l2][r2];
int ans = 0;
if(!emp1){//假如牌堆1没被拿空
ans = max(ans,sum1[r1] - sum1[l1 - 1] + sum2[r2] - sum2[l2 - 1] - dfs(l1 + 1,r1,l2,r2));//假如拿牌堆1最下面的一张
ans = max(ans,sum1[r1] - sum1[l1 - 1] + sum2[r2] - sum2[l2 - 1] - dfs(l1,r1 - 1,l2,r2));//假如拿牌堆1最上面的一张
}
if(!emp2){//假如牌堆2没被拿空
ans = max(ans,sum1[r1] - sum1[l1 - 1] + sum2[r2] - sum2[l2 - 1] - dfs(l1,r1,l2 + 1,r2));//假如拿牌堆2最下面的一张
ans = max(ans,sum1[r1] - sum1[l1 - 1] + sum2[r2] - sum2[l2 - 1] - dfs(l1,r1,l2,r2 - 1));//假如拿牌堆2最上面的一张
}
return dp[l1][r1][l2][r2] = ans;
}
int main(){
scanf("%d",&T);
while(T--){
memset(dp,-1,sizeof dp);
scanf("%d",&n);
for(int i = 1; i <= n; i++){
scanf("%d",&a[i]);
sum1[i] = sum1[i - 1] + a[i];
}
for(int i = 1; i <= n; i++){
scanf("%d",&b[i]);
sum2[i] = sum2[i - 1] + b[i];
}
int ans = dfs(1,n,1,n);
cout << ans << "\n";;
}
}
Moving Pebbles（QWQ）
给你 \(N\) 堆石头，两个人玩游戏. 每次任选一堆，首先拿掉至少一个石头，然后移动任意个石子到任意堆中。谁不能拿石子了，谁就输了。请求出哪个玩家存在必胜策略。
不妨先思考一下对于先手来说的必败态。在这样的博弈问题中，一般存在一个情形，使得后手能够完全模仿先手的操作，是一个必败态。拿到这个题里面来看，假如当前石堆为 \(n\)，且石堆可以被分成 \(x\) 对大小相等的石堆对，那么就是一个必败态。
对于其他状态，先手总可以把它们转化为一个必败态，对先手来说这就是一个必胜态。
接下来考虑如何证明必败态和必胜态之间可以相互转化。
假如现在有 \(n\) 堆石子，为一个必败态。对 \(i\) 这堆石子进行操作，它有 \(A_i\) 个石子。显然随便拿石子，就可以打破以前两两相对的状态。
假如现在为一个必胜态，所有石堆按从小到大排序。
如果 \(n\) 为奇数，需进行操作，将 \(A_n\) 的石子全部分配出去，使得 \(A_1=A_2\) \(A_3=A_4........\)那么需要操作的石子为 \((A_2-A_1) + (A_4-A_3) + (A_6 - A_5) + ... + (A_{n-1} - A_{n - 2}) <= A_2 - A_1 + A_4 - A_2 + A_6 - A_4 + ... + A_{n-1} - A_{n - 3} = A_{n-1} - A_1 < A_n\)，所以可以完成操作。
如果 \(n\) 为偶数，类比上式，仍可分配下去。得证。
然后直接看初状态是必胜态还是必败态就行了。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5;
template<class T>inline void read(T &a){
char c;while(!isdigit(c=getchar()));
for(a=c-'0';isdigit(c=getchar());a=a*10+c-'0');
}
int n,m;
map<int,bool> tag;
int main(){
while(~scanf("%d",&n)){
tag.clear();
int cnt = 0;
for(int i = 1; i <= n; i++){
read(m);
if(tag[m])cnt--,tag[m] = 0;
else ++cnt,tag[m] = 1;
}
if(cnt)cout << "first player\n";
else cout << "second player\n";;
}
}
P5932 [POI1999]多边形之战
游戏在一个有 \(n\) 个顶点的凸多边形上进行，这个凸多边形的 \(n-3\) 条对角线将多边形分成 \(n-2\) 个三角形，这 \(n-3\) 条对角线在多边形的顶点相交。
三角形中的一个被染成黑色，其余是白色。双方轮流进行游戏，当轮到一方时，他必须沿着画好的对角线，从多边形上切下一个三角形。切下黑色三角形的一方获胜。
- 注：如果连接一个多边形中任意两点的线段都完全包含于这个多边形，则称这个多边形为凸多边形。
遇到乍看来没有思路的题，画图辅助思考不失为一种不错的方法。
如图，不难发现，如果要割出一个三角形，就必须把它三个方向的三角形全部删去。那么可以知道，在这个游戏中的必胜态是黑色三角形只有一边存在三角形。这时只需切一刀就可以割下这个三角形。
假设三角形的三边所对应的三个方向分别有 \(x\) \(y\) \(z\) 个三角形，只需使其中两个元素为 \(0\) 即可赢得游戏。
又由题目知双方都会采用最优策略，所以肯定不存在黑色三角形的一边存在大量没有被割掉的三角形。理想状况是黑色三角形只有一边存在一个三角形。
所以先手是否有必胜策略就和 \(x + y + z\) 的奇偶性有关了。若和模 \(2\) 为 \(1\)，则先手按最优策略走，就可以实现上文所提到的理想状况，一刀切下！此时就有必胜策略。若模 \(2\) 为 \(0\)，则后手存在必胜策略。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5;
int n,cnt;
bool vis[MAXN + 5];
map<pair<int,int>,int> m;
vector<int> edge[MAXN + 5];
struct TRI{
int a,b,c;
}tri[MAXN + 5];
int main(){
int a,b,c;
scanf("%d%d%d%d",&n,&a,&b,&c);
if(a > b)swap(a,b);
if(a > c)swap(a,c);
if(b > c)swap(b,c);
int x = 0,y = 0,z = 0;
for(int i = 1; i <= n - 3; i++){
int p,q,r;
scanf("%d%d%d",&p,&q,&r);
if(p >= a && p <= b && q >= a && q <= b && r >=a && r <= b)x++;
else if(p >= b && p <= c && q >= b && q <= c && r >= b && r <= c)y++;
else z++;
}
int k = x + y + z;
int j = (x == 0) + (y == 0) + (z == 0);
if(j >= 2)cout << "TAK";
else if(k & 1)cout << "TAK";
else cout << "NIE";
}