能在场上想出来自己不怎么擅长的交互题还是比较开心的（
但是因为不了解 Extra Registration（在 (30) 分钟之后就不能报名了），没能交上去。。。
题面
给定一张 (n) 个点竞赛图，你可以进行一些询问，询问有两种：
- (1) (a) (b)：查询是否有从 (a) 到 (b) 的有向边。这种询问次数 (le 9n)。
- (2) (x) (k) (s_1) (s_2) (...) (s_k) : 查询 (x) 到 (s_1)，(s_2)，...，(s_k) 是否存在一条有向边。这种询问次数 (le 2n)。
最后要求输出对于所有 ((i, j))，是否有 (i) 到 (j) 的 路径。多测。
题解
众所周知把竞赛图缩点之后形成的强联通分量是一条链，如果知道了这些的强联通分量就可以得出答案。
接下来分成两个步骤：
-
找到一条包括 (1, 2, ..., n) 的路径。
-
在这条路径上进行缩点。
步骤1
考虑增量，设这条链原先是 (v_1, v_2, ..., v_k)，现在要加入点 (k)。
因此要找出一个位置 (p) （(1 le p le k + 1)） 满足有一条从 (v_{p-1}) 到 (k) 的边且有一条从 (k) 到 (v_p) 的边，并在 (p) 之前插入 (k)。
如果有从 (v_{l-1}) 到 (k) 的边且有从 (k) 到 (v_r) 的边，那么可以在 ([l, r]) 找到答案。
考虑二分答案，如果有 (k) 到 (v_{mid}) 的边那么在 ([l,mid]) 中可以找到答案，否则在 ([mid+1, r]) 种可以找到答案。
需要 (n log n) 个询问 (1)。
步骤2
设目前缩出来的链是 (S_1 o S_2 o ... o S_k)。
从后往前缩点，对于一个 (S_t) 中的点 (z)，如果存在一条从 (S_1, S_2, ..., S_{t - 1}) 的点到 (z) 的边（可以利用询问 (2) 查询），那么 (S_t) 和 (S_{t-1}) 必然在一个集合中。
不停地这样缩点即可得到最终答案。需要 (2n) 个询问 (2)。
代码
#include<bits/stdc++.h>
#define L(i, j, k) for(int i = j, i##E = k; i <= i##E; i++)
#define R(i, j, k) for(int i = j, i##E = k; i >= i##E; i--)
#define ll long long
#define pii pair<int, int>
#define db double
#define x first
#define y second
#define ull unsigned long long
#define sz(a) ((int) (a).size())
#define vi vector<int>
using namespace std;
const int N = 233;
int n, tot, v[N];
set < int > S[N];
void merge(int x, int y) {
for(int k : S[y]) S[x].insert(k);
S[y].clear();
}
int getin() {
int k;
return cin >> k, k;
}
bool check(int x, int y) {
return cout << 1 << " " << x << " " << y << endl, getin();
}
bool all[N][N], vis[N];
int rmain() {
memset(all, 0, sizeof(all)), memset(vis, 0, sizeof(vis)), memset(v, 0, sizeof(v));
L(i, 1, tot) S[i].clear();
tot = 0;
cin >> n;
L(i, 0, n - 1) {
int l = 1, r = tot + 1;
while(l < r) {
int mid = (l + r) >> 1;
if(mid == tot + 1 || check(i, v[mid])) r = mid;
else l = mid + 1;
}
R(i, tot, l) v[i + 1] = v[i];
++tot, v[l] = i;
}
L(i, 1, tot) S[i].insert(v[i]);
int now = tot;
while(now > 1) {
for(int v : S[now]) if(!vis[v]) {
cout << 2 << " " << v << " ";
int cnt = 0;
L(i, 1, now - 1) cnt += sz(S[i]);
cout << cnt << " ";
L(i, 1, now - 1) for(int u : S[i]) cout << u << " ";
cout << endl;
if(getin()) {
merge(now - 1, now);
break;
}
vis[v] = true;
}
--now;
}
L(i, 1, tot) L(j, i, tot) for(int u : S[i]) for(int v : S[j]) all[u][v] = true;
cout << 3 << endl;
L(i, 0, n - 1) {
L(j, 0, n - 1) cout << all[i][j];
cout << endl;
}
return getin(), 0;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int T;
cin >> T;
while(T--) rmain();
return 0;
}
祝大家学习愉快！