https://codeforces.com/contest/2066/problem/A
题目大意
给出 $n$ 长的数组 $x$ 和某个隐藏的确定的数组 $y$。保证 $x_i \neq y_i, \forall i$ 且 $(x_i, y_i) \neq (x_j, y_j), \forall i \neq j$ 。对于每组数据，背后有一个隐藏的对象是以下两种之一：
- Obj A: 一个 $n$ 个点的有向图当且仅当存在有向边 $(x_i, y_i)$
- Obj B: $n$ 个点在二维平面上，每个点坐标为 $(x_i, y_i)$。
可以最多进行两次询问，每次询问给出 $i, j$：
如果是 Obj A 则返回 $i -> j$ 的最短路，不存在路径则返回 $0$。
如果是 Obj B 则返回 $|x_i - x_j| + |y_i - y_j|$。
两次询问后判断隐藏的对象是哪一种。
$3 \le n \le 2 \times 10^5$。
$1 \le x_i, y_i \le n$。
简要题解
观察：
- $x$ 不可能所有元素都相同，否则由 $x_i \neq y_i$ 则 $y_i$ 只有 $n - 1$ 个值可以选，根据鸽巢原理必有 $(x, y_i) = (x, y_j)$ 存在。
- 如果是 Obj A 则答案不会超过 $n - 1$。
- 如果是 Obj B 则答案不会为 $0$（因为点彼此不同，则其曼哈顿距离不会为 $0$）。
- 如果是 Obj A 且某值 $a$ 没有出现在 $x_i$ 中，则其到其他所有点没有边，则询问总为 $0$。
- 如果是 Obj B 则，对于 $x_i = 1, x_j = n$ 答案不会小于 $n - 1$。
有了这些观察，我们发现，如果 $x_i$ 有重复值，则必定有没有出现的值 $a$，那么我们只要用 $a$ 和任意其他 $b$ 做一次询问，则我们由观察 $3, 4$ 即可判断出是哪一种情况。
如果 $x_i$ 没有重复值，则 $x_i$ 是 $1 \sim n$ 的一个排列，则总有 $1$ 和 $n$ 存在，这时我们询问 $(1, n)$ 与 $(n, 1)$ 若任意一个小于 $n - 1$ 则根据观察 $5$ 其是 Obj A，若其大于 $n - 1$ 则其是 Obj B。
最后如何判断这两个值都是 $n - 1$ 的情况呢？注意到 $n \ge 3$，此时若 $1 -> n$ 和 $n -> 1$ 都有 $n - 1$ 条边，则总有 $2n - 2 > n, \forall n \ge 3$，即这不可能是 Obj A。
（这题写起来好烦，很容易注意到一些没用的东西，比如观察 1 似乎完全没用到！）
复杂度
$T$：$O(n)$
$S$：$O(n)$
代码实现
#include <bits/stdc++.h>
using namespace std;
int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();
using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;
template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) {
return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) {
return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z
if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
if(x<z) { y=x; x=z; } else if(y<z) y=z; }
// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());
/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/
int query(int x, int y) {
cout << "? " << x << ' ' << y << endl;
int ans; cin >> ans;
return ans;
}
void solve() {
int n; cin >> n;
vector<int> a(n);
for (int& i : a) cin >> i;
vector<vector<int>> pos(n + 1);
for (int i = 0; i < n; i++) {
pos[a[i]].push_back(i + 1);
}
bool has_two = false;
int x, y;
for (int i = 1; i <= n; i++) {
if (pos[i].size() >= 2) {
has_two = true;
}
}
if (has_two) {
for (int i = 1; i <= n; i++) {
if ((int)pos[i].size() == 0) {
x = i;
break;
}
}
for (int i = 1; i <= n; i++) {
if (i != x) {
y = i;
break;
}
}
int ans = query(x, y);
if (ans) {
cout << "! B" << endl;
} else {
cout << "! A" << endl;
}
return;
}
// all different!
for (int i = 0; i < n; i++) {
if (a[i] == 1) {
x = i + 1;
}
if (a[i] == n) {
y = i + 1;
}
}
if (query(x, y) < n - 1 || query(y, x) < n - 1) {
cout << "! A" << endl;
} else {
cout << "! B" << endl;
}
}
int main() {
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
Next: [CF] E. Vasya and Binary String - Educational Codeforces Round 59 (Rated for Div. 2)