交互题选编
I. Guess Numbers
https://codeforces.com/gym/104828/problem/I
- 求：
! x y\(x\) 和 \(y\) 的值。 - 问：
? a b返回 \(\gcd(x+a,y+b)\) 的值。 - 限制询问次数：\(200\)。
- \(0≤x,y<2^{60},0≤a,b<2^{61}\)。
点击查看题解
+0+0，+0+1，+1+0。
为了方便，询问时全局加一，避免 \(x,y\) 为 \(0\) 的情况。设前 \(k\) 位的 \(x\) 和 \(y\) 分别为 \(curx,cury\)。用 \(2^{k+1}\) 减去 \(curx\) 得到 \(a\) 的值，来让前 \(k\) 位都变成 \(0\)，从而得到第 \(k+1\) 位的情况。
避免 \(a,b\) 超出范围，对 \(x,y\) 为 \(2^{60}-1\) 的情况特判。
D. Beautiful Permutation
https://codeforces.com/contest/2162/problem/D
- 求：
! l r一个长度为 \(n\) 的排列，然后区间 \([l,r]\) 加了 \(1\)，找出 \(l,r\)。 - 已知：排列长度 \(n\)。
- 问：
1 l r返回原排列区间和，2 l r返回修改排列区间和。 - 限制询问次数：\(40\)。
- \(1≤n≤2⋅10^4\)。
点击查看题解
2 1 r 减去 1 1 r
可以得到因修改而改变的前缀和。询问 2 1 n 减去 \(n(n+1)/2\) 得到区间长度 \(L\)，通过二分得到一个值 \(x\in(0,L)\)，即可算出 \(l,r\) 的值。
D. MAD Interactive
Problem
https://codeforces.com/contest/2160/problem/D
- 求：
! a1 a2 ... a2n求一个长度为 \(2n\) 的数列，包含从 \(1\) 到 \(n\) 的每个整数恰好两次。 - 已知：数列长度 \(2n\)。
- 问：
? k j1 j2 ... jk返回集合 \(\{a_{j1},a_{j2},...,a_{jk}\}\) 中至少出现两次的最大元素（没有则值为 \(0\)）。 - 限制询问次数：\(3n\)。
- \(1≤n^2≤10^5\)。
点击查看题解
两趟进行：
- 第一趟：\(i:1\rightarrow 2n\)，初始询问集合为空，加入询问下标 \(i\)，值为 \(0\) 则加入未知集合；否则值为此位置的答案，此后询问不再包括 \(i\)，防止干扰。
- 第二趟：\(i\in\) 未知集合，每次询问 第一趟后的询问集合 + \(i\)，可以得到此位置的答案。
最多 \(3n\) 次询问。
