背景

光速卡D，前三道其实都不难

A题： Make All Equal

题意

每次可以选定两个相邻的元素，删除其中任意一个，问使得数组中元素全都相等的最小操作次数

思路

大水题，我们只需要找到数组中出现最多的元素，将其他的删除即可

代码

inline void solve() {int n; cin >> n;map<int, int> cnt;int maxv = 0;for (int i = 1; i <= n; i ++ ) {int x; cin >> x;cnt[x] += 1;if (cnt[x] > maxv) maxv = cnt[x];}cout << n - maxv << endl;return;
}

B题：Generate Permutation

题意

给定一个大小为n，值全都为-1的数组a。两台机器分别从左往右和从右往左对数组进行扫描。

对于一次扫描称为一次操作

两者在扫描的过程中，可以将-1更改为当前数组中未出现的最小正整数，问能否构造出一个排列p，使得两台机器在构造排列p时花费的操作次数相同

思路

无论如何，都是要先将p中的1先整出来的

所以，对于偶数大小的数组，这个1该放哪里呢？其次，放了以后，对于2来说，无论放哪，两台机器中总有一台要减少一次操作次数，3，4...同理。这样奇数次（从2开始，到n结束），不可能操作次数相等

那么就只有奇数大小的情况了。

贪心地想，我们肯定将1放中间

记2放在1的右边（左边也行）

那么3该放哪呢？1的左边

然后再考虑4和5，发现只要将4放到右边，5放到左边即可

3 1 2

5 3 1 2 4

代码

inline void solve() {int n; cin >> n;if (n % 2 == 0) cout << -1 << endl;else {for (int i = n; i >= 1; i -= 2) {cout << i << ' ';}for (int i = 2; i < n; i += 2) {cout << i << ' ';}cout << endl;}return;
}

C题：Guess The Tree

题意

交互题，每次可以询问两个点a和b，会告知使得|d(a,x)-d(b,x)|最小的x

思路

按照题目要求，我们要确定n-1条边，那我们该如何利用交互来确定边呢？

只能是ask(a,b)返回a和b其中一个的情况，我们才可以知道a和b有连边

那么再看要求，15n次询问，这个15就很灵性，最简单的想法是2的15次，这个比1000大

这么想，如果它是连成一条的，树的直径最大是1000，每次告知的信息相当于就是在做一次二分一样的

所以对于某个点，我们一直进行ask，把结果拿来一直ask即可

代码

int ask(int a, int b) {cout << "? " << a << ' ' << b << endl;cout.flush();int res; cin >> res;return res;
}
inline void solve() {int n; cin >> n;vector<PII> res;for (int i = 2; i <= n; i ++ ) {int t = 1;for (int j = 0; j < 15; j ++ ) {t = ask(t, i);}res.push_back({t, i});}cout << "! ";for (auto [x, y] : res) {cout << x << ' ' << y << ' ';}cout.flush();return;
}