题解 CF1779E 【Anya's Simultaneous Exhibition】

· · 题解

给一个 官方题解 Bonus 部分中提到的“只进行 n 次询问”的做法。

先考虑建立图论模型描述这个问题：对于 u, v 两个人，如果 u 战胜 v，则连边 u \to v，反之连边 v \to u。这样建立的图就是一个 竞赛图。

这个图显然有如下几个性质：

引理 1：如果一个人 u 是候选冠军，则对于任意一个人 v，都存在一条 u 到 v 的路径。\square

引理 2：所有候选冠军构成一个强连通分量。\square

考虑对这个竞赛图的所有强连通分量缩点，有结论：

定理 1：对竞赛图缩点后，形成的图是一条链的传递闭包。即，链中的每个点向后面的每个点都连一条边，且 \forall u, v，如果 u 在 v 前面，则 u 中所有点的入度都小于 v 中所有点的入度。

证明：

首先明确一点，竞赛图缩点后仍然是竞赛图，因此任意两个强连通分量之间必定存在一条边相连。

如果图上只有一个或两个强连通分量，则定理显然成立。

否则，图上至少有三个强连通分量。考虑图上任意的三个强连通分量 u, v, w，首先，它们之间的连边不可能成环（否则它们就能组成更大的强连通分量了），从而只能形成定理 1 所描述的情况。

\square

因此，缩点后链上的第一个点对应的强连通分量就是我们要求的候选冠军的集合。

有了前面这些结论，已经可以推出官方题解所给的 2n 次询问的做法了，这里不展开叙述。为了实现 n 次询问，接下来给出一个定理。

定理 2：在竞赛图中，将所有点按入度升序排序后，若前 n 个点的入度和为 \dfrac{n(n-1)}{2}，且不存在更小的 n 满足这一条件，则这 n 个点构成一个强连通分量。

证明：

考虑反证法。

  2. \exists m > n$，前 $m$ 个点构成一个强连通分量。前 $n$ 个点之间的两两连边已经让这些点的入度和等于 $\dfrac{n(n - 1)}{2}$，因此并不存在前 $n$ 个点之外的其他点向前 $n$ 个点连边的情况，从而前 $m$ 个点并不是强连通的。$\square

（这个结论在 CF1498E 中也有用到）

因此我们得到如下算法：

  1. 对于点 i，询问其与其他所有点的对战情况，得到 i 的入度 in_i；
  2. 将所有点按入度升序排序；
  3. 找到最小的 m 使得 \sum_{i = 1}^m in_i = \dfrac{m(m-1)}{2}，则前 m 个点即为所求。

这样就只用 n 次询问就完成任务了。当然最后一次询问事实上也是多余的，只要根据前面所有点的入度和就能算出最后一个点的入度，这样就是 n - 1 次询问了（虽然意义不大）。

// Problem: E. Anya's Simultaneous Exhibition
// Contest: Codeforces - Hello 2023
// URL: https://codeforces.com/contest/1779/problem/E
// Author : StudyingFather
// Site : https://studyingfather.com
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <algorithm>
#include <iostream>
using namespace std;
int in[305], id[305], ans[305];
int main() {
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cout << '?' << ' ' << i << ' ';
    for (int j = 1; j <= n; j++) cout << (i == j ? 0 : 1);
    cout << endl;
    cin >> in[i];
    in[i] = n - 1 - in[i]; // in + out = n - 1
    id[i] = i;
  }
  sort(id + 1, id + n + 1, [](int x, int y) { return in[x] < in[y]; });
  int sum = 0;
  for (int i = 1; i <= n; i++) {
    sum += in[id[i]];
    if (sum == i * (i - 1) / 2) {
      for (int j = 1; j <= i; j++) ans[id[j]] = 1;
      break;
    }
  }
  cout << "! ";
  for (int i = 1; i <= n; i++) cout << ans[i];
  cout << endl;
  return 0;
}