专栏文章

CF2005E2 Subtangle Game (Hard Version) 题解

llinjunye
CF2005E2题解参与者 1已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mip8pxko
此快照首次捕获于
2025/12/03 07:59
3 个月前
此快照最后确认于
2025/12/03 07:59
3 个月前
查看原文
不错的 DP 题。
我们先约定一下：以 (i,j)(i,j) 为左上角的子矩阵，表示以 (i,j)(i,j)，(i,m)(i,m)，(n,j)(n,j)，(n,m)(n,m) 为四个端点的子矩阵；矩阵均指二维数组 bb。
首先我们可以列出 dpi,j,kdp_{i,j,k} 表示以 (i,j)(i,j) 为左上角的子矩阵，且接下来取 aka_k，先手是否必胜。我们约定 11 表示必胜，00 表示必败。
然后先考虑朴素转移：
首先可以发现如果以 (i,j)(i,j) 为左上角的矩阵的子矩阵可以成功（当然当前取的数相同，即 kk 相同）的情况下，dpi,j,k=1dp_{i,j,k}=1。
好绕啊！这里有一个形式化一点的表达：
如果存在 x,yx,y 满足 x≥ix\ge i 且 y≥jy\ge j，dpx,y,k=1dp_{x,y,k}=1，则 dpi,j,k=1dp_{i,j,k}=1。这里可以自行画图理解。
然后考虑特殊情况，bi,j=akb_{i,j}=a_k：
首先容易想到的是从边界出发：
  • 如果 i=ni=n，那么取完后后手就没有地方可以操作了，先手必胜。
  • 如果 j=mj=m，那么取完后后手就没有地方可以操作了，先手必胜。
  • 如果 k=lk=l，那么先手取完就没了。
所以如果 i=ni=n 或 j=mj=m 或 k=lk=l，先手必胜。
然后有一个简单转移：考虑取这里，那么后手拿到的是以 (i+1,j+1)(i+1,j+1) 为左上角的子矩阵。那么如果 dpi+1,j+1,k+1=0dp_{i+1,j+1,k+1}=0，先手显然必胜。
这样子就完成 DP 的转移了，复杂度 O(nml)O(nml)，可以通过 E1。
然后考虑优化。
提示：考虑分析一下样例，或者再看一眼 DP 的朴素转移，有没有什么规律？
我们可以从 DP 的朴素转移里发现两个性质：
首先，如果 dpi,j,k=1dp_{i,j,k}=1，则 dpi,j−1,k=1dp_{i,j-1,k}=1，这一点显然（再看看朴素转移）。
同理，如果 dpi,j,k=1dp_{i,j,k}=1，则 dpi−1,j,k=1dp_{i-1,j,k}=1。
从第一个性质推导，我们惊喜的发现好像可以压维，也就是把 jj 那一维压掉！
故我们定义 fi,kf_{i,k} 表示能使 dpi,j,k=1dp_{i,j,k}=1 的最大的 jj。
考虑优化转移（如果 bi,j=akb_{i,j}=a_k，dpi+1,j+1,k+1=0dp_{i+1,j+1,k+1}=0，dpi,j,k=1dp_{i,j,k}=1）：
提示：当 jj 变大时，dpi+1,j+1,k+1=0dp_{i+1,j+1,k+1}=0 的可能性是怎样的？
发现如果 bi,j=akb_{i,j}=a_k，那么 jj 越大转移成功（即先手获胜）的概率越高。这是一个贪心的想法，证明显然（注意到若 dpi,j,k=1dp_{i,j,k}=1，则 dpi,j−1,k=1dp_{i,j-1,k}=1，而 dpi,j+1,kdp_{i,j+1,k} 不一定等于 11）。
那么，我们肯定取最大的 jj，满足 bi,j=akb_{i,j}=a_k。
于是我们定义 mxi,kmx_{i,k} 表示使 bi,j=akb_{i,j}=a_k 的最大的 jj。我们记 mxi,k=0mx_{i,k}=0 表示不存在 bi,j=akb_{i,j}=a_k。
那么这个转移为：若 mxi,k≠0mx_{i,k}\ne 0 且 mxi,k≥fi+1,k+1mx_{i,k}\ge f_{i+1,k+1}，则 fi,k=mxi,kf_{i,k}=mx_{i,k}。
这一点可能有点难，那么讲一下思考过程：
首先我们想让 dpi,mxi,k,k=1dp_{i,mx_{i,k},k}=1，所以 dpi+1,mxi,k+1,k+1=0dp_{i+1,mx_{i,k}+1,k+1}=0，即 fi+1,k+1<mxi,k+1f_{i+1,k+1}<mx_{i,k}+1，即 fi+1,k+1≤mxi,kf_{i+1,k+1}\le mx_{i,k}。
所以若 mxi,k≠0mx_{i,k}\ne 0 且 mxi,k≥fi+1,k+1mx_{i,k}\ge f_{i+1,k+1}，则 fi,k=mxi,kf_{i,k}=mx_{i,k}。
然后考虑 i,j,ki,j,k 的影响：
首先 j=mj=m 是好写的，显然 fi+1,k+1≤mf_{i+1,k+1}\le m，所以可以并为上面的转移。
然后 i=ni=n 和 k=lk=l 也简单，fi,k=mxi,kf_{i,k}=mx_{i,k}，这里的转移不难。
最后是朴素转移：
首先 y≥jy\ge j 的情况不用推了，前面定义的时候就用过了。
然后是 x≥ix\ge i 的部分：我们看到第二个性质，如果 dpi,j,k=1dp_{i,j,k}=1，则 dpi−1,j,k=1dp_{i-1,j,k}=1。所以 fi,k=fi+1,kf_{i,k}=f_{i+1,k}。
最后对上述所有值取最大值即可。
然后呢？然后就没了。接下来你只需要写一下求 mxmx 就可以了。
最后考虑输出：如果先手必胜，那么 dpi,j,1=1dp_{i,j,1}=1。然后根据上面的两个性质，不难推出：如果 f1,1≠0f_{1,1}\ne 0，那么先手必胜。
时间复杂度：O(nm+nl)O(nm+nl)。
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1510;
const int mod=998244353;
const int INF=0x3f3f3f3f3f3f3f3f;
int l,n,m;
int a[N];
int b[N][N];
int f[N][N];
int mx[N][N];
int T[N*N];
void solve(){
	cin>>l>>n>>m;
	for(int i=1;i<=l;i++)cin>>a[i];
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin>>b[i][j];
	for(int i=1;i<=n;i++){//这里开桶记录，如果用map复杂度会多一个log
		for(int j=1;j<=m;j++)T[b[i][j]]=j;
		for(int j=1;j<=l;j++)mx[i][j]=T[a[j]];
		for(int j=1;j<=m;j++)T[b[i][j]]=0;
	}
	for(int k=l;k>=1;k--){
		for(int i=n;i>=1;i--){
			f[i][k]=max(f[i][k],f[i+1][k]);
			if(mx[i][k]>0&&f[i+1][k+1]<=mx[i][k])f[i][k]=max(f[i][k],mx[i][k]);
			if(mx[i][k]>0&&(i==n||k==l))f[i][k]=max(f[i][k],mx[i][k]);
		}
	}
	int fl=0;
    if(f[1][1]>0)fl=1;
	if(!fl)cout<<"N\n";
	else cout<<"T\n";
	for(int i=1;i<=n;i++)
		for(int j=1;j<=l;j++)
			f[i][j]=mx[i][j]=0;
	return;
}
signed main(){
	ios::sync_with_stdio(0);
	cout.tie(0);
	cin.tie(0);
	int T=1;
	cin>>T;
	while(T--)solve();
	return 0;
}
/*
dp[i][j][k]：考虑(i,j)~(n,m)的子矩阵，a到了第k位，先手是否必胜
考虑初始化：dp[i][j][k]=1（其中b[i][j]=a[k]）
考虑转移：
b[i][j]=a[k]:
dp[i][j][k]=(!dp[i+1][j+1][k+1])
i==n or j==m or k==l
b[i][j]!=a[k]:
dp[i][j][k]=dp[x][y][k](i<=x and j<=y)
这是E1的做法
发现转移中，若(i,j)=1，则(i,k)=1 [k<=j]
记：
f[i][k]表示使dp[i][j][k]=1最大的j
mx[i][k]表示使b[i][j]=a[k]最大的j
考虑用这个转移：
f[i][k]=max(mx[i][k],f[i+1][k+1])
i==n or k==l:f[i][k]=mx[i][k]
这是E2的做法
*/

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...