P9786 题解

rzh123 · 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;
}