[eJOI 2020] Dots and Boxes (Day2)

0
15011418730 LV 7 @ 2025-8-24 22:29:09
自动搬运

查看原文

来自洛谷，原作者为

Danno0v0
我们会再次见面的，相信我。再见。

搬运于2025-08-24 22:29:09，当前版本为作者最后更新于2021-11-17 15:38:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

~~是一道棋牌类问题但不是大%拟的问题，太棒了~~

题目中有一句非常重要的话：

满足每一个格子周围的四条边都有 0 条或 2 条未被连

这说明了什么呢，当然是说明了所有联通起来的（不被黑线隔开的）方块要么组成一条链，要么链首尾拼接组成一个环，不可能是树或者奇奇怪怪的东西。这个性质手推就很容易得到了。

那么我们的预处理就是把每一条链和每一个环的大小预处理出来。接下来为了方便做（原因后讲），我们把不同种类的图丢到两个数组里面。

接下来就是讨论最优策略了。

这里拿链来举例：

假设这里有一条没有被操作过的链：（图上的红边表示原有的边）

现在轮到先手（蓝色的边）来操作，很明显是一个格子都占不了的，所以只能随意地画一条边：

现在轮到后手（绿色的边）了。他就可以高高兴兴地靠着先手的边占掉这条链上所有格子。

然后这条链就算处理完了。接下来到下一条链时，由于后手的 combo 奖励，他这个时候是先对这条链进行操作的，所以——

他现在变成了先手，而之前的先手变成了现在的后手。而依据上面的推导，后手将会占完所有的格子，然后这里的后手就变成了先手，所以，两个人就交替地占着格子。然后注意到后手能得到多少收益取决于先手决定操作哪条链，而先手肯定会选大小最小的链让后手收益最小，所以，答案就是把所有连通块按从小到大排序然后两人交替取就是——

了吗？

我们来看这样一种情况，先手决定操作大小为 $3$ 的链，现在轮到后手了：

按照上面的推论，后手现在只能收掉大小为 $3$ 的链而把旁边大小为 $6$ 的链送给先手，所以后手特别不满意，于是他决定操作一下。

问题是操作在哪里呢？操作在大小为 $6$ 的链上是肯定不行的，（相当于下一步操作先手就可以把两条链都占了，抢占 $6$ 没占成，倒把 $3$ 给丢了）于是只能操作在 $3$ 上了（边上的数字表示画边的顺序）：

在画下第二条边的时候后手因为没有占格子所以停止了画边。现在轮到先手了。
1. 先手操作在 $3$ 上—，这个时候先手只好把后手留给他的两个格子占掉，然后面对 $6$ 的链当先手。
2. 先手直接操作在 $6$ 上，等于直接面对 $6$ 的链当先手。
所以此时无论先手怎么搞，都会在面对 $6$ 的时候当先手，这样，后手就能愉快地在 $6$ 的时候当后手啦。

对后手的这种战术做一个总结：也就是放弃两个属于自己的格子（在链上时）给先手，让面对下一条更大的链的时候先手依然是当先手。

（注 $^1$ ：在环上时需要放弃四个格子，就像这样：

可以证明没有方法在画下 $last$ 的时候只放弃三个或更小的格子，手推即可。

注 $^2$ ：如果一个链的大小等于 $2$ ，先手可以把线画在链的中心位置让后手不能放弃格子；如果大小等于 $1$ ，请问后手怎么执行放弃两个格子的战术。也就是只有链的大小大于 $2$ ，后手才可以放弃格子换取后手。

）

所以综上，对于每一个连通块：

先手只能操作一条线。

后手可以选择：
- 获取这个连通块内所有格子，然后把后手转让给先手。
- 获取这个连通块内格子数量 $-2$ （链） $-4$ （环），剩下的给先手。
这个直接 DP 就可以了。

哦对了，由于对于环和链，后手的第二种策略放弃格子数量是不同的，所以我们分开转移（所以要分开存）。然后因为不管后手怎么操作，后手能获得的格子数还是取决于先手选择的连通块，所以不管先手决定操作哪种连通块，一定都是选最小的。

code：（还是说一下 DP ： $dp_{i,j}$ 表示现在选到了第 $i$ 大的链和第 $j$ 大环时的并且两人采用最优策略的分数，并且现在轮到先手，然后倒推，一些细节放代码里了）
```
#include<bits/stdc++.h>
#define up 1
#define right 2
#define down 4
#define left 8
using namespace std;
int n,m,a[101][101],size_chain[1000001],size_loop[1000001],fi[1000001],nx[1000001],to[1000001],val[1000001],totm,fa[1000001],dp[101][101],num1,num2,cnt,A,T,tot;
bool vis[1000001],check;
bool cmp(int a,int b){
	return a>b;
}
void link(int a,int b){
	nx[++tot]=fi[a];
	fi[a]=tot;
	to[tot]=b;
} 
void dfs(int now,int fath){//丑陋找连通块 
	vis[now]=1;
	cnt++;
	for(int i=fi[now];i;i=nx[i]){
		int v=to[i];
		if(v==fath) continue;
		if(vis[v]) {
			check=1;
			continue;
		}
		dfs(v,now);
	}
}
int main()
{
	char s;
	cin>>n>>m;
	for(int i=0;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>s;
			a[i][j]+=((s-'0')*down);
			a[i+1][j]+=((s-'0')*up);
		} 
	}
	for(int i=1;i<=n;i++){
		for(int j=0;j<=m;j++){
			cin>>s;
			a[i][j]+=((s-'0')*right);
			a[i][j+1]+=((s-'0')*left);
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(!(a[i][j]&1)&&i-1>0) link(i*100+j,(i-1)*100+j);
			if(!(a[i][j]&2)&&j+1<=m) link(i*100+j,i*100+(j+1));
			if(!(a[i][j]&4)&&i+1<=n) link(i*100+j,(i+1)*100+j);
			if(!(a[i][j]&8)&&j-1>0) link(i*100+j,i*100+(j-1));
			if(a[i][j]==15) vis[i*100+j]=1;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(!vis[i*100+j]){
				cnt=0,check=0;
				dfs(i*100+j,0);
				if(!check) size_chain[++num1]=cnt;
				else size_loop[++num2]=cnt;
			}
		}
	}
	sort(size_chain+1,size_chain+num1+1,cmp);
	sort(size_loop+1,size_loop+num2+1,cmp);
	for(int i=0;i<=num1;i++){
		for(int j=0;j<=num2;j++){
			dp[i][j]=-0x7ffffff;
			if((!i)&&(!j)){
				dp[i][j]=0;
				continue;
			}
			if(i){
				if(size_chain[i]>=3) dp[i][j]=-max(size_chain[i]+dp[i-1][j],size_chain[i]-4-dp[i-1][j]);
				else dp[i][j]=-size_chain[i]-dp[i-1][j];
				/* 
				第一个问题：为什么是max前是-和转移方程的含义
				这是从经过上一次后手操作后的分数转移的，而后手的收益相当于先手的负收益所以要加-
				第一个转移的含义就是：把没有选这条链时的分数加上选了这条链的收益就是后手收益
				第二个转移的含义就是：这条链的大小减去放弃格子失去的收益再减去没有选这条链时的分数
				——为什么是减去没选时的分数？因为数组里存的是对于先手来说的收益，而进行放弃操作时，在下一个（别忘了我们是倒推）联通块时后手仍然是后手不会进行先后交换，所以下一个连通块时的操作时，需要从下一个连通块时后手分数进行转移，而后手分数就是先手分数的相反数 
				第二个问题：为什么都是-了，用max，不应该用min保证这个人收益最大吗？ 
				后手用的是最优策略啊喂，假如用min，就相当于让后手用最劣策略来保证先手的最优策略啊。 
				第三个问题：对于第二个转移，为什么-4而不是-2？
				你转出两个格子给另一个人，那么你不仅损失了应得的两个格子，还让对手得到了本不应得的两个格子；加起来就是4个。 
				*/ 
			}
			if(j){
				dp[i][j]=max(dp[i][j],-max(size_loop[j]+dp[i][j-1],size_loop[j]-8-dp[i][j-1]));
			}
			/*
			环的转移同理。 
			*/ 
		}
	}
	cout<<dp[num1][num2];
}
```