P6965 [NEERC2016]Binary Code

oisdoaiu · 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，则：

可以复制一遍 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;
}

还是复制一遍 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;
}

设点 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 )

完整代码