自动搬运

查看原文

来自洛谷，原作者为

	oisdoaiu 林地生长于漫宿墙外。每一个研习诸史的人都知道，漫宿无墙

搬运于2025-08-24 22:25:31，当前版本为作者最后更新于2021-03-02 11:25:19，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

注意到每个串只有一个 ? (只有 $2$ 种状态)，所求的是构造方案，所以考虑使用 2-SAT。

于是进一步想到如果 $x_0,y_0$ 一个是另一个的前缀，就 $x_0\to y_1,y_0\to x_1$。

那么容易想到暴力 $n^2$ 建图，下一步显然就是减少边数。

考虑使用 trie，那么对于一个状态 $x_0$ ，设 trie 上对应点为 $cur$，则：

• $x_0$ 连向 $cur$ 的祖先节点的另一个状态(比如说 $cur$ 的祖先中有一个 $y_1$，则连向 $y_0$ )

可以复制一遍 trie，trie 树上儿子连父亲，然后 $x_0\to fa(cur),cur\to x_1$ (这样可以避免连自己)，增加 $m$ 个点($m$ 为 trie 的节点个数)， $m+2n$ 条边。

inline void build1(){
    for(register int i=1; i<=trie_cnt; i++) if(fa(i)) Add_Edge(i+node_cnt,fa(i)+node_cnt);
    for(register int i=1, x; i<=n; i++){
        x = loc[0][i]; if(x) Add_Edge(x+node_cnt,Y(i)); if(fa(x)) Add_Edge(N(i),fa(x)+node_cnt);
        x = loc[1][i]; if(x) Add_Edge(x+node_cnt,N(i)); if(fa(x)) Add_Edge(Y(i),fa(x)+node_cnt);
    }
    node_cnt += trie_cnt;
}

• $x_0$ 连向 $cur$ 的儿子节点的另一个状态(同上)

还是复制一遍 trie，父亲连儿子，然后 $x_0\to cur, fa(cur)\to x_1$ ，增加 $m$ 个点， $m+2n$ 条边。

inline void build2(){
    for(register int i=1; i<=trie_cnt; i++) if(fa(i)) Add_Edge(fa(i)+node_cnt,i+node_cnt);
    for(register int i=1, x; i<=n; i++){
        x = loc[0][i]; if(x) Add_Edge(N(i),x+node_cnt); if(fa(x)) Add_Edge(fa(x)+node_cnt,Y(i));
        x = loc[1][i]; if(x) Add_Edge(Y(i),x+node_cnt); if(fa(x)) Add_Edge(fa(x)+node_cnt,N(i));
    }
    node_cnt += trie_cnt;
}

• $x_0$ 连向 $cur$ 对应的其他状态的另一个状态

设点 $cur$ 对应的状态为 $a_1,a_2\cdots$，那么我们要做的就是把 $a_i$ 和 $a_j'$ ( $a_j$ 的对应状态)两两连边，这是一个经典的前缀优化建图模型，增加 $2n$ 个点， $12n$ 条边。

inline void build3(){
    static int tmp[MAXN], num;
    for(register int i=1; i<=trie_cnt; i++){
        num = vec[i].size();
        if(num>=2){
            for(register int j=1; j<=num; j++)
                tmp[j] = vec[i][j-1],
                Add_Edge(tmp[j],j+node_cnt),
                Add_Edge(j+num+node_cnt,tmp[j]^1);
            for(register int j=1; j<num; j++)
                Add_Edge(j+node_cnt,j+1+node_cnt),
                Add_Edge(j+node_cnt,tmp[j+1]^1),
                Add_Edge(tmp[j+1],j+num+node_cnt),
                Add_Edge(j+1+num+node_cnt,j+num+node_cnt);
            node_cnt += num*2;
        }
    }
}

然后走一般 2-SAT 流程就行了，输出方案看哪个状态的 $belong$ 小，就选哪个状态。

一点小细节

仔细看题，最多一个"?"，意思是会有没有 ? 的字符串(样例2)，这种情况可以假设任意一位为 ? ，然后强制这一位选 $0/1$ 。(即 $x_0\to x_1$ 或者 $x_1\to x_0$ )

完整代码