博弈补充练习
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";
}