2020.4.16 省选模拟试题 T1 编码 Trie树 + 2-SAT

题目来源

#6036. 「雅礼集训 2017 Day4」编码

题目描述

原题：NEERC 2016 B. Binary Code
Bob 最新学习了一下二进制前缀编码的那一套理论。二进制编码是指一个由 $n$ 个互不相同的二进制串 $s_1,s_2,...,s_n$ 构成的集合。而如果一套编码理论满足，对于任意的 $i\neq j$ ， $s_i$ 不是 $s_j$ 的前缀，那么我们称它为前缀编码。
Bob 发现了一张上面写有 $n$ 行二进制编码的纸，但这张纸年代久远，有些字迹已经模糊不清。幸运的是，每一行至多只会有一个模糊的字符。
Bob 想知道这 $n$ 行二进制编码是否有可能是一个前缀编码？

输入格式

第一行一个整数 $n$ ，表示编码的大小。
接下来 $n$ 行，每行一个由 $0,1$ 及 $?$ 组成的字符串。保证每行至多有一个 $?$ 。

输出格式

如果这 $n$ 个二进制编码可能是前缀编码，输出 $YES$ ，否则输出 $NO$ 。

样例1

4
00?
0?00
?1
1?0

YES

样例解释1

一组可能的解为：

样例2

NO

数据范围与提示

本题采用捆绑测试。
令 $L$ 为输入的字符串总长。
$Subtask1(20\ points):n\leq 10,L\leq 1000$
$Subtask2(30\ points):n\leq 1000,L\leq 5*10^5$
$Subtask3(50\ points):n,L\leq 5*10^5$

题解

$20\ pts：2^n$ 枚举所有可能的字符串情况，插入 $Trie$ 树中判断是否可行
$50\ pts：$ 在 $Trie$ 树中插入所有可能的字符串
问题转化成在 $Tire$ 树中选择 $n$ 个结束点，满足同一 $?$ 形成的两个串的结束点不能同时选
且任意一个结束点的祖先节点中不存在一个结束节点
为 $2-SAT$ 模型，时间复杂度： $O(n^2)$
$100\ pts：$ 考虑在 $50\ pts$ 基础上进行优化
被选择的结束点和该点的祖先不能同时选
所以给 $Tire$ 树上每个节点加一个变量表示不选该点的祖先节点
该变量可以进行从上到下的传递
还应判断 $?$ 处的决策，如果选择了 $Trie$ 树上的某点的前缀，则该点不可选
即必须选择该点的另一个点
此外，有一些不同的串会共用同一个结束位置
这些串之间互相有影响，不能共用
考虑将这个 $Trie$ 树节点看做成 $k$ 个点与 $k-1$ 条边的结合体即可
注意新建的变量编号都 $<<1$ ，因为点 $i<<1$ 与 $i<<1|1$ 之间是不能同时选的
新建的变量没有这些限制，所以要 $<<1$

code

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
int n, len, em = 1, cnt, tot, id, top, scc_cnt;
const int N = 3500010;
int read() {
	int x = 0, f = 1; char ch;
	while(! isdigit(ch = getchar())) (ch == '-') && (f = -f);
	for(x = ch^48; isdigit(ch = getchar()); x = (x << 3) + (x << 1) + (ch ^ 48));
	return x * f;
}
char s[N];
vector<int> v[N];
int ch[N][2], head[N], to[N], nxt[N], dfn[N], low[N], sta[N], scc[N];
void add(int x, int y) {to[++ tot] = y; nxt[tot] = head[x]; head[x] = tot;}
void ADD(int x, int y) {add(x, y); add(y ^ 1, x ^ 1);}
void insert(int x) {
	int p = 1;
	for(int i = 1; i <= len; ++ i) {
		if(! ch[p][s[i] - '0']) ch[p][s[i] - '0'] = ++ em;
		p = ch[p][s[i] - '0'];
	}
	v[p].push_back(x);
}
void dfs(int x, int last) {
	for(int i = 0, siz = v[x].size(), y; i < siz; ++i) {
		y = v[x][i]; ++ cnt; ADD(cnt << 1, y ^ 1);
		if(last) ADD(cnt << 1, last << 1), ADD(y, last << 1);
		last = cnt;
	}
	if(ch[x][0]) dfs(ch[x][0], last);
	if(ch[x][1]) dfs(ch[x][1], last);
}
void Tarjan(int x) {
	dfn[x] = low[x] = ++ id; sta[++ top] = x;
	for(int i = head[x]; i; i = nxt[i]) {
		if(!dfn[to[i]]) Tarjan(to[i]), low[x] = min(low[x], low[to[i]]);
		else if(! scc[to[i]]) low[x] = min(low[x], dfn[to[i]]);
	}
	if(dfn[x] == low[x]) {
		int y; ++ scc_cnt;
		do {
			y = sta[top--];
			scc[y] = scc_cnt;
		} while (y != x);
	}
}
int main() {
//	freopen("code.in", "r", stdin);
//	freopen("code.out", "w", stdout);
	n = read();
	for(int i = 1, pos; i <= n; ++i) {
		scanf("%s", s + 1); len = strlen(s + 1); pos = 0;
		for(int j = 1; j <= len; ++j) if(s[j] == '?') {pos = j; break;}
		s[pos] = '0'; insert(i << 1);
		s[pos] = '1'; insert((i << 1) | 1);
	}
	cnt = n; dfs(1, 0);
	for(int i = 1; i <= ((cnt << 1) | 1); ++ i) if(! dfn[i]) Tarjan(i);
	for(int i = 1; i <= cnt; ++i) if(scc[i << 1] == scc[(i << 1) | 1]) return puts("NO"), 0;
	puts("YES");
	fclose(stdin);
	fclose(stdout);
	return 0;
}
/*
4
00?
0?00
?1
1?0

3
0100
01?0
01?0
*/