原题链接：P6965 [NEERC2016] Binary Code

笔者做的第 6 道黑题。

与其说是做，不如说是贺。因为笔者不仅几乎没有接触过数据结构优化建边，也完全不知道这道题应该如何实现，所以完全借鉴了 Alex_Wei 老师的题解。本篇博客，其实是在做完之后重新梳理一下思路，细化一下建边的思考与实现过程。

数据结构优化建图

首先，什么是数据结构优化建图，就是法如其名。我们可以利用一些数据结构的好的性质来简化建图的操作，让边数更少，或建边更快。

比如，考虑 线段树 善于 维护区间 的性质，我们可以使用他优化 向区间建边 的操作，比如 P5471 [NOI2019] 弹跳。感觉貌似这种数据结构优化建图的很多都是一个内向树、一个外向树，管辖 最短路的起点和终点 / 字符串的前缀和当前是另一字符串的前缀，这应该也是一种套路吧。

还有另一种套路，就是 前缀优化建边。这真的很抽象，所以大家可以 BDFS 理解，我就不多说了。

巧的是，本题同时运用了这两种套路。所以，妙啊。

本题的建边分析

我们来分析一下这个题的大概流程。

• 首先，注意到每个位置只能填 \(0\) 或 \(1\)，考虑使用 2-SAT，这是必然的。

• 我们考虑如何建边：枚举第 \(i\) 个位置的选择 \(p_i\)，此时该字符串为 \(s_i\)。若存在另一个位置 \(j\) 的选择 \(p_j\)，使得该字符串为 \(s_j\)，且 \(s_i\) 是 \(s_j\) 的前缀，则 \(p_i\) 和 \(p_j\) 二者只能选其一，在连边上体现为 \(p_i \to \neg p_j,p_j \to \neg p_i\)。

• 寻找前缀的过程非常的繁琐，这会增加代码难度和程序运行时间。所以我们考虑使用 01 - trie 来维护前缀。分别构建 内向（根向）/ 外向（叶向） 字典树。对上文中 \(s_i\) 为 \(s_j\) 前缀的情况，我们可以转化为 \(p_i\) 向 \(s_i\) 在字典树中子树代表的所有字符串的选择 \(p_j\) 的 否定 \(\neg p_j\) 连边，使用外向字典树；\(p_j\) 向 \(s_j\) 在字典树中祖先代表的所有字符串的选择 \(p_i\) 的否定 \(\neg p_i\) 连边。

• 为防止出现 \(s_i=s_j\)，导致同一位置向同一位置的否定连接导致误判无解，我们在连接 祖先否定 时实际是从对应状态的 父亲 开始，连接 子树否定 时实际是从对应状态的 两个儿子 开始。由于有字典树辅助建边的存在，实际上我们只需要对 父亲 或者 儿子 连边即可，祖先和子树会顺着字典树的边构成关系。

• 对于 \(s_i = s_j\) 但对应不同字符串的情况，我们对任意一个 \(p_i\) 向其他选项的否定 \(\neg p_j\) 连边，暴力连太慢了，我们考虑 前后缀优化建图。

连边的具体实现

在上一个部分分析好了流程之后，我们这一部分来真正的实现他。

字典树的构造 insert

插入之前，如果这个字符串有 ? 的话，我们就找到它，替换一下。

std::cin>>n; tot=(n<<1)+2; // 初始化动态开点编号分配起点
for(int i=0;i<n;++i) {
	std::cin>>s[i];
	qpos[i]=s[i].find('?'); // 找一下问号小姐的位置
	if(~qpos[i]) {
		s[i][qpos[i]]='0',insert(i<<1,s[i]);
		s[i][qpos[i]]='1',insert(i<<1|1,s[i]);
	} // 有问号就换两次
	else insert(i<<1,s[i]),insert(i<<1|1,s[i]); // 没问号就无所谓
}

字典树也要作为图的一部分并入 2-SAT 跑连通分量算法，所以我们考虑给字典树分配节点编号。

我们给第 \(i\) 个位置选 \(0\) 和选 \(1\) 分配编号 i<<1 和 i<<1|1。字典树的编号则从 \(2n\) 开始。（注意我的写法中字符串下标从 \(0\) 开始，所以字典树编号从 \(2n\) 而非 \(2n+2\) 开始。）

两棵树要同时构建，还要动态开点，所以考虑用 偶数点 构建 外向树，用 奇数点 构建 内向树。动态开点的同时构建树的有向边。

最后，记录当前字符串对应的点 \(ontrie_{id} \gets now\) ，记录这个点对应的字符串的 否定 \(buc_{now} \gets buc_{now} \bigcup \{ id \oplus 1 \}\)，记录当前字符串在这个点对应的所有字符串的集合中的下标 \(pos_{id} \gets |buc|\)。（下标从 \(0\) 开始。）再将当前节点与对应字符串的 否定 连边。这样，\(p_i\) 到这个节点连边时，就相当于 \(p_i\) 向这个节点对应选择的 否定 \(\neg p_j\) 连边了。

inline void insert(int id,const std::string &s) {
	int now=n<<1; // 外向树树根，内向树编号通过外向树异或 1 获得
	for(auto ch:s) {
		bool to=ch-'0';
		if(!node[now][to]) add(now,tot),add(tot^1,now^1),fa[node[now][to]=tot]=now,tot+=2; // 动态开点，同时建立有向树边
		now=node[now][to];
	}
	ontrie[id]=now,pos[id]=buc[now].size(),buc[now].push_back(id^1); // 维护字符串对应节点相关信息
	add(now,id^1),add(now^1,id^1); // 向对应选项的否定连边
}

接下来对于每个选项，向两棵树连边就好啦。

for(int i=0;i<n<<1;++i) {
	int p=ontrie[i]; // 获取选项在子树中的位置
	node[p][0]&&(add(i,node[p][0]),0);
	node[p][1]&&(add(i,node[p][1]),0); // 向外向树儿子连边
	add(i,fa[p]^1); // 异或后变成奇数点，转到内向树
}

前缀优化建边

对于同一个节点对应的不同字符串，我们先 向前、向后 两个方向把他们的 否定 全部连边，这就是传说中的 前后缀优化建图 中为什么称为“前后缀”了。

for(int i=n<<1;i<nowtot;i+=2) {
	if(buc[i].empty()) continue;
	int size=buc[i].size();
	pref[i].resize(size),suff[i].resize(size); // 使用 resize 重新划分内存会比 push_back 快
	for(int p=0;p<size;++p) {
		if(p) add(tot,tot-1);
		add(tot,buc[i][p]),pref[i][p]=tot++;
	} // 构造前缀边
	for(int p=size-1;~p;--p) {
		if(p!=size-1) add(tot,tot-1);
		add(tot,buc[i][p]),suff[i][p]=tot++;
	} // 构造后缀边
}

接下来，每一个选项对所有其他选项的否定连边，直接对它 相邻 的两个选项否定连边即可，其他选项的关系 靠前后缀边传递。

for(int i=0;i<n<<1;++i) {
	int q=pos[i]; // 获取当前选项在该节点代表的所有选项的集合中的下标
	if(q) add(i,pref[p][q-1]); // 与前缀建立关系
	if(q+1<buc[p].size()) add(i,suff[p][q+1]); // 与后缀建立关系
}

接下来，就是一个 相 ~ 当简单的普通 tarjan，平凡的 2-SAT 操作啦 ~

完整代码

// Author: MichaelWong
// Code: C++14(GCC 9)
// Date: 2023/8/11
// File: E.cpp
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define pii std::pair<int,int>
#define fsp(x) std::fixed<<std::setprecision(x)
#define forE(u) for(int p=head[u],v=to[p];p;p=next[p],v=to[p])
const int N=3e6+5,M=1e7+5;
int cnt,head[N],to[M],next[M];
inline void add(int u,int v) { to[++cnt]=v,next[cnt]=head[u],head[u]=cnt; }
int n,tot,node[N][2],fa[N],ontrie[N],pos[N];
std::vector<int> buc[N],pref[N],suff[N];
int dfn[N],low[N],tim,stc[N],top,instc[N],scc,bel[N],qpos[N];
std::string s[N];
inline void insert(int id,const std::string &s) {
	int now=n<<1;
	for(auto ch:s) {
		bool to=ch-'0';
		if(!node[now][to]) add(now,tot),add(tot^1,now^1),fa[node[now][to]=tot]=now,tot+=2; 
		now=node[now][to];
	}
	ontrie[id]=now,pos[id]=buc[now].size(),buc[now].push_back(id^1);
	add(now,id^1),add(now^1,id^1);
}
void tarjan(int u) {
	dfn[u]=low[u]=++tim;
	stc[++top]=u,instc[u]=1;
	forE(u) {
		if(!dfn[v]) tarjan(v),low[u]=std::min(low[u],low[v]);
		else if(instc[v]) low[u]=std::min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u]) {
		++scc;
		while(top) {
			bel[stc[top]]=scc,instc[stc[top]]=0;
			if(u==stc[top--]) break;
		}
	}
}
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr); std::cout.tie(nullptr);
	std::cin>>n; tot=(n<<1)+2;
	for(int i=0;i<n;++i) {
		std::cin>>s[i];
		qpos[i]=s[i].find('?');
		if(~qpos[i]) {
			s[i][qpos[i]]='0',insert(i<<1,s[i]);
			s[i][qpos[i]]='1',insert(i<<1|1,s[i]);
		}
		else insert(i<<1,s[i]),insert(i<<1|1,s[i]);
	}
	int nowtot=tot;
	for(int i=n<<1;i<nowtot;i+=2) {
		if(buc[i].empty()) continue;
		int size=buc[i].size();
		pref[i].resize(size),suff[i].resize(size);
		for(int p=0;p<size;++p) {
			if(p) add(tot,tot-1);
			add(tot,buc[i][p]),pref[i][p]=tot++;
		}
		for(int p=size-1;~p;--p) {
			if(p!=size-1) add(tot,tot-1);
			add(tot,buc[i][p]),suff[i][p]=tot++;
		}
	}
	for(int i=0;i<n<<1;++i) {
		int p=ontrie[i];
		node[p][0]&&(add(i,node[p][0]),0);
		node[p][1]&&(add(i,node[p][1]),0);
		add(i,fa[p]^1);
		int q=pos[i];
		if(q) add(i,pref[p][q-1]);
		if(q+1<buc[p].size()) add(i,suff[p][q+1]);
	}
	for(int i=0;i<tot;++i) if(!dfn[i]) tarjan(i);
	for(int i=0;i<n;++i) {
		if(bel[i<<1]==bel[i<<1|1]) return std::cout<<"NO\n",0; 
		if(~qpos[i]) s[i][qpos[i]]=(bel[i<<1]<bel[i<<1|1]?'0':'1');
	}
	std::cout<<"YES\n";
	for(int i=0;i<n;++i) std::cout<<s[i]<<'\n';
	return 0;
}

// The code was submitted on Luogu.
// Version: 1.
// If I filled in nothing on the statement,
// it means I'm in a contest and I have no time to do this job.

这个优化建图真的太牛了，不过其实前后缀还有优化的空间，就是注意到同一个点表示的选项，如果 ? 的位置一样，那顶多容纳两个，超过就不合法，所以可以考虑用 std::map 或 std::unordered_map 直接暴力维护一下。据说也是能过的。

学会一个知识点，理解一个黑题，好爽。

脑子前所未有的 生化 升华。

本栏目推荐文章
• Jmeter 如何连接mysql数据库？
• SQL Server 检测是不是数字型数据的两种方法
• 如何通过Navicat把MySQL远程数据库导入到本地数据库
• 和利时MACS6通过dat文件实现任意时间范围与测点的历史数据提取与科研分析
• 深入理解spring框架：剖析多线程模式下数据库连接
• 数据可视化是如何帮助大型企业提高效率的？
• redis 数据库
• openpyxl模块--------------------------------重复数据
• Django客户端应用1向服务端应用2发送POST请求并接收解析数据
• 数据可视化是如何帮助我们高效了解数据的？

数据结构 结构 就是 报告 数据数据结构 结构 就是 报告 报告 专电 数据结构 结构 报告 数据结构 结构 数据 报告 数据结构 第一次 结构 数据源 前端 思路 就是 报告书 用户界面 界面 结构 接口 就是 数据api 线程 缓存 数据库 就是 软件 就是 数据 数据表 专题 报告 数据