交互杂题选做

交互杂题选做

记录一些自己写过的很有意思的交互题。

另外 JOISC 中有很多有意思的交互题，很值得一做。

CF1292E Rin and The Unknown Flower

题意：交互题，你要猜一个长为 \(n\) 的由 \(CHO\) 构成的字符串，你每次可以询问一个长度为 \(t\) 的字符串，代价是 \(\dfrac{1}{t^2}\)，你会得到这个串在原串的所有出现位置，要求总代价不超过 \(\frac{7}{5}\)。

思路：首先不难想到可以直接问 \(C,H\)，不过代价是 2。我们发现，\(t\) 越大代价越小，于是我们可以问 \(CC,CH,CO\) 来代替问 \(C\)，这样代价更小。问了这些后，我们得到了除了最后一个以外所有 \(C\) 的位置。我们接着尝试求出所有 \(O\) 的位置，我们可以问 \(HO,OO\)，不问 \(OC\) 是因为 \(OC\) 只可能在开头或结尾。这样我们可以用 \(\frac{5}{4}\) 的代价问出除了开头和结尾之外的所有字符。而开头肯定不是 \(C\)，结尾肯定不是 \(O\)，于是只有4种情况，总代价是 \(\frac{5}{4}+\frac{3}{n^2}\)。

做完了吗？没有。因为当 \(n=4\) 时，这样做的代价超过了 \(\frac{7}{5}\)，我们还需特判。我们先问 \(CC,CH,CO,HO\)，如果有出现过的，那么第 3 位一定不是 \(C\)，这时有 6 种情况，总代价是 \(1+\frac{5}{16}\)。如果没有出现过，那就问 \(OO\)。如果有 \(OO\)，那一定是一段前缀，而且一定只剩 2 种情况，代价是 \(\frac{5}{4}+\frac{1}{16}\)。如果没出现过，那么就问 \(HHH\)，因为这时只剩 \(HHHC,OHHH,HHHH,OHHC\)，可以直接解决，代价是 \(\frac{5}{4}+\frac{1}{9}\)。

Coffee Varieties (hard version)

题意：给定正整数 \(n,k\)。有 \(n\) 个数 \(a_1,a_2,\dots,a_n\) 初始未知，有一队列 \(Q\) 初始为空。
每次查询你可以给出一个编号 \(x\)，交互系统会依次进行如下操作：

• 告诉你当前 \(Q\) 中是否有与 \(a_x\) 相同的数
• 将 \(a_x\) 放入 \(Q\) 的尾部
• 如果此时 \(Q\) 中元素多于 \(k\) 个，弹出队首元素

此外，你还可以重置队列，这将使得 \(Q\) 中所有元素被弹出。重置队列不算入查询次数。 现请你求出 \(a_1,a_2,\dots,a_n\) 中有多少个不同的数。要求你的查询次数不超过 \(\frac{3n^2}{2k}\)，重置次数不超过 30000。

思路：完全没想到分块，wtcl。

考虑每 \(\frac{k}{2}\) 一块，那么有一个暴力的想法就是每一对块都问一次，这样是 \(\frac{2n^2}{k}\) 的，过不去。

我们分析一下这个方法的问题。首先，重置的次数太多，而且我们其实不用考虑这些数的相对位置，因为我们只关心一个数在其他位置有没有出现过。这样我们可以变成一个完全图，要不断地用链去覆盖，覆盖方式就是形如 zig-zag ，就是 \(\forall x\in[1,\frac{n}{2}],x\rightarrow x-1\rightarrow x+1\rightarrow x-2\rightarrow x+2\cdots\) 这样覆盖，可以证明最终次数是 \(\frac{n^2}{k}\) 的。

用到的结论：\(n\) 个点（\(n\) 为偶数）的完全图最少需要用 \(\frac{n}{2}\) 条链覆盖，而且链是类似 zig-zag 的。

X-OR

题意：有一个固定的长度为 \(n\) 的排列 \(P\)，其值域为 \([0,n-1]\)，你可以进行不超过 \(4269\) 次询问得到两个数的异或和，之后你需要输出这个排列 \(P\)。

思路：只想到了比较蠢的做法。首先，如果我们找出了0，那么可以用 \(n\) 次问出所有数。然后就是考虑找一个数，然后与其他数或起来，留下或起来最小的数，然后再继续下去。

正解是从另一个角度来找0。假设当前0只能在 \(a,b\) 两个位置，那么如果新来了一个 \(c\)，考虑 \(a|c\)和 \(a|b\) 的大小关系：如果是 \(<\)，那么 \(c\) 显然不会是0；如果是 \(=\)，那么 \(a\) 显然不会是0；否则 \(a\) 不会是0。把序列 \(random_shuffle\) 一下就不会需要太多次数。最后从两个数里找 0 可以随机一个数然后判断。

Secure Password

题意：有一个固定的数组 \(A\)，同时通过数组 \(A\) 构造出数组 \(P\)，具体来讲，\(P_i\) 是 \(A\) 中除 \(A_i\) 外的所有元素的按位或。你需要在最多 \(13\) 次询问中得到最后的 \(P\) 数组。

思路：想到了类似二进制分组的做法，但是无法小于 \(2\log n\)。

正解是一个贼神仙的方法。我们把所有 13 位的、恰好有 6 位是 1 的二进制数拿出来，与序列做映射，然后询问13次，每一次询问所有第 \(i\) 位为1的位置的或和 \(w_i\)，最后每个点 \(i\) 的答案就是第 \(j\) 位为0的 \(w_j\) 的或和。这是因为保证了 1 的个数相等，那么所有 \(\ne i\) 的数至少存在一位使得在这一位上是 1 而 \(i\) 在这一位上是0 。

Madhouse (Hard version)

题意：有一个长度为 \(n\) 的由小写字母组成的字符串，你需要通过两种操作得到整个字符串：

• ? l r ——列出 \(s[l\dots r]\) 的所有子串。子串返回的顺序会被随机打乱，并且在每一个子串中，字母的顺序也会被随机打乱。
• ! s ——表示你已经得到了 \(s\)。这个操作只能进行一次，进行完后游戏立即结束。

你可以进行最多三次询问，同时所有询问中所有子串个数的总数 \(\lceil0.777(n+1)^2\rceil\)。

思路：方法是记 \(m=\left\lceil\dfrac{n}{2}\right\rceil\)，问 \([1,m],[2,m],[1,n]\)，这样可以先求出 \(s_1,s_2\cdots s_m\)。

然后考虑怎么求出后面的部分。

记 \(cnt_{i,x}\) 表示 \(x\) 在长为 \(i\) 的子串中出现次数的和，那么 \(cnt_{i+1,x}-cnt_{i,x}\) 就等于 \(x\) 在 \([i+1,n-i]\) 出现的次数，于是就可以求出来了。

Guess Divisors Count

题意：要求猜一个\(1\)到\(10^9\)之间的一个数\(X\)。

你可以询问一个数\(Q\)（\(1\le Q\le10^{18}\)），然后读取到\(\gcd(X,Q)\)。

在不多于\(22\)次猜测，得到\(X\)的因数个数。

注意：设你的答案为\(d\)，标准答案为\(ans\)，只要满足\(|ans-d|\le7\)或\(\frac12\le\frac{ans}{d}\le2\)即算正确。

思路：看到这么神奇的限制就考虑乱搞。

我们枚举每一个质数，加入优先队列，按幂次降序为第一关键字，质数大小升序为第二关键字，每次取出队首，然后询问这些质数的乘积，如果包含了这个幂次就让幂次 +1，重复 22 次，最终回答答案的两倍。

最终用到的质数最大在 850 左右，于是在这以下的部分解决了，其他的情况也可以证明是满足限制的。

Deleting Numbers

题意：已知 \(n\), 有一个未知数 \(x\) \((1\le x\le n)\)，你需要求出 \(x\) 的值。

一开始，你有一个集合 \(S=\{x|x\le n,x\in \mathbb{N^+}\}\)，你可以对这个集合执行不超过 \(10000\) 次 A、B、C 操作（总和不超过）。

A: A \(a\)，表示求出 \(S\) 中 \(a\) 的倍数的个数 \((1\le a\le n)\)

B: B \(a\)，表示求出 \(S\) 中 \(a\) 的倍数的个数并将这些 \(a\) 的倍数从 \(S\) 中删去（\(x\) 是不会被删掉的） \((2\le a\le n)\)

C: C \(a\)，表示你知道了 \(x=a\) \((1\le a\le n)\)

思路：首先有暴力的做法就是找质因数然后枚举幂次。于是可以对于每一个质数问一次，判断和没有 \(x\) 的答案是否有不同。

问题是我们无法找到最小的质因子。这里可以采用分块，每 \(\sqrt{m}\) 个就做 A 询问，就可以知道是否有最小质因子，如果有就再扫描一遍。

总次数是 \(m+2\sqrt{m}+\log n\)。

P9529 [JOISC2022] 一流团子师傅

题意：交互题。给定 \(n\times m\) 个团子，有 \(n\) 种，每种恰好 \(m\) 个。要求给出 \(m\) 个大小为 \(n\) 的集合，使得每个集合取遍所有种类，每个团子只在恰好一个集合出现。

每次询问可以给出一个团子集合，回答的是这些团子能组成至多几个那种集合。

\(n=400,m=25\)，询问次数要求 \(\le 50000\)。

思路：发现询问次数大概是 \(nm\log m\) 的，考虑怎么用这个 \(log\)。我们考虑一个一个集合填，那么每加入一个新的团子，可以二分出它可以放到哪个集合中，刚好次数就是 \(nm\log m\) 的，于是就解决了。

P6982 [NEERC2015] Jump

题意：交互题，你要猜一个长度为 \(n\) 的 01 串，你可以向询问一个 01 串，可以得到是否有 \(n\) 位或者 \(\dfrac{n}{2}\) 位对应相同，要求在 \(n+500\) 次以内问出。

思路：很厉害的随机化思想。

考虑假设我们已经知道了有 \(\dfrac{n}{2}\) 位相同，那么就可以用 \(n\) 次问出每一位是否和第一位相同，把所有取反再问一遍即可。

现在的问题是怎么知道一个有 \(\dfrac{n}{2}\) 位相同的串。答案是：直接随。

每次随出来的概率是 \(\dfrac{\binom{\dfrac{n}{2}}{n}}{2^n}\)，那么 499 次以内随出来的概率大概是 0.99997，因此有极大概率是对的。