CF1779E Anya's Simultaneous Exhibition 题解

· · 题解

交互题用错误的询问次数故意误导选手太恶劣了。

思路：

这是一种只需要 n-1 次操作的做法。

假设我们已经知道了所有人之间的关系，若 i 能打败 j 则连有向边 (i,j)，在此有向图中缩点，拓扑序最小的强连通分量中的点是可以获胜的。

由于任意两点间一定存在一条边，所以可以证明此强连通分量必唯一。

假设这个强连通分量的大小为 s ，那么有以下性质：此强连通分量中的点出度至少为 n-s ，而其余点出度至多为 n-s-1 。

于是不难想到用 n-1 次询问得到所有点的出度（最后一个点不用问，减一减就好了）。

得到出度 d_i 后，我们按照出度从大到小给点排序。设排完序后的点为 v_1,v_2,...v_n ，对应出度为 d_1,d_2,...d_n，满足 d_i 不升。由有关度数的性质，答案一定为 v_i 的一段前缀（很重要）。

从 corner case 开始考虑：若 d_1=n-1 ，则答案为 v_1，当我们推进到 2 号点的时候，我们知道 1 和 2 之间一定有一条边（不用管具体方向），于是可以得出这两个点向后 n-2 个点连边的数量是 d_1+d_2-1。依此类推，前 m 个点向后 n-m 个点连边的数量为 \sum_{i=1}^md_i-\frac{m(m-1)}{2}。

我们猜想，当第一次遇到前 m 个点向所有后 n-m 个点均连边的时候，就说明前 m 个点是拓扑序最小的强连通分量。即，从前向后扫描，当扫描到 v_m ，第一次发现等式 (\sum_{i=1}^{m}d_i)-\frac{m(m-1)}{2}=m(n-m) 成立时，可以得出答案是 v_1,v_2,...v_m 。

为什么？利用反证法证明。（这一段如果只是做题的话没必要看，感性理解即可）

我们认为前 m 个点形成了拓扑序最小的强连通分量。

假设实际上是前 t 个点形成了一个拓扑序最小的强连通分量。

至此，命题得证。

代码：

#include <bits/stdc++.h>
#define fuck fflush(stdout);
int n, d[255], e[255];
char s[255];
inline bool cmp(int x, int y){
  return d[x] > d[y];
}
int main(){
  scanf("%d", &n);
  for(int i = 1; i <= n - 1; ++i){
    for(int j = 1; j <= n; ++j){
      if(i == j) s[j] = '0';
      else s[j] = '1';
    }
    printf("? %d %s\n", i, s + 1);
    fuck;
    scanf("%d", &d[i]);
    e[i] = i;
    d[n] -= d[i];
  }
  e[n] = n;
  d[n] += (n - 1) * n / 2;
  std::sort(e + 1, e + n + 1, cmp);
  int ans = n, sum = 0;
  for(int i = 1; i <= n - 1; ++i){
    for(int j = 1; j <= n; ++j) s[j] = '0';
    for(int j = i + 1; j <= n; ++j) s[e[j]] = '1';
    printf("? %d %s\n", e[i], s + 1);
    fuck;
    int x;
    scanf("%d", &x);
    sum += x;
    sum -= (i - 1 - (d[e[i]] - x));
    sum += d[e[i]] + 1 - i;
    if(sum == i * (n - i)){
      ans = i;
      break;
    }
  }
  for(int i = 1; i <= n; ++i) s[i] = '0';
  for(int i = 1; i <= ans; ++i) s[e[i]] = '1';
  printf("! %s\n", s + 1);
  fuck;
  return 0;
}