A. 编码

一眼原题，是一道数据结构（？）优化2-SAT建图的题。

2-SAT还是比较容易看出来的，每一个串只有$0/1$两种取值，一个串对另一个串起到了限制的作用。

于是暴力的做法就是先将所有的串按照长度排序，由小到大分别将两个副本插入字典树。

对字典树上每个节点维护一个vector，表示终止节点集合。

当一个串插入的时候，对路径上每个节点的vector集合内元素，建$a\ xor \ b=1$的命题即可。

容易发现一个元素只向祖先节点对应的元素集合建边。

所以可以随着字典树构造另外两棵树，一棵向上，一棵向下，来实现优化建边。

B. 哈密顿回路

可以发现，因为这是一条回路，起点的位置是无关紧要的。

所以可以直接折半搜索了。

C. 旅行

问题是构造一个DFS序，使得在DFS序上相邻两个叶子节点的距离的最大值的最小值最小。

这个问题一看就是二分答案，设当前考虑的为$lim$。

然后可以发现对于每棵子树，只关注一条上去的链和一条下来的链。

使这两条链最小，是更优的。

所以考虑合并，对于两棵子树分别贡献$(a,b)$，$(c,d)$。其中$a<=b$，$c<=d$。

如果$b+d<=lim$，那直接上传$(a,c)$即可。

如果$a+c>lim$，那就可以直接返回不合法。

但是如果$b+d>lim$，并且$a+d<=lim$ $b+d<=lim$，我的考试时简单的上传一个$pair$的算法就伪了。

其实已经与正解很接近了。

一个节点可以上传很多个$pair$。

考虑怎样的$pair$是优秀的，仅当不存在一个$pair$，满足两维均比它小。

所以对每个节点，维护一个$pair$类型的vector，满足第一维递增，第二维递减。

一个性质是，所有节点的$vector$大小的总和不超过$nlog(n)$，因为有$|vector(father)|<=2min(|vector(lch)|,|vector(rch)|)$。

证明是，考虑取出左右儿子中vector大小较小的那一个。

对于该vector中的每个元素，找到另一个vector中匹配最合适（可以通过单调指针实现）的那一个，放入父节点的vector中。

之后将父节点的vector翻倍（即两维互换）即可。

D. 猎人杀

刚开始一直在想容斥，然后没有结果，还是把这个题想复杂了。

最后打暴力，写状压，还没打完考试就结束了。

实际上状压是没有必要的，因为只有第一个猎人是特殊的，对于其他的猎人，我们只关注他当前对于$1$号猎人的相对位置。

所以设$dp_{i,j}$表示还有$i$个猎人，当前有一枪打在第$j$个猎人身上。

分两种情况讨论，即没打死和打死就行了。

然后发现这个转移出现了环，也就是说没打死会不断转移到自己。

然后发现这个东西只存在简单环，所以暴力展开一下就好了。