交互题杂题选做

首先假设没有变异鼠

考虑每一只老鼠的信息量是 $1$ bit，而我们要确定的是 $\log n$ bits

因此至少要 $\log n$ 只老鼠，不难想到二进制

考虑让第 $i$ 只老鼠喝 $2^{i-1}$ 这一位是 $1$ 的所有水，死了这一位就是 $1$，否则是 $0$

注意到变异鼠就是普通老鼠取反，因此我们要考虑确定变异鼠的位置

然后就是这题很牛的地方了

注意到我们又在做一个确定位置的东西，因此考虑和刚才的做法类似，因此我们得找一个方法判定一组小白鼠当中是否有矛盾的地方

考虑用第 $k$ 只检验鼠来检验所有编号第 $2^{k-1}$ 这一位是 $1$ 的所有鼠，检验方法就是和这些鼠的水集合的异或，然后再把最后的死亡情况取一个异或，若为 $1$ 则表示有矛盾

这样正确的原因是所有水都被喝了偶数次，因此异或起来一定是 $0$，由于有且仅有一只变异，所以出现差错的话答案一定异或起来是 $1$

然后注意到我们无法判断变异鼠是在检测鼠当中还是实验鼠当中，不过注意到我们还剩一只没有用，拿它来检测检测鼠即可

神仙分块题。

考虑先花 $1000$ 步走到棋盘正中间，那么显然棋盘被分成了四块。

注意到删去存在车最少的那一块，剩下三块中车的个数一定大于等于 $500$，但是我们只需要走 $499$ 步就能让这些车都将到我一次。

一直往对应的方向斜着走即可。

但是注意到有些时候斜着走会被其他车挡住。

但是没有关西，考虑这样上界也就多 $500$ 步，而且我们仍然可以做到对手每一步都有事儿干，显然我们迟早能走到一个两车的位置。

首先不难想到花一次问出整棵树的最大距离。

注意到 $\gcd$ 越取越小，因此最大距离一定产生于两个相邻的点。

因此要想到一种策略，使得我们每次都能取一个大小减半的连通块，这样就可以二分，然后判断要求的点对是否在这个连通块内。

考虑树上连通块问题要么是树分治，要么可以考虑排成序列问题。

我们考虑序列的欧拉序，注意到欧拉序有一个性质就是相邻两个数都是相连的。

而且其长度只是翻倍了而已，因此剩下 $11$ 次就可以确定答案。

显然考虑先问出全局最大值，然后二分找到最大值位置。

由于集合两两不交，只剩下一个包含最大值的集合没确定了。

最后花一次问出来即可。

大概想法显然是每一位问两次，然后逐位确定。

那么剩下两次我们考虑干什么。

考虑怎么诸位确定，大胆猜想肯定要先每一次问消去 $a, b$ 比当前位高的所有位后的大小关系。

那么我们先想想我们逐位确定时，留给下一层的信息最重要的其实就是这一层消去后的大小关系。

注意到第一层之前我们没这个信息，因此考虑我们先花一次问出 $a, b$ 大小关系，然后每一层的策略就相同了。

我们不妨设 $a>b$，然后假设我们在问第一位。

假设消去之后还是 $a > b$，即大小关系不变，那么显然当前位是相同的，只需要确定具体是全 $0$ 还是全 $1$ 即可。

这个可以考虑反转其中一项再问一次，显然最后的大小关系就是这一位的大小关系。

假设消去之后还是 即大小关系变了，那么显然当前位是不同的，并且哪个是 $0$ 哪个是 $1$ 可以确定。

不过没有确定的是消去这一层的大小关系，因此问出这个即可。

最后只需要 $61$ 次。

注意到一旦有一个确定的数，那么我们全部 xor 一遍就可以得到答案。

我们不妨花 $n-1$ 次确定出 $a_0$ 与剩下所有元素的异或值，不难发现此时若存在两个相同的数我们是可以知道的。

若存在，我们拿出那两个相同的数，与一下，就可以推出所有数了。

若不存在，那么这个序列就是一个排列，显然值域中每一个数都恰好出现一次。

我们考虑取出两个数，一个数异或数组的前 $i$ 都是 $0$，后 $k-i$ 位都是 $1$，另一个刚好相反。这里的 $i$ 可以任取。

把这两个数与第一个数的且问出来，由于是 $0$ 的部分都与第一个数对应位相同，因此其与的结果就是第一个数的对应位。

那么确定了第一个数就可以直接做了。

两次一次高 $7$ 位都是 $0$，一次低 $7$ 位都是 $0$ 即可。

这样一次确定高 $7$ 位，一次确定低 $7$ 位，拼起来就行。

首先第一次显然要问出这个距离，然后一定会返回一个链上的点。

我们以这个点为根构建出有根树，二分即可找出两个点中的某个点，然后再询问另一个点的对应深度的点集即可确定另一个点。

但是二分可能要 $10$ 次，次数有点不够。

注意到两个隐藏点中的某一个的深度一定在 $[\frac{len}{2}, len]$ 之间。

这样询问区间缩小一半，刚好只需要 $9$ 次，加上额外的两次一共 $11$ 次。

首先由于我们要构造出的每一条路径权值和不同，因此显然要构造出一个整数的集合，里面每一个数与一条路径一一对应。

只有这样给你这个数你才可以唯一确定这条路径。

那么我们考虑什么可以和一条路径一一对应，一个常见的转化是一个长度为 $2n-2$ 的序列，里面每一个元素取 “向下走” 或者 “向右走”。显然所有包含恰好 $n-1$ 个向下和恰好 $n-1$ 个向右的这种序列与一条路径一一对应。

注意到这个序列每一位只有两种取值，因此考虑压位，发现 $2^{50-2}=2^{48}<10^{16}$ 因此开得下。

那么现在的问题是：考虑如何构造一个矩阵使得 所有路径的和的二进制表示可以唯一确定一个序列。

考虑归纳，假设我们对于一个长度为 $x$ 的 二进制下的 前缀已经可以确定当前位置，那么我们只需要对于 $x+1$ 这一位确定我们应该是往右还是往下。

我们可以考虑对于矩阵上的每一个位置维护出它向右是对应的二进制位取 $1$ 还是向下取 $1$，因此只需要每一位向右向下一个取 $1$ 一个取 $0$ 即可。由于我们 $x=0$ 时显然知道当前位置在 $(1, 1)$，因此后面都可以递推的构造出一条路径。

因此可以构造一个矩阵，其中偶数行都是 $0$，奇数行则考虑一个位置 $(i,j)$ 可以取 $2^{i+j-2}$，这样每一条对角线取值全部相同，而且不难发现一定对应一个新的二进制位。

最后找路径顺推即可。

考虑要是能找出 $0$ 我们就胜利了。

注意到 $4269$ 比 $2\times 2048=4096$ 还有不少余量。

然后注意到随机若干个数与一个 $x$ 或起来，结果与起来，由于每一位取到 $0$ 的概率是 $\frac{1}{2}$，因此随机 $k$ 次错误率就是 $\frac{1}{2^k}$。

考虑用这个方法求出第一个数，然后每一次往后求与当前数的或。

考虑若结果与当前数相同，显然新数是当前数的子集，集合大小至少缩小 $1$。

因此缩小 $\log n$ 次之后就没了。

那么直到缩小到 $0$，就确定了 $0$ 的位置。

然后直接扫一遍即可。

首先考虑返回值 $x$ 那个式子，显然可以化成 $(n_1 - s_1)(n_2 - s_2)$ 的形式。

那么现在就是有一堆 $0, 1, -1$，然后你要找出所有 $0$，每次可以询问两个集合和的乘积。

不难发现，我们若找到一个非 $0$ 的元素，拿它扫一遍就可以得到答案，现在的问题就是如何在 $\lfloor\log_2 n\rfloor + 1$ 次内找出一个这样的元素。

但是注意到这并不好做，于是这题神仙的地方就来了。

我们考虑用 $\mathcal{O}(n)$ 次来处理一个非 $0$ 元素，剩下的来处理出 $0$ 元素。

考虑极端情况，由于至少有两个非 $0$，因此 考虑每次询问 $i$ 和 $[1, i-1]$，注意到枚举 $i=1\sim n$ 的话，第一次出现非 $0$ 结果的位置一定是第二个非 $0$ 元素。

我们考虑后面的都可以用这个元素处理出来，那么现在就是用 $\lfloor\log_2 n\rfloor + 1$ 次找出前面那个 $1$。

发现后缀查询就行了，这个直接二分。

那么其实已经做完了。

首先考虑答案一定在 $[1, n]$ 里。

然后询问中点和中点右边那个。

若中点更小则左区间一定至少有一个答案，否则右区间。

递归即可。

考虑我们随便问两个数，正反各问一次。

显然一次是一个对较小数取模后的数，另一次就是两数中的最小值。

因此问两次取更大的那个就行。

最后剩下一个位置就是最大值。

首先不难发现，由于一定有解，那么对于 $k+1 < n$ 的问题，我们只需要前 $k+1$ 项仍然一定有解。

因此我们只需考虑 $n=k+1$ 的极端情况。

那么问 $n$ 次能问出什么也显而易见了，显然是每一个空掉然后问一次。

那么问题就是一个序列，每次告诉你随机删掉一个位置后 rank 为 $m$ 的数，保证每次删掉的位置不同。

注意到删掉 $m$ 以及以前的，返回的就是第 $m+1$ 个数，否则就是第 $m$ 个。

找更大的返回值的出现次数即可。

首先第一次不问一个 $k = 1$ 你就死了，假设我们这一次问的是一个 $x$。

考虑若 $< x$，那么就是一个范围为 $x$ 的子问题，只不过少一次询问而已。

这不难想到 dp，不妨设 $f_i$ 表示询问次数为 $i$ 所能问出的最大可行值域。

显然 $f_1=1$，注意到次数限制为 $2$ 的时候我们第一次只能问 $2$，不然交互库一旦给你一个小于你根本不知道干什么。

那你考虑第二次应该问什么，很显然答案已经被确定 $> 2$，因此你最优就是 $k=3$，此时你可以问的范围是 $[3,5]$。

因此得到 $f_2=5$。

然后考虑次数限制为 $3$ 的时候，显然第一次应该问 $6$，不然返回小并且剩下两次你确定不出来。

那么考虑第二次你可以问 $k=7$，考虑枚举边界。

首先考虑你选取的第一个边界应该满足 “区间内数的个数不超过最后一次能安全问的范围”，注意到这个范围仍然是 $7$。

因此你最后一次要问 $[7,13]$ 的数，因此你第二次询问应该有 $s_1=14$。

依此类推，有 $s_2=30, s_3=62, s_4=126, s_5=254, s_6=510,s_7=1022$，发现是指数级增长。

注意到 $f_3=2045$。

然后考虑问四次的情况，第一次显然是问 $f_3+1$，第二次就考虑后面两次用类似限制为三时的方案能到达多少，卡着那个上界即可。

询问五次显然同理。

实现时直接对这些分界点 dp 即可，那么询问时直接询问对应分界点即可。