自动搬运

查看原文

来自洛谷，原作者为

	TruchyR ¿啥你问了我我问了你啥?

搬运于2025-08-24 23:10:27，当前版本为作者最后更新于2025-02-25 20:45:12，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

知识点：Hall 定理、轮廓线 dp。

赛时被队友一眼秒了但是自己不会怎么办。

本文内棋子可以移动的方向和题目里的相反。

我们把初始状态的每个棋子看作一个左部点，最终状态的每个棋子看作一个右部点。

在可以到达的状态之间连边，本题就是在求这个二分图是否存在完备匹配。

根据 Hall 定理，一个二分图存在完备匹配的充要条件是对于左部点的大小为 $k$ 的任意子集 $S$，这些点在右部连到的点集大小不小于 $k$。

所以我们令 $c_{i,j,k}=a_{i,j,k}-b_{i,j,k}$，我们要求的就是以下问题。

选取若干个点，如果有一个点被某个选择的点偏序了那么这个点也要选。使得选出的点的权值 $c$ 之和最大。

如果这个最大值大于 $0$，就说明存在一个点集不满足上述条件。

设 $p_{i,j}$ 表示第 $i$ 块第 $j$ 行选了前 $p_{i,j}$ 个点。根据偏序关系容易有 $p_{i,j}\geq p_{i,j+1}$ 和 $p_{i,j}\geq p_{i+1,j}$。

因为后两维的数据范围很小，考虑直接把他们压缩在一起。状态数的计算考虑组合意义，即 $C_{6+6}^{6}=924$。

有第一种状态 $f_{i,w}$ 表示考虑到第 $i$ 层且第 $i$ 层选点状态是 $w$，权值和的最大值。

直接暴力转移是 $O(n\times 924^2)$ 的，大抵是过不去。

怎么办？可以考虑轮廓线 dp。

假如轮廓线现在的状态长这样：
| $p_{i,j}$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | |:-:|:-:|:-:|:-:|:-:|:-:|:-:| |$j-1$|$/$|$/$|$/$|$?$|$1$|$0$| |$j$|$6$|$3$|$3$|$2$|$/$|$/$|

那么我们枚举问号处选中了多少个点，就可以从上一个轮廓线的状态转移。

还是因为偏序关系，这里轮廓线的总状态数顶天是 $6\times 924$ 的，加上转移复杂度仍然是可以过的。

实现时建议开滚动数组，以及特判 $B=1$ 时带来的一些问题。

代码前面几行也是简要的题解。

//学习Hall定理和轮廓线dp。 
//首先每个棋子看成一个点 a是左部点b是右部点
//能移动到的连边 这题就是在求是否有完备匹配
//Hall定理：一个图存在完备匹配的充要条件是
//          对于任意大小为k的左部点集S，它的可达右部点集T大小>=k
//那么令c[i][j][k]=a[i][j][k]-b[i][j][k]
//我们要选择一些点(如果一个点选了那么被偏序的必须选)
//使得sum(c[i][j][k])最大。
//其他两维很小，考虑直接压缩状态 
// #####. 首先对于一层的点的选择状态肯定长这样。 
// #####. 考虑直接把第三维压掉变成二维问题。 
// ####.. 从上往下转移，每层选的点数肯定也和上一层偏序。 
// ####.. 然后转移是一个高维前缀max 但是不好做 实际上和状压差不多 
// ##.... 我们考虑轮廓线dp！
//        假如轮廓线现在长这样（存储为f[4][6,3,3,2,1,0]） 
// ...?10 那么我们只需要枚举?位置的值就可以从f[3][6,3,3,?,1,0]转移过来了
// 6332   用组合意义粗略估算有效状态数约为C(12,6)*6=5544。轻微卡常。 
#include<bits/stdc++.h>
#define MX 10005
#define int long long
#define CKE if(CHECK)
#define FRE if(FIL)
using namespace std;
const int CHECK=0,FIL=0;int read();
int T,n,x,y,cnt,a[MX][7][7],b[MX][1000];
int f[117649],p[1000][8],q[7],g[7][1000]; 
void dfs(int t,int lst,int o){
	if(t>x){
		p[++cnt][0]=o;f[o]=cnt;
		for(int i=1;i<=x;i++)
			p[cnt][i]=q[i];
		p[cnt][x+1]=0;
		return;
	}
	for(int i=0;i<=lst;i++){
		q[t]=i;dfs(t+1,i,o*(y+1)+i);}
}
signed main(){
	//ios::sync_with_stdio(false);
	//cin.tie(0);cout.tie(0);
	FRE freopen(".in","r",stdin);
	FRE freopen(".out","w",stdout);
	T=read();while(T--){
		n=read();x=read();y=read(); 
		for(int i=n;i>=1;i--) for(int j=x;j>=1;j--) for(int k=y;k>=1;k--)
			a[i][j][k]=read();
		for(int i=n;i>=1;i--) for(int j=x;j>=1;j--) for(int k=y;k>=1;k--)
			a[i][j][k]-=read();
		//搜索所有可能状态 & 其他预处理 
		//p[t][0] 第t个状态hash值
		//p[t][1~x] 第t个状态代表什么
		//f[h] hash值为h的是哪个状态
		//b[i][t] 第i层 第t个状态覆盖的点的权值和 
		cnt=0;dfs(1,y,0);
		memset(g[0],-0x3f,sizeof(g[0]));
		g[0][1]=0,q[x]=1;
		for(int i=x-1;i>=0;i--) q[i]=q[i+1]*(y+1);
		for(int i=1;i<=n;i++){
			for(int j=1;j<=cnt;j++){
				b[i][j]=0;
				for(int k=1;k<=x;k++) for(int l=1;l<=p[j][k];l++)
					b[i][j]+=a[i][k][l];
			}
		}
		//轮廓线 dp
		int res=0;
		for(int t=n;t>=1;t--){
			for(int o=1;o<=x;o++){
				for(int I=1;I<=cnt;I++){
					//第t块
					//轮廓线包含第t块前o个和第t-1块的后B-o个状态 
					//这些状态叠起来是第I个状态 
					int lo=p[I][o+1];
					int hi=p[I][o];
					int zt=p[I][0]-q[o]*hi;
					if(x>1) g[o%x][I]=-1e18;
					for(int i=lo;i<=hi;i++)
						g[o%x][I]=max(g[o%x][I],g[o-1][f[zt+q[o]*i]]);
				}
			}
			//这一层枚举完了 加上对应权值 
			for(int I=1;I<=cnt;I++){
				g[0][I]+=b[t][I];
				if(t==1) res=max(res,g[0][I]);
			}
		}
		if(res>0) printf("NIE\n");
		else printf("TAK\n");
	}
	return 0;
}
int read(){
	int Ca=0;char Cr=' ';int Cf=1;
	while(Cr<'0' || Cr>'9'){Cr=getchar();if(Cr=='-'){Cf=-1;}}
	while(Cr>='0' && Cr<='9'){Ca=Ca*10+Cr-48;Cr=getchar();}
	return Ca*Cf;
}