自动搬运

查看原文

来自洛谷，原作者为

	rzh123 而我将 爱你所爱的人间 / 愿你所愿的笑颜 / 你的手我蹒跚在牵 / 请带我去明天

搬运于2025-08-24 22:51:50，当前版本为作者最后更新于2023-10-28 07:51:14，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

因为每一列构成排列，如果给 $z_i$ 加一，第 $i$ 列只有一个数字对应布尔值会从 $0$ 变成 $1$，总共最多只会有一个 $val_{2n-1}$ 从 $0$ 变成 $1$。没有从 $1$ 变成 $0$ 的。

暴力枚举 $i$ 从 $1$ 到 $n$，每次给 $z_i$ 一直加一直到 $m$，如果还没有达到 $s$ 就到下一个 $i$ 继续加。比如样例就是枚举 $(0,0,0,0),(1,0,0,0),(2,0,0,0),(3,0,0,0),(3,1,0,0),(3,2,0,0),\cdots$，因为每次最多加 $1$，一定能枚举到恰好是 $s$ 的情况。一共枚举了 $O(nm)$ 种情况。

现在只需要一种快速修改的方法。对于指令，$a_p,b_p$ 不重复，把 $p$ 向 $a_p,b_p$ 连边，构成了一个二叉树（表达式树），每次相当于修改一个叶节点，从叶节点开始一直跳父亲更新。更新时只有 $0$ 变成 $1$ 的，如果跳到一个节点时它已经是 $1$ 就停止，如果更新完仍然是 $0$ 也停止，这样每个节点只会被修改一次，修改的总复杂度 $O(nm)$。

#include <bits/stdc++.h>
using namespace std;
constexpr int N=3e5+5;
int n,m,s;
struct Op{
    int a,b,t;
};
vector<int> x[N],pos[N],fa[N],val[N];
// pos[i][j]: i 在第 j 列的第几行
vector<Op> op[N];
int z[N],crtcnt;
void upd(int i){
    if(z[i]==1) return;
    int p=pos[z[i]-1][i];
    // val[p][i]: 0->1
    val[p][i]=1;
    if(n==1){
        ++crtcnt;
        return;
    }
    int u{fa[p][i]};
    for(;;u=fa[p][u]){
        if(val[p][u]) break;
        auto t=op[p][u-n];
        if(t.t==1) val[p][u]=(val[p][t.a]&&val[p][t.b]);
        else val[p][u]=(val[p][t.a]||val[p][t.b]);
        if(!val[p][u]) break;
        if(u==2*n-1){
            ++crtcnt;
            break;
        }
    }
    // printf("crtcnt=%d\n",crtcnt);
}
signed main(){
    scanf("%d%d%d",&n,&m,&s);
    for(int i{1};i<=m;++i){
        x[i].resize(n+3);
        op[i].resize(n+3);
        pos[i].resize(n+3);
        fa[i].resize(n*2+5);
        val[i].resize(n*2+5);
        for(int j{1};j<=2*n-1;++j){
            val[i][j]=0;
        }
    }
    for(int i{1};i<=m;++i){
        for(int j{1};j<=n-1;++j){
            int a,b,t;scanf("%d%d%d",&a,&b,&t);
            op[i][j]={a,b,t};
            fa[i][a]=fa[i][b]=n+j;
        }
    }
    for(int i{1};i<=m;++i){
        for(int j{1};j<=n;++j){
            scanf("%d",&x[i][j]);
            ++x[i][j];
            pos[x[i][j]][j]=i;
        }
    }
    for(int i{1};i<=n;++i) z[i]=1;
    for(int i{1};i<=n;++i){
        if(crtcnt==s) break;
        for(;;++z[i],upd(i)){
            if(crtcnt==s){
                i=n+1;
                break;
            }
            if(z[i]==m+1) break;
        }
    }
    for(int i{1};i<=n;++i){
        printf("%d%c",z[i]-1," \n"[i==n]);
    }
    return 0;
}