CF2002G 题解

· · 题解

Problem Link

题目大意

给定 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}))。

代码呈现

#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;
}