CF2002G 题解

题目大意

给定 $n\times n$ 网格，边带权，定义路径权值为经过的边权 $\mathrm{mex}$ ，求从左上走到右下的格路的最大权值。

数据范围： $n\le 20$ 。

思路分析

很显然无法优化维护

\mathrm{mex}(S)

的过程，必须爆搜，因此需要 Meet-in-Middle 平衡复杂度。

那么思路就是选取一条副对角线，每条路径恰好过其中一个点，爆搜出从起点 / 终点到对角线上每个点的路径对应的权值集合。

求答案是否

\ge k

相当于判断交点两侧路径权值集合进行

\mathrm{OR}

卷积后，是否有元素包含二进制位

0\sim k-1

。

无法用 FWT 处理

\mathrm{OR}

卷积状物，因此必须在一侧枚举子集。

那么设这条副对角线在

x+y=k

上，那么左侧枚举子集并插入哈希表，右侧每条格路直接在哈希表中查值即可判定答案是否

\ge k

，如果满足就更新

k\gets k+1

继续判断。

时间复杂度

\mathcal O(n(3^k+2^{2n-k}))

。

代码呈现

CPP

#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct HshT {
	static const int MAXN=(1<<26)+5,P=3e7+1;
	int sz,hd[P],to[MAXN];
	ll w[MAXN];
	void ins(ll x) {
		int p=x%P;
		for(int i=hd[p];i;i=to[i]) if(w[i]==x) return ;
		w[++sz]=x,to[sz]=hd[p],hd[p]=sz;
	}
	bool qry(ll x) {
		int p=x%P;
		for(int i=hd[p];i;i=to[i]) if(w[i]==x) return true;
		return false;
	}
	void init() {
		for(int i=1;i<=sz;++i) hd[w[i]%P]=0,to[i]=w[i]=0;
		sz=0;
	}
}	H;
int n,k,z,a[45][45],b[45][45];
const ll B=1ll<<40;
void dfs(int x,int y,ll s) {
	if(x+y==k+2) {
		while(H.qry((x*B)|(((1ll<<z)-1)&(~s)))) ++z;
		return ;
	}
	if(x>1) dfs(x-1,y,s|1ll<<a[x-1][y]);
	if(y>1) dfs(x,y-1,s|1ll<<b[x][y-1]);
}
void solve() {
	scanf("%d",&n),H.init(),z=1;
	for(int i=1;i<n;++i) for(int j=1;j<=n;++j) scanf("%d",&a[i][j]);
	for(int i=1;i<=n;++i) for(int j=1;j<n;++j) scanf("%d",&b[i][j]);
	k=2*(n-1)/3;
	for(int p=0;p<(1<<k);++p) {
		int i=1,j=1; ll s=0;
		for(int o=0;o<k;++o) {
			if(p>>o&1) s|=1ll<<a[i++][j];
			else s|=1ll<<b[i][j++];
		}
		for(ll t=s;;t=(t-1)&s) {
			H.ins((i*B)|t);
			if(!t) break;
		}
	}
	dfs(n,n,0);
	printf("%d\n",z-1);
}
signed main() {
	int T; scanf("%d",&T);
	while(T--) solve();
	return 0;
}

文章操作

相关推荐

评论

CF2002G 题解