问题描述
Bob 最新学习了一下二进制前缀编码的那一套理论。二进制编码是指一个由\(n\)个互不相同的二进制串\(s_1,s_2,...,s_n\)构成的集合。而如果一套编码理论满足，对于任意的 \(i\not=j\)，\(s_i\)不是\(s_j\)的前缀，那么我们称它为前缀编码。
Bob 发现了一张上面写有\(n\)行二进制编码的纸，但这张纸年代久远，有些字迹已经模糊不清。幸运的是，每一行至多只会有一个模糊的字符。
Bob 想知道这\(n\)行二进制编码是否有可能是一个前缀编码？
输入格式
第一行一个整数\(n\)，表示编码的大小。
接下来\(n\)行，每行一个由 0、1 及 ? 组成的字符串。保证每一行至多有一个 ?。
输出格式
如果这\(n\)个二进制编码可能是前缀编码，输出 YES，否则输出 NO。
对于所有的\(n\)，保证\(n\leq500000\)，字符串长度\(\leq500000\)
不同于Trie树的板题，这个题其实还有一些别的东西。首先判断一个字符串是不是另一个字符串的前缀是非常模板的问题，直接套Trie树模板即可。但是我们发现这个题有一个非常坑的地方：‘?‘的存在！有了这个‘?‘，前缀就无法确定。
怎么办呢？
发现每一个字符串最多只有一个‘?‘，我们通过思考可以想到，这个‘?‘，实际上表达了一个信息：即这个字符为0和为1的状态必须且只能选一个。这让我们想到了2-SAT算法！2-SAT算法即是用来解决这种问题的。那么这个题转化为了一个2-SAT的基础建模题。
1.\(s_i\)为\(s_j\)前缀
这种情况我们就可以将它转化为2-SAT的常见模型————\(i\)和\(j\)最多只能选一个，那么\(i\)向\(j‘\)连边，\(j\)向\(i‘\)连边。
2.\(s_i\)没有‘?‘
转化为2-SAT模型中的已选模型————\(i‘\)向\(i\)连边。
然后直接跑2-SAT即可。
#include <bits/stdc++.h>
using namespace std;
char ch[5000005];
int id[5000005][2], cnt, Go[5000005][2], tot;
struct node {
int to, nxt;
}e[10000005]; int head[5000005], tt;
inline void add_e(int u, int v) {e[++tt].to = v; e[tt].nxt = head[u]; head[u] = tt;}
inline void insert(char *s, int k)
{
int u = 0;
for (int i = 0, c; s[i]; i++)
{
if (s[i] == ‘?‘) c = k & 1;
else c = s[i] - ‘0‘;
if (!Go[u][c]) Go[u][c] = ++tot;
u = Go[u][c];
}
if (!id[u][0]) add_e(k, id[u][0] = ++cnt), add_e(id[u][1] = ++cnt, k ^ 1);
else
{
add_e(k, id[u][1]), add_e(id[u][0], k ^ 1);
add_e(k, ++cnt), add_e(id[u][0], cnt), id[u][0] = cnt;
add_e(++cnt, k ^ 1), add_e(cnt, id[u][1]), id[u][1] = cnt;
}
}
stack <int> st; int ct;
bool instk[5000005];
int dfn[5000005], scc, bl[5000005], low[5000005];
inline void Tarjan(int u)
{
st.push(u); instk[u] = 1;
dfn[u] = low[u] = ++ct;
for (int i = head[u]; i; i = e[i].nxt)
{
int v = e[i].to;
if (!dfn[v]) Tarjan(v), low[u] = min(low[u], low[v]);
else if (instk[v]) low[u] = min(low[u], dfn[v]);
}
if (dfn[u] == low[u])
{
int v; ++scc;
do
{
v = st.top();
st.pop();
bl[v] = scc;
instk[v] = 0;
} while (u ^ v);
}
}
void dfs(int u, int p1, int p2)
{
if (id[u][0])
{
if (!p1) p1 = id[u][0], p2 = id[u][1];
else
{
add_e(p1, id[u][1]), add_e(id[u][0], p2);
add_e(p1, ++cnt), add_e(id[u][0], cnt), p1 = cnt;
add_e(++cnt, p2), add_e(cnt, id[u][1]), p2 = cnt;
}
}
if (Go[u][0]) dfs(Go[u][0], p1, p2);
if (Go[u][1]) dfs(Go[u][1], p1, p2);
}
int main()
{
int n;
scanf("%d", &n); cnt = 2 * n + 2;
for (int i = 1; i <= n; i++)
{
scanf("%s", ch); insert(ch, i << 1);
if (!count(ch, ch + strlen(ch), ‘?‘)) add_e(i << 1 | 1, i << 1);
else insert(ch, i << 1 | 1);
} dfs(0, 0, 0);
for (int i = 1; i <= n; i++)
{
if (!dfn[i << 1]) Tarjan(i << 1);
if (!dfn[i << 1 | 1]) Tarjan(i << 1 | 1);
if (bl[i << 1] == bl[i << 1 | 1]) return !puts("NO");
} puts("YES");
}