CF2219B2 Unique Values (Hard version)
查询 \(|S|-\mathrm{ask}(S)\) 可以得到出现 2 次的数的个数减去出现 3 次数的个数，那么根据奇偶性可以得到是否有出现 3 次的数。
可以依次从后往前求每个 3 的位置。
AT_agc044_d [AGC044D] Guess the Password
先问 \(128\times c\)，\(\mathrm{occ}(c)=128-\mathrm{ret}\)。
然后做归并排序。
CF2031F Penchick and Even Medians
如果找到了中位数两侧的两个数 \(x,y\)，可以增量维护，每次询问 \(x,y,i,j\)，如果其中包含中位数中的一个，则一定会返回包括中位数的结果。
这样我们可能会获得 \((i_1,j_1),(i_2,j_2)\)，答案在这些 pair 中。
容易得到正确的答案。
然后是 \(x,y\) 怎么办，直接随机化，然后问 \(x,y\) 的补集。
P16457 [UOI 2026] Guess the Number
先问最高位，然后考虑在区间 \([d\times 10^7,(d+1)\times 10^7)\) 二分答案。
考虑 \(mid\le n\Rightarrow 1\le \frac{n}{mid}\)，所以可以问 \(\frac{10^{16}}{mid}\)，然后首位是 1 就说明 \(mid\le n\)。
注意到确定了 \(n_{\max}\) 不会超过 2 倍 \(n_{\min}\)，所以直接判断是不是 1 就是对的。
QOJ18123 Is this a problem?
先求出一个极大的独立集 \(S\)，然后考虑其补集 \(T\)，二分找出 \(S\to T\) 的所有边。
然后是 \(T\) 内部的边，可以递归处理。
pkuCPC2026G
题意：
- 交互题。
- 有一棵未知的 \(n\) 个节点的树，每次你可以选择一个点集，你会得到这个两端都
在点集内的边的数量，你要在 \(35\) 次询问内找到一个叶子。 - \(1\le n\le 10^5\)。
查询 \(n-1-\mathrm{ask}(U-S)-\mathrm{ask}(S)\) 可以得到 \(S\) 集合的度数。
那么可以根据鸽巢原理进行二分。
P14002 [eJOI 2025] Navigation
考虑 dfs，颜色 1 表示这个点还没遍历完 0 的出边，颜色 2 表示这个点已经结束遍历。
树：按照上述模拟，若一个点没有 0 的出边，那么就往唯一的 1 出边走，并标记当前节点颜色 2。
然后仙人掌的话会有环，考虑环走了一圈走到一开始进来那个点，这时候我们是需要回溯的。将 3 颜色标记到最后一个点上，那么我们可以通过 1 的个数区分 3 颜色的两个邻居。
如果起点在环上的话就不太对，因为 1 的个数都是 1。
但是发现最多会多走一圈，正确性是对的。次数 \(\le 3n\)。
AT_agc077_e [AGC077E] Hamiltonian Path Inversion
\(x=0\) 一定是 0000...11111....。
考虑增加一个逆序对，可以交换一对相邻的 01。
考虑每次交换的都是最后一对 01。那么这样类似于每次冒泡一个 0 到后面。0 跑到最后就相当于这个序列循环位移了。
考虑构造：
000000...00000
001111...11110
011111...11110
000000...00000
容易找到哈密顿回路满足某个 0 夹在 \(x,y\) 个 1 之间：在外层开始走，走到合适的位置再在内层绕一圈后出来。
P9605 [IOI 2023] 机器人比赛
分两步：
- dfs 出最短路径。
- 标记最短路径，并将多余的删掉。
那么考虑用 2,3,4,5 标记一个格子指向的方向。类似迭代加深搜索，走到空白格子就指向父亲，而走到标记过的格子就旋转这个点的指向方向，直到旋转到一个格子 \(v\) 是指向自己的或者空白的。
注意：\(u\) 指向的格子 \(v\) 一定指向 \(u\)，这可以区分我们在做哪一步。
判断是否到达终点：右下都是 -2。
到达终点后把箭头指向右/下，现在整个图形成终点的根向树。
然后从终点开始回溯到起点，现在从起点开始标记最短路。
如果有指向 \(u\) 的格子 \(v\)，那么走过去递归子树。否则考虑标记 \(u\) 是 0 还是 1。
\(u\) 周围有 1 就标记 1，否则标记 0。接着走向 \(u\) 原本指向的格子 \(v\)。