上一章节：https://www.cnblogs.com/znstz2018/p/18695755
本文发布了一些习题的解答。
https://qoj.ac/problem/9156
容易发现，在一轮询问之后，所有还可能成为答案的元素，是图上的一个独立集。
这启发我们用一些大小相同的团去进行一轮询问，至于用何种大小的团，可以考虑 dp。
令 \(dp(i,j)\) 表示，用 \(i\) 轮询问，在 \(j\) 个点中找最大值，最小的查询次数是多少。转移需要注意如下几点：
- 注意处理除不尽的情况，比如将 \(10\) 个元素分成大小为 \(4\) 的团。\(4,3,3\) 要优于 \(4,4,2\)，为了处理这一问题，可以考虑枚举团的个数，而不是大小。
- 团的大小不能太大，可以限定一个团的大小的范围，然后通过 \(j/size\) 算出团的个数，注意除不尽的问题，可以通过枚举一个小邻域来避免。
- 耐心等待运行结果。
https://qoj.ac/problem/9237
先在 \(S\) 的后面补上 \(100\cdots000\)，这样可以统一长度，只需考虑 \(|S|=1025\) 的情况。
将你发送的信息顺次拼接成一个 \(66 \times 31\) 的矩阵。记所有可以用的列为 \(d_0,d_1,\cdots,d_{15}\)，定义 \(c_i=(d_{i+1}-d_i) \bmod 31\)。
将矩阵的第 \(d_i\) 列从上到下依次写入 \(c_i-1\) 个 \(0\) 和 \(1\) 个 \(1\)，总共会占用 \(31\) 个 bits。在没被占用的位置依次写入 \(S\) 的每一个字符，正好能填满。
解密的时候可以根据每一列第一个 \(1\) 出现的位置解出 \(c_i\)，连边 \(i \rightarrow (i+c_i) \bmod 31\)，形成一棵基环树，由于 \(31\) 个点的基环树只可能有一个长度 \(\ge 16\) 的环，故 \(d_0,d_1,\cdots,d_{15}\) 可被唯一确定，进而确定 \(c_i\)，确定被占用的位置，然后读出 \(S\) 即可。
https://qoj.ac/problem/8642
观察到题目中并不要求我们求出最短路的长度，而是求出一条路径上的所有点。
考虑最短路树，你可以通过最短路树得出每一条边会在哪些点的最短路径上出现。在解密的时候，你只需要将经过的边的权值设成 \(0\)，没经过的边的权值设成 \(+\inf\)，直接运行最短路算法即可。
考虑在最短路树中提取出 \(16\) 个询问点的虚树，对于每一条被隐藏边权的边，只需要花费 \(5\) bits 去传递虚树上的一个节点编号。
问题变成了如何运用 \(60\) bits 传递这个虚树，可以考虑将所有点按照 dfn 从小到大依次加入，编码所有可能插入的位置，容易发现总共可能的方案数是双阶乘，可以接受。
https://qoj.ac/problem/8745
对于每一条边，随机 \(25\) 个询问填 \(1\)，另外 \(25\) 个询问填 \(0\)。
问完所有询问之后，考虑一个一个删叶子。
对于一个叶子，一定会有恰好 \(25\) 次询问的返回值为 \(1\)，另外 \(25\) 次询问的返回值均大于 \(1\)。对于非叶子，你可以通过简单的放缩将误判叶子错误率分析到 \(2^{-25}\)。
考虑确定叶子的父亲，对于每个叶子返回值 \(\gt 1\) 的的询问，一定有：叶子的返回值恰好比父亲的返回值多 \(1\)，你还是可以通过简单的放缩将误判父亲的错误率分析到 \(2^{-25}\)。
然后更新掉每个询问中父亲的返回值即可。
https://qoj.ac/problem/7281
令 \(n=1000\)，答案的二元组为 \((u,v)\)，令 \(u \le v\)。
子任务 \(1\)，枚举二进制位，每次问所有这一位为 \(0\) 的数，如果有则答案的这一位为 \(0\)，否则为 \(1\)。\(R= \log n\)，由于不需要在线，\(H=1\)。
子任务 \(2\)，考虑一个二分的过程，先找到较小的位置，然后找较大的位置，注意找较大的位置的时候，如果询问集合包含已经确定的小的位置，需要把它删掉。过程需要在线，\(R=H=2\log n\)。
子任务 \(3\)，枚举每一位，询问所有这一位为 \(0\) 的数，和所有这一位为 \(1\) 的数，然后读取结果。如果某一位，\(0\) 有 \(1\) 没有，则 \(u,v\) 的这一位都为 \(0\)； \(0\) 没有 \(1\) 有同理。如果 \(0,1\) 都有，则说明 \(u,v\) 这一位不相同，不妨令这些位的最高一位 \(d\) 上，\(u\) 为 \(0\)，\(v\) 为 \(1\)。我们只需要确定 \(u\) 所有的位 \(i\) 和位 \(d\) 是否相同，枚举 \(i\)，询问所有位 \(i\) 和位 \(d\) 都为 \(0\) 的数，\(R=3\log n,H=2\)。
子任务 \(4\)，首先有一个随机化的做法，每一次询问随机一个集合，每个数等概率被包含，令概率为 \(P\)，则一个数在一次询问中被确定 \(\notin \{u,v\}\) 的概率是 \(P \cdot (1-P)^2\)，取 \(P=1/3\) 最优，实测 \(R=56\)。
借用子任务 \(3\) 的想法，枚举每一位，询问所有这一位为 \(0\) 的数，和所有这一位为 \(1\) 的数，然后再随机加一点集合，实测 \(R=41\)。
换一个角度考虑，对于每一个 \([1,n]\) 的数 \(i\)，确定一个二进制数 \(A_i\)，其中第 \(d\) 位表示了在第 \(d\) 次询问中是否包含 \(i\)。询问的结果可以看做得到一个二进制数 \(A_u | A_v\)，其中 \(|\) 表示按位或，也就是说，需要找到一个尽可能短的二进制数组 \(A\)，满足对于任意 \(u,v(u \le v)\)，\(A_u|A_v\) 两两不同。
嗯，其实这是一道提交答案题，把 \(A\) 在本地求出来后打表，询问后暴力枚举找答案就行。
一个很直观的感觉是 \(A_u\) 的 \(popcount\) 在 \(1/3\) 长度左右，在这个数字两边试试，尝试一些随机化，逐个确定 \(A_i\)，能得到 \(R=30\) 左右的做法。观察到如果一个二进制数加入后不合法，那么在之后的过程中同样也不合法，想做到更优的话需要实现一个能快速从一个序列中随机选一个数并删除的东西。我的实现方法是维护序列长度 \(x\) 和里面剩余的数个数 \(y\)，每次随机的期望随机次数是 \(x/y\)，如果 \(y \ge x/2\)，就不管它，否则把序列重构一次，这样每个数均摊是 \(O(1)\) 的，可以得到 \(R=28\) 左右的做法。
还有一个不是很直观的感觉，\(A_i |A_j\) 的 \(popcount\) 不能太小，不然很容易撞。若 \(R=26\)，我取的阈值是 \(A_i\) 的 \(popcount =8\)，\(A_i|A_j\) 的 \(popcount \ge 11\)，从小到大尝试加入，能得到 \(992\) 个 \(A_i\)，就差 \(8\) 个，很恶心。
考虑给这个过程加点乱搞， 初始令 \(A_i|A_j\) 的 \(popcount\)，阈值为 \(15\)，然后找一轮，找完之后将阈值减一点，比如 \(15 \rightarrow 14 \rightarrow 11\)，每次遇到能加入的数，以 \(99\%\) 的概率加入，多跑几次，我得到 \(996\) 个 \(A_i\)。
遍历一遍所有 \(2^R\) 个数，检查是否能加入，将所有能加入的数找出来，发现很少（我得到了 \(7\) 个），枚举所有可能的情况，加入 \(996\) 个 \(A_i\) 并检查，然后就找到解了。