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]);
}

526互联

CF1364E X-OR

CF1364E X-OR