@gym - [emailprotected] Binary Code

@[email?protected]

我们称一组字符串是 “前缀码”，当且仅当不存在一个字符串为另一个字符串的前缀。

现在给定 n 个 01 字符串，其中有些字符串存在最多一个的未知字符。

问是否能将未知字符替换为 0 或 1，使得这 n 个字符串构成 “前缀码”。

Input
第一行给定整数 n 表示字符串个数 (1 ≤ n ≤ 5 · 10^5).
接下来 n 行每行一个字符串，每个字符串由 ‘0‘,‘1‘,‘?‘ 构成，且保证最多包含一个 ‘?‘。
保证字符串总长不超过 5 · 10^5.

Output
如果无解，输出 "NO"。
否则输出 "YES"，接下来 n 行每行一个字符串（按照输入的顺序输出），表示最后得到的 “前缀码”。
如果有多解，输出任意一个皆可。

Examples
binary.in
4
00?
0?00
?1
1?0
binary.out
YES
000
0100
11
100

binary.in
3
0100
01?0
01?0
binary.out
NO

@[email?protected]

含有问号的串有两种状态，且串 s 选定某个状态时，会导致另一些串只能选择与 s 没有前缀关系的状态。这可以使我们联想到 2-sat。
具体一点，假如 x 与 y 有前缀关系，则 x -> y‘,y -> x‘。
假如 s 不含问号，则我们不妨令 s 表示的串为 x，令 x‘ -> x 即可。

这样建图是 O(n^2) 的，考虑优化建图。
判断任意两个串的前缀关系，不难想到可以上 trie，则两个串是前缀关系当且仅当两个串在 trie 上对应的结点一个是另一个祖先。

我们建出 trie 后，将 trie 拆成两棵 T1,T2，T1 方向全部朝根结点，T2 方向全部朝叶结点。
则与一个点成前缀关系的点要么顺着 T1 往上，要么顺着 T2 往下。
于是我们可以对于 x 所对应的 trie 中结点 k，k 向 x‘ 连边，x 向 k 的父亲与儿子连边。
考虑可以新建一个 k‘，k‘ 向父亲与儿子连，则 k 所能代表的所有 x 直接向 k 连边即可。

最后一个问题：对于长得完全一样的 x1,x2,...,xp，我们不能够随便乱连，否则可能会导致 xi -> xi‘ 的不合法连边。
考虑再新建 y1,y2,yp 表示前缀连边（即 yi 可以直接或间接连向 x1‘...xi‘），可以通过 yi -> yi-1 且 yi -> xi‘ 实现；同理得到 z1,z2,zp 表示后缀连边。
则只需要建 xi -> yi-1,xi -> zi+1 即可达到我们的目的。

@accepted [email?protected]

#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int MAXN = 1000000;
const int MAXV = 5*MAXN;
vector<int>G[MAXV + 5];
int n,m,ncnt;
void addedge(int u,int v) {G[u].push_back(v);}
int ch[2][MAXN + 5];
vector<int>vec[MAXV + 5];
void insert(char *S,int lenS,int id) {
    int nw = 0;
    for(int i=0;i<lenS;i++) {
        if( ch[S[i] - '0'][nw] == 0 )
            ch[S[i] - '0'][nw] = (++ncnt);
        nw = ch[S[i] - '0'][nw];
    }
    vec[nw].push_back(id);
}
void build_trie_edge(int rt,int fa) {
    if( !rt ) return ;
    addedge(fa + 2*n + 0*(ncnt + 1),rt + 2*n + 0*(ncnt + 1));
    addedge(fa + 2*n + 2*(ncnt + 1),rt + 2*n + 0*(ncnt + 1));
    addedge(rt + 2*n + 1*(ncnt + 1),fa + 2*n + 1*(ncnt + 1));
    addedge(rt + 2*n + 2*(ncnt + 1),fa + 2*n + 1*(ncnt + 1));
    for(int i=0;i<vec[rt].size();i++) {
        addedge(rt + 2*n + 0*(ncnt + 1),vec[rt][i]^1);
        addedge(rt + 2*n + 1*(ncnt + 1),vec[rt][i]^1);
        addedge(vec[rt][i],rt + 2*n + 2*(ncnt + 1));
    }
    build_trie_edge(ch[0][rt],rt);
    build_trie_edge(ch[1][rt],rt);
}
void build_node_edge(int rt) {
    if( !rt ) return ;
    if( vec[rt].size() >= 2 ) {
        int lst = vec[rt][0]^1;
        for(int i=1;i<vec[rt].size();i++) {
            addedge(vec[rt][i],lst);
            if( i + 1 == vec[rt].size() ) break;
            m++; addedge(m,lst); addedge(m,vec[rt][i]^1);
            lst = m;
        }
        lst = vec[rt][vec[rt].size() - 1]^1;
        for(int i=int(vec[rt].size())-2;i>=0;i--) {
            addedge(vec[rt][i],lst);
            if( i == 0 ) break;
            m++; addedge(m,vec[rt][i]^1);
            lst = m;
        }
    }
    build_node_edge(ch[0][rt]);
    build_node_edge(ch[1][rt]);
}
int tid[MAXV + 5],low[MAXV + 5],num[MAXV + 5],stk[MAXV + 5];
int tp,tot,dcnt;
void dfs(int x) {
    stk[++tp] = x; tid[x] = low[x] = (++dcnt);
    for(int i=0;i<G[x].size();i++) {
        int p = G[x][i];
        if( !tid[p] )
            dfs(p),low[x] = min(low[x],low[p]);
        else if( !num[p] )
            low[x] = min(low[x],tid[p]);
    }
    if( low[x] >= tid[x] ) {
        tot++;
        while( tp && tid[stk[tp]] >= tid[x] ) {
            int t = stk[tp--];
            num[t] = tot,vec[tot].push_back(t);
        }
    }
}
bool tag[MAXV + 5];
void solve() {
    for(int i=1;i<=tot;i++) {
        for(int j=0;j<vec[i].size();j++) {
            int x = vec[i][j];
            for(int k=0;k<G[x].size();k++)
                if( tag[num[G[x][k]]] )
                    tag[i] = true;
        }
        if( !tag[i] ) {
            for(int j=0;j<vec[i].size();j++) {
                int x = vec[i][j];
                if( x < 2*n )
                    tag[num[x^1]] = true;
            }
        }
    }
}
char str[MAXN + 5]; int len[MAXN + 5];
int main() {
    freopen("binary.in","r",stdin);
    freopen("binary.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%s",str + len[i-1]);
        len[i] = len[i-1] + strlen(str + len[i-1]);
    }
    for(int i=1;i<=n;i++) {
        int pos = -1;
        for(int j=len[i-1];j<len[i];j++)
            if( str[j] == '?' ) pos = j;
        if( pos == -1 ) {
            addedge((i-1)<<1|1,(i-1)<<1|0);
            insert(str + len[i-1],len[i] - len[i-1],(i-1)<<1|0);
        }
        else {
            str[pos] = '0',insert(str + len[i-1],(i-1)<<1|0);
            str[pos] = '1',(i-1)<<1|1);
            str[pos] = '?';
        }
    }
    m = 2*n + 3*(ncnt + 1);
    build_trie_edge(ch[0][0],0),build_trie_edge(ch[1][0],0);
    build_node_edge(ch[0][0]),build_node_edge(ch[1][0]);
    for(int i=0;i<=ncnt;i++) vec[i].clear();
    for(int i=0;i<=m;i++)
        if( !tid[i] ) dfs(i);
    for(int i=0;i<n;i++)
        if( num[i<<1] == num[i<<1|1] ) {
            puts("NO");
            return 0;
        }
    puts("YES"); solve();
    for(int i=1;i<=n;i++)
        for(int j=len[i-1];j<len[i];j++)
            if( str[j] == '?' )
                str[j] = tag[num[(i-1)<<1]] + '0';
    for(int i=1;i<=n;i++) {
        for(int j=len[i-1];j<len[i];j++)
            putchar(str[j]);
        puts("");
    }
}

@[email?protected]

一开始 RE 了，非常懵逼。
后来把 trie 大小稍微调整了一下，发现MLE了又再把2-sat的图的点数调到一个感觉不够的大小，结果 A 了。
思考了一下，发现原来我每次加入字符串是两个两个加的，所以 trie 的大小应该开到 2 倍字符串总长。。。

另外，原来 tarjan 求出来的强连通的编号就是天然的拓扑序。
我以前还一直在写什么拓扑排序。。。原来拓扑排序没用啊。。。

2-sat 用拓扑排序求出来的方案数是非常“任意”的——即它既没有字典序也没有任何已知规律。