[LOJ #6036] 「雅礼集训 2017 Day4」编码

LOJ #6036.

思路

考虑一个平凡一点的方法。可以对于每个串?的位置填0还是填1建一个2-SAT,直接$O(n^2)$枚举找出所有关系即可。

而更优秀的方法,可以把2-SAT挪到可持久化Trie上,对于每个串,?位置取01分成两个串插入,每个串建一个新版本。对于Trie树上的节点,在2-SAT中有不存在和存在两种状态,对于每个串,有取还是不取两种状态。有以下几种约束条件:

  1. Trie树中的父节点不存在,儿子节点一定不存在
  2. 若当前版本的某个节点不存在,之后版本从这个节点拷贝出去的节点都不存在
  3. 若一个串被选了,那么之后版本的这个串的结束节点一定不存在,否则这个串就会成为别的串的前缀
  4. 若一个串被选了,当前版本的这个串的结束节点一定存在

建出2-SAT之后跑一遍Tarjan判是否有解即可

代码

#include <iostream>
#include <cstdio>
#include <algorithm>

#define A(x) (x<<1)
#define B(x) ((x<<1)|1)

struct Graph{
    #define MX 10000010
    int to[MX], ne[MX], head[3000010], cnt;
    Graph() : cnt(1){}
    int operator [](int x){return head[x];}
    void add_edge(int x, int y){
        to[++cnt]=y; ne[cnt]=head[x]; head[x]=cnt;
        to[++cnt]=x^1; ne[cnt]=head[y^1]; head[y^1]=cnt;
    }
    #undef MX
}G;

struct Trie{
    #define MX 2000010
    int cnt, rt, ch[MX][2];
    void insert(std::string s, int p){
        int v=rt, f=rt;
        for(int i=0; i<s.length(); i++){
            int c=s[i]-'0';
            if(!ch[v][c]){
                ch[v][c]=++cnt;
                G.add_edge(A(v), A(cnt));
            }
            f=v, v=ch[v][c]; 
        }
        cnt++;
        G.add_edge(A(v), A(cnt));
        G.add_edge(p, B(v));
        G.add_edge(p, A(cnt));
        ch[f][ch[f][1]==v]=cnt;
    }
    #undef MX
}T;

int N;
std::string s[500010];

namespace Tarjan{
    #define MX 3000010
    int dfn[MX], low[MX], col[MX], cnt, sta[MX], top, tot;
    bool fl[MX];
    
    void dfs(int x, int fa){
        dfn[x]=low[x]=++cnt;
        sta[++top]=x; fl[x]=true;
        for(int i=G[x]; i; i=G.ne[i]) if(G.to[i]!=fa)
            if(!low[G.to[i]]){
                dfs(G.to[i], x);
                low[x]=std::min(low[x], low[G.to[i]]);
            }else if(fl[G.to[i]]) low[x]=std::min(low[x], dfn[G.to[i]]);
        if(low[x]==dfn[x]){
            tot++;
            while(sta[top]!=x) col[sta[top]]=tot, fl[sta[top]]=false, top--;
            col[sta[top]]=tot, fl[sta[top]]=false, top--;
        }
    }

    bool check(){
        for(int i=1; i<=B(T.cnt); i++)
            if(!dfn[i]) dfs(i, 0);
        for(int i=1; i<=T.cnt; i++)
            if(col[A(i)]==col[B(i)])
                return false;
        return true;
    }
    #undef MX
}

int main(){
    scanf("%d", &N); T.rt=T.cnt=N+1;
    for(int i=1; i<=N; i++) std::cin>>s[i];
    std::sort(s+1, s+N+1, [](std::string a, std::string b){return a.length()<b.length();});
    for(int i=1; i<=N; i++)
        for(int j=0; j<s[i].length(); j++)
            if(s[i][j]=='?'){
                s[i][j]='0'; T.insert(s[i], A(i));
                s[i][j]='1'; T.insert(s[i], B(i));
                break;
            }else if(j==s[i].length()-1){
                G.add_edge(B(i), A(i)); 
                T.insert(s[i], A(i));
            }
    puts(Tarjan::check() ? "YES" : "NO");
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注