IOI2021 集训队作业（二）
有生之年。
103. Boys and Girls
求一个长为 \(n\) 的由 01 构成的环，满足恰有 \(x\) 个点的两侧有 0 ，恰有 \(y\) 个点的两侧有 1 。
时间复杂度：\(O(n)\) 。
题解
注意到每个点的两侧有三种情况：全是 0 ，全是 1 ，一边 0 一边 1 ，设上述三种情况的点的数量分别为 \(a\), \(b\), \(c\) ，容易知道有 \(c = x + y - n\), \(a = x - c\), \(b = y - c\) 。
我们把距离恰为 \(2\) 的点连边，得到一个新的环，准确来说，如果 \(n\) 是奇数，得到的是一个长为 \(n\) 的环，否则得到的是两个长为 \(\dfrac{n}{2}\) 的环。
那么我们现在要做的就是在环上填 01 使得三种边的数量分别为 \(a, b, c\) ，注意到 \(c\) 必须是偶数，且 \(c\) 为 \(0\) 的时候必须有 \(ab = 0\) 。假设只有一个环，就很容易构造一个解，两个环的话就把边集分成两个大小相等的部分，只要满足每个部分都合法即可。
109. Knapsack Cryptosystem
Hellman-Knapsack Cryptosystem 这一密码系统的描述如下：
A 的密钥由长为 \(n\) 的正整数序列 \(a\) 和两个互质的正整数 \(r, q\) 组成，满足 \(\forall i, a_i > \sum_{j=1}^{i-1} a_j\) 且 \(q > \sum_{i=1}^n a_i\) 。
A 的公钥是一个长为 \(n\) 的正整数序列 \(b\) ，其中 \(b_i = (a_i \cdot r) \bmod q\) 。
需要传输给 A 的信息是一个长为 \(n\) 的 01 序列 \(z\) ，加密方式是计算 \(s = \sum_{i=1} z_i b_i\) ，然后将 \(s\) 传输给 A 。
（这样一来，仅知道公钥破译 \(z\) 的难度远远比通过密钥计算 \(z\) 的大）
现在你窃取到了 \(q\) 的值和 \(s \bmod q\) 的值，求出 \(z\) （公钥也是已知的）。
时间复杂度：\(O(\sqrt[3]{q} \log q)\) 。
题解
首先注意到 \(n \le \log_2 q\) ，如果 \(n\) 非常小，不难想到直接枚举 \(z\) 然后加以验证，这样的复杂度是 \(O(2^n)\) 的。
上述做法很好加以优化，不难想到折半搜索，做到 \(O(n 2^{n/2})\) 。
但如果 \(n\) 非常大呢？注意到 \(n\) 越大对 \(a\) 的限制就越强，具体来说，这个限制是 \(a_1 2^{n-1} < q\) ，当 \(n\) 很大的时候，\(a_1\) 的可能的取值会很少，不妨枚举 \(a_1\) ，进而通过 \(a_1\) 和 \(b_1\) 的值确定 \(r\) （并不能唯一确定，枚举所有可能的 \(r\) 即可）。知道 \(r\) 后就可以还原整个密钥，进而得到 \(z\) 。
得到 \(z\) 的具体方法是，求出 \(t = (s \cdot r^{-1}) \bmod q)\) ，那么 \(t = \sum_{i=1} z_i a_i\) ，由于 \(a\) 的性质特殊，可以直接确定 \(z\) 。
这一做法的复杂度是 \(O(\dfrac{q}{2^n} n)\) 。
综合两者，总复杂度是 \(O(\sqrt[3]q \log q)\) 。
110. Heavy Chain Clusterization
给定 \(n\) 个长度至少为 \(k\) 的串 \(s_i\) ，要求将它们划分成若干集合，使得每个集合的串满足以下至少一个条件：
- 它们的最长公共前缀至少为 \(k\) 。
- 它们的最长公共后缀至少为 \(k\) 。
在此基础上，最小化划分的集合的数量。
时间复杂度：\(O(n^2 + \sum_{i=1}^n |s_i|)\) 。
题解
每个 \(s_i\) 可以抽象为一个二元组 \((x_i, y_i)\) ，其中 \(x_i\) 和 \(y_i\) 分别表示 \(s_i\) 长为 \(k\) 的前缀和后缀。
那么一个集合要满足的条件就是集合内二元组的 \(x\) 均相同或 \(y\) 均相同。
进一步把二元组抽象为连接两点的边，那么形成一个有 \(n\) 条边的二分图，要求对边集进行划分，每个边集要满足的条件即：该边集存在一个公共点。
那么实际上我们可以用公共点来代表该边集，那么最小的边集划分实际上就是最小的点覆盖。对二分图求最小点覆盖是容易的。
117. List of Primes
将所有质数组成的数集排序（以总和为第一关键字，数集内部排序后的字典序为第二关键字），然后依次写到纸上组成字符串，求该字符串 \([L, R]\) 之间的子串。
其中一个数集按如下方式书写：[a1, a2, a3, ... an],
（每个逗号后面都有一个空格）。
时间复杂度：\(O(X^2 + R - L)\) ，其中 \(X\) 是 \([1, R]\) 内的子串涉及到的数集的和的最大值。
题解
先 DP 预处理出 \(f_{i,j}\) 表示由编号大于等于 \(i\) 的质数组成的总和不超过 \(n\) 的数集的数量。类似地处理 \(g_{i,j}\) 表示这些数集表示的字符串的长度的和。
然后就可以直接搜索所有数集，先枚举总和，再枚举字典序，根据 \(f, g\) 我们可以时刻知道当前状态对应字符串的下标区间，如果该区间与 \([L, R]\) 就剪枝。
状态构成了一颗多叉有根树，而这个搜索方法类似于线段树的区间操作，那么搜索到的无用节点的数量不超过 搜索树深度 乘 搜索树节点度数 ，两者都不超过 \(X\) 内的质数数量。
ps: \(R = 10^{18}\) 时 \(X = 2096\) 。
106. Binary vs Decimal
求第 \(n\) 小的满足十进制表示是二进制表示的后缀的正整数。
时间复杂度：\(O(L f(L) \dfrac{L}{w})\) ，其中 \(L\) 是答案的十进制表示的位数，\(f(L)\) 是长度为 \(L\) 的合法的数的数量。
ps: \(f(L)\) 几乎是线性的，在假定 \(f(L) = O(L)\) 的前提下，上述复杂度即 \(O(\dfrac{n^{1.5}}{w})\) 。
题解
称一个 \(01\) 串 \(s\) 是合法的，当且仅当 \(s\) 是其代表的十进制数的二进制表示的后缀。
注意到 \(s\) 合法的一个必要条件是：\(s_{2 ... |s|}\) 是合法的。
那么我们可以枚举长度 \(l\) ，考虑求出所有 \(|s| = l\) 的合法 \(s\) ，求法就是从每个长为 \(l-1\) 的合法串前添加 0 和 1 分别判断是否合法。注意到这个过程是可以从小到大遍历所有合法正整数的，遍历到第 \(n\) 个的时候退出即可。
复杂度分析略，至于 \(f\) 的增长速度究竟如何还有待进一步研究，值得一提的是 \(f(L)\) 并不是随 \(L\) 单调递增的，但 \(L \le 1000\) 时总有 \(f(L) < 7.2 L\) 。
175. Ice Igloos
给定若干圆心在整点且半径小于 1 的圆。\(q\) 次询问，每次询问一个端点为整点的线段与多少圆有交点。保证任意两个圆心的切比雪夫距离不超过 \(W\) 且没有同心圆。
时间复杂度：\(O(W^2 + qW)\) 。
题解
事实上，对于一条长为 \(l\) 的线段，与其距离小于 \(1\) 的整点的数量是 \(O(l)\) 的，枚举所有小于 \(1\) 的整点即可。
具体的，先枚举横坐标 \(x\) ，然后可以计算出纵坐标 \(y\) 的范围，再枚举范围内的纵坐标即可。特别处理线段平行于 y 轴的情况即可。
177. Outer space invaders
对于一个非负整数数列给定 \(n\) 个限制，每个限制形如要求第 \(l\) 项到第 \(r\) 项必须存在不小于 \(k\) 的值。求满足所有限制的前提下，数列的各项和的最小值。
时间复杂度：\(O(n^3)\) 。
题解
区间 DP ，设 \(f_{L, R}\) 表示仅考虑 \(L \le l \le r \le R\) 的限制，数列第 \(L\) 到 \(R\) 项的和的最小值。设这些限制的 \(k\) 的最大值为 \(x\) ，那么至少要有一个位置填 \(x\) ，转移枚举填 \(x\) 的位置即可。
求 \(x\) 只需要通过差分预处理 \(m_{L, R}\) 表示范围内限制的 \(k\) 的最大值。
239. Triangles
给定一个形如下面这样的图，求三角形的数量。图的行数和列数分别为 \(n\), \(m\) 。
时间复杂度：\(O(n m \log m)\) 。
题解
仅考虑上面一个点下面两个点的三角形，在右下角统计这样的三角形。
预处理每个点向左和向左上向右上有多少条连续的边，那么统计的时候就是要询问该点向左一段指定区间内有多少点的向右上达到了一个值，扫描线加树状数组即可。
170. String Theory
定义一个长为 \(n\) 的正整数序列 \(a\) 是 \(k\) 引用的，当且仅当：
- 若 \(k=1\) ，则 \(n = 2, a_1 = a_2 = 1\) 。
- 若 \(k>1\) ，则 \(a_1 = a_n = k\) 且 \(a_{2...n-1}\) 由若干 \(k-1\) 引用的序列拼接而成。
给定一个序列 \(b\) ，每次操作可以将 \(b\) 的一项总和不变的若干项，要求操作后 \(b\) 是一个 \(k\) 引用序列，求最大的 \(k\) 。
时间复杂度：\(O(\sum b_i)\) 。
题解
序列 \(a\) 是 \(k\) 引用的一个必要条件是，前面 \(k\) 项是 \(k\) 到 \(1\) ，后面 \(k\) 项是 \(1\) 到 \(k\) 。而对于中间的项，不妨全部划分成 \(1\) ，是不会影响合法性的。
这样一来可以知道，\(b\) 可以操作为一个 \(k (k > 1)\) 引用序列当且仅当可以把前面 \(k\) 项操作为 \(k\) 到 \(1\) ，后面 \(k\) 项操作为 \(1\) 到 \(k\) ，中间的部分和为偶数。对于 \(k=1\) 的情况需要特判。
由于 \(k\) 的上界是 \(O(\sqrt{\sum b_i})\) 的，那直接枚举 \(k\) 并 \(O(k)\) 判断的复杂度就是 \(O(\sum b_i)\) 的。
183. Hack Protection
给定一个长为 \(n\) 的序列 \(a\) 求有多少区间满足按位异或等于按位与。
时间复杂度：\(O(n \log n \log a_i)\) 。
题解
考虑对于固定的区间右端点 \(r\) 统计答案，注意到对于任意一个数位，均存在一个分界点 \(p\) 满足：
- 左端点落在 \([1, p]\) 内时区间按位与为 \(0\) 。
- 左端点落在 \([p + 1, r]\) 内时区间按位与为 \(1\) 。
由于每个数位都有一个分界点，假设一共有 \(k\) 个数位，那么就可以把 \([1, r]\) 划分成至多 \(k + 1\) 个区间，满足同一区间内左端点落在任何位置按位与都是相同的。
那么维护每个分界点，然后在每个区间内查询按位异或即可。可以记录异或前缀和，然后对于每个值都开一个
std::vector 记录下标，查询的时候二分。
210. Sensor Network
在平面上给定 \(n\) 个点，求一个最大的点集使得任意两个点的距离不超过 \(d\) 。
时间复杂度：\(O(n^5)\) 。
题解
假设固定了点集中距离最远的两个点，它们的距离为 \(r\) ，那么其他可以选的点必须离两个点的距离都不超过 \(r\) ，容易发现可选的区域构成一个纺锤形，进一步观察可以发现，把该纺锤形平分为 A 和 B 两个区域，那么同一区域内的任意两点距离都不超过 \(r\) （如下图所示）。
那么，如果在纺锤形内把距离超过 \(r\) 的两点连边，会构成二分图，而要求的点集事实上就要求是独立集，二分图最大独立集是容易的。
这个复杂度上界的分析很大但实际上跑的往往不满，不知道有没有更好的复杂度分析。
285. Integral Polygons
给定一个由 \(n\) 个整点构成的凸多边形，求有多少条连接两个顶点的线段把多边形切割为两个面积均为正整数的部分。
时间复杂度：\(O(n)\) 。
题解
首先存在答案的一个必要条件是整个多边形面积为整数。
由于我们只需要关注面积两倍的奇偶性，不难发现每个点的横纵坐标也只需要关注奇偶性。定义一条连接 \((x_1, y_1)\) 和 \((x_2, y_2)\) 的线段的权值为 \(x_1 y_2 + x_2 y_1\) ，那么一个多边形的面积两倍的奇偶性就是边权和的奇偶性。
那么一条连接 \((x_1, y_1)\) 和 \((x_2, y_2)\) 的线段是合法的当且仅当
\[ (p_1 + p_2 + x_1 y_2 + x_2 y_1) \bmod 2 = 0 \]
其中 \(p_1\) 和 \(p_2\) 分别是两个点的边权前缀和。我们只需要关注每个点的 \(p, x, y\) 在模 \(2\) 意义下的值，一共有 \(2^3\) 种情况，记录每种情况的点的数量即可。
291. Binary Code
有 \(n\) 个 01 串，每个串 \(s_i\) 至多有一个位置未知。确定未知部分的字符，使得任意两个串相互不是前缀。
时间复杂度：\(O(\sum |s_i|)\) 。
题解
由于每个串有两种选择，不难发现该问题可以规约到 2-SAT 问题的模型。其中如果两个串有前后缀关系，那么它们代表的变量就是相互矛盾的。
但是不难发现矛盾的数量是 \(O(n^2)\) 的，因此需要优化建图，把所有串扔到 Trie 上，串之间的前缀关系可以用一棵树描述，前缀关系在树上等价于祖先关系，也就是说两个变量有矛盾当且仅当它们在该树上有祖先关系。在树上优化连边，建图跑 2-SAT 即可。
207. Escape
给定一棵 \(n\) 个点的树，点有点权。初始时能量为 \(0\) ，从点 \(s\) 开始游走，首次到达一个点会获得该点点权的能量（可能为负），求在保证能量始终非负的前提下是否能到达点 \(t\) 。
时间复杂度：\(O(n \log n)\) 。
题解
链
考虑对于树上的一条链，我们该如何处理它。
首先，相邻的非负权值点可以合并，相邻的负权值点可以合并。这是显而易见的。因此接下来假设链上的点权的符号是交替的。设第 \(i\) 个点的权值为 \(a_i\) ，不妨假设有偶数个点且 \(a_1 \le 0\) 。
若 \(|a_2| < |a_1|\) ，那么到达前两个点的时候能量会减少，因此如果要经过第一个点，就必然要经过第三个点。据此我们可以将 \(a_1, a_2, a_3\) 三个点合并。因此接下来可以假设
\[ \forall i \ge 1, |a_{2i-1}| \le |a_{2i}| \]
若 \(|a_2| \ge |a_3|\) ，那么到达第二个点的时候，可以直接前往第四个点，这样一定不劣。据此我们可以将 \(a_2, a_3, a_4\) 三个点合并。因此我们可以讲 \(a\) 转换为绝对值单调递增的形式。
树
事实上，对于一棵子树，同样可以转换为一条链。
对于节点 \(u\) 的子树，首先将 \(u\) 个每个儿子的子树转换为一条链，然后不难想到可以把这些链排序重组为一条新的链。具体的，我们将链上相邻两个点 \(a_{2i-1}\) 和 \(a_{2i}\) 看做一个整体，然后按 \(|a_{2i-1}|\) 排序组成一条新的链。
但是这样并不能保证 \(|a_i|\) 单调递增，但是没关系，只需要让每条链保证：
- \(\forall i \ge 1, a_{2i-1} \le 0 \le a_{2i}\)
- \(\forall i \ge 1, |a_{2i-1}| \le |a_{2i}|\)
- \(\forall i \ge 1, |a_{2i-1}| \le |a_{2i+1}|\)
称这样的链为合法链，容易发现多条合法链排序重组仍是合法链。
接下来，需要在一条合法链的开头加上 \(u\) 节点本身（事实上为了保证偶数长度还需要加一个零权点），我们按照“链”部分的讨论使得新链合法即可。
原问题
我们可以以 \(s\) 为根把树转换成一条合法链，但是 \(t\) 可能并不会出现在链上，这是因为，不是每个子树都能成功转换为合法链，对于这些子树需要删掉，而 \(t\) 可能恰好在这样的子树中。
一个简单的解决方法是建一个新点连向 \(t\) ，该点的权值为 \(W\) ，\(W\) 是一个足够大的正值使得问题可以转换为：判断是否能够使得能量不小于 \(W\) 。这样一来就不需要关注终点位置了。
容易发现合法链实际对应一个可并堆的数据结构，因此总复杂度可以做到 \(O(n \log n)\) 。
143. Jump
有一个长度为 \(n\) （\(n\) 为偶数）的 01 串 \(s\) ，每次询问可以给出一个长度为 \(n\) 的 01 串 \(q\) ，设 \(t\) 为 \(s \oplus q\) 的 \(1\) 的数量，询问的结果为 \(t [t = \dfrac{n}{2} \lor t = n]\) 。
询问次数：\(n + O(\sqrt{n})\) 。
题解
不难想到随机串 \(q\) 进行询问直到 \(t = \dfrac{n}{2}\) ，一个询问的成功概率为
\[ p = \frac{\binom{n}{\frac{n}{2}}}{2^n} \]
根据斯特林公式 \(n! \thickapprox \sqrt{2 \pi n} (\dfrac{n}{e})^n\) ，可以知道 \(p \thickapprox \sqrt{\dfrac{2}{\pi n}}\) ，也就是说通过 \(O(\sqrt{n})\) 次随机询问可以得到一个使得 \(t = \dfrac{n}{2}\) 的串 \(q\) 。
那么接下来，不妨假设 \(s\) 有恰好 \(\dfrac{n}{2}\) 个 0 和 \(\dfrac{n}{2}\) 个 1 。
可以发现，如果询问一个 \(q\) 满足 \(q\) 有恰好两个 \(1\) 且分别在 \(i, j\) 两个位置，那么 \(t = \dfrac{n}{2}\) 当且仅当 \(s_i \neq s_j\) 。这样一来一次询问相当于一个连边，只需要 \(n-1\) 次询问就可以把所有位置分为两类，每类的值相同。然后对于可能的两种情况均进行一次询问即可。
282. King's Inspection
给定一张 \(n\) 个点 \(n + m\) 条边的有向图，求一条哈密顿回路或断言其不存在。
时间复杂度：\(O(n + m 2^m)\) 。
题解
众所周知这是个 NP 问题。
首先有解的一个必要条件是每个点的出度至少为 \(1\) 。那么可以注意到的是，在该条件满足的前提下，出度大于 \(1\) 的点至多有 \(m\) 个。
对于出度唯一的点，不妨把它和它连向的点合并，这样最后就只剩不超过 \(m\) 个点了，状压 DP 求哈密顿回路即可。