Anya’s Simultaneous Exhibition

题意

description
交互题。一共\(n(n \leq 250)\)个人，两两之间存在胜负关系（不具有传递性），现在举行锦标赛，每次从剩下的人里选两个人决斗，胜负关系中胜者留下，负者淘汰。$ n-1 $轮后留下的被称为“候选大师“。目前不知道两两之间的胜负关系。可以进行不超过\(2n\)次询问，每次询问给出一个人\(x\)和他要挑战的人的集合\(S\)，返回\(x\)将\(S\)里每个人决斗后会胜的场次数。求那些人存在一种锦标赛的方案能够使得他们成为”候选大师“。

做法

如果这个竞赛图给定，胜者向负者连边，那么一个点能够成为”候选大师“的充要条件是能够从它走到其他所有的点。（易证不难）
如果一个点它的出度最大，那么它一定是”候选大师“。假设\(x\)的出度最大，让 \(S_1\) 是\(x\)可以直接到达的点的集合，$ S_2$ 是其他点的集合（不包括 \(x\)）。对于任意 $ y \in S $ ，假设 $ x $ 无法到达 $ y $ ，那么对于任意 $ z \in S_1 $ ， $ z $ 无法到达 $ y $ ，也就是\(y\)向\(S_1\)中每个点连边，也向\(x\)连边。\(x\)的出度是\(|S_1|\)，\(y\)的出度至少是\(|S_1|+1\)，\(y\)的出度大于\(x\)的出度，与假设矛盾。
假设一个点它是”候选大师“，那么所有出度大于它的点也一定是”候选大师“。设 \(S_1, S_2, \dots S_k\) 为按拓扑序从小到大排序的强联通分量。由于该图是一个竞赛图，所以对于 \(x \in S_i, y \in S_j, i < j\)存在从\(x\)到\(y\)的有向边。对于每个 $ x \in S_i, y \in S_j, i < j $ ，\(x\)出度比\(y\)大。
这样可以在\(2n\)次询问内解决。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 300;
int n, d[N], id[N];
bool vis[N], ans[N];

void ask(int x) {
	printf("? %d ", x);
	for(int i = 1; i <= n; i++) printf("%d", vis[i]);
	puts(""), fflush(stdout);
}
int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) vis[i] = 1, id[i] = i;
	for(int i = 1; i <= n; i++) {
		vis[i] = 0;
		ask(i); int x; scanf("%d", &x);
		d[i] = x;
		vis[i] = 1;
	}
	memset(vis, 0, sizeof(vis));
	sort(id + 1, id + n + 1, [&](int x, int y) { return d[x] > d[y]; });
	ans[id[1]] = 1, vis[id[1]] = 1;
	for(int i = 2; i <= n; i++) {
		int u = id[i];
		if(d[u] == d[id[1]]) {
			ans[u] = 1, vis[u] = 1; continue;
		}
		ask(u); int x; scanf("%d", &x);
		if(x) {
			for(int j = 1; j <= i; j++) ans[id[j]] = 1, vis[id[j]] = 1;
		}
	}
	printf("! "); for(int i = 1; i <= n; i++) printf("%d", ans[i]);
	puts(""); fflush(stdout);
	return 0;
}

更优的做法

可以在\(n-1\)次询问内解决。
假设缩点后按照拓扑序从小到大的强连通分量为\(S_1, S_2, S_k\)，那么除去强连通内部的连边外，有$ |S_1|(|S_2| + |S_3| + \dots + |S_k|) + |S_2|(|S_3| + \dots + |S_k|) + ... + |S_{k-1}||S_k| $。
显然只有 \(S_{1}\)中的元素会被统计，可以将\(S_2, S_3, \dots , S_k\) 看作一个整体，那么有 $ C(n, 2) = C(|S_1|, 2) + C(n - |S_1|, 2) + |S_1|(n - |S_1|) $ 。结合之前给出的做法，出度前\(|S_1|\)大的构成\(S_1\)，可以找到\(|S_1|\)最小的\(S_1\)。