CF1364E X-OR
用这题总结一下交互题中的一种套路。
询问两个数的 or，给了我们两个想法。
- 按位确定每个数。
- 找到某些关键数，之后快速求出剩下的数。
对于第一种想法，发现询问次数比较少，很难有优秀的做法，那么就考虑第二种。
先考虑找到怎样的关键数能够更好地帮助解题。对于此题而言，如果我们可以确定 \(p_x = 0\)，那么只需用 \(x\) 与剩下的数询问即可求出整个排列。
这时候发现我们陷入了困境，重新理清思路，需要在 \(n + 174\) 次询问内找到 \(p_x = 0\)。
这时候又有另外一个套路：尝试利用询问确定一个数的值。
这个操作在本题中很简单，我们可以利用按位确定的思路，确定一位可以随机一堆数询问，确定 \(\log n\) 位还是只用随这么多个数，假设随了 \(t\) 个数，那么正确的概率为 \((1-(\frac 1 2)^t) ^ {\log n}\)。取 \(t = 15\) 可以保证较大的正确率。
确定一个数 \(p_x\) 后，以这个数为基准，尝试找到 \(0\)，考虑用其他数 \(p_k\) 与这个数询问，若问 \(p_x\)，说明 \(p_k\) 是 \(p_x\) 的真子集。于是更新 \(x\)，位数递减，最终可找到 \(0\)。
回顾一下，我们几乎完全利用套路解决了这道交互题，其关键在于：时刻变换观点，更新问题。这样一直转变陈述问题的视角的方法在许多题目中都是十分关键的。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
namespace IO {
#define isdigit(x) (x >= '0' && x <= '9')
template<typename T>
inline void read(T &x) {
x = 0; char ch = getchar(); int f = 0;
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = 1;
for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
if(f) x = -x;
}
template<typename T, typename... Rest>
inline void read(T &x, Rest&... rest) {
read(x), read(rest...);
}
template<typename T>
inline void write(T x) {
if(x < 0) putchar('-'), x = -x;
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
}
#undef isdigit
}
using namespace IO;
constexpr int N = 1 << 12;
int n;
int p[N];
int ask(int x, int y) {
printf("? %d %d\n",x + 1,y + 1);
fflush(stdout);
int res; read(res);
return res;
}
mt19937 rnd(19260817);
void get(int x) {
p[x] = 2047;
for(int i = 0; i < 15; ++i) {
int y = x;
while(y == x)
y = rnd() % n;
p[x] &= ask(x, y);
}
}
int main() {
read(n);
int x = 0;
get(0);
for(int i = 1; i < n && p[x]; ++i)
if(ask(x, i) == p[x])
get(x = i);
for(int i = 0; i < n; ++i)
if(!p[i] && i ^ x) p[i] = ask(i, x);
printf("! ");
for(int i = 0; i < n; ++i)
printf("%d ",p[i]);
}