https://codeforces.com/contest/2060/problem/C
题目大意
给出 $n \ (2 \le n \le 2 \times 10^5)$ （且为偶数）和 $k \ (1 \le k \le 2n)$。Alice 和 Bob 轮流选数，每轮 Alice 先选，Bob 后选，如果选到的数的和为 $k$ 则加 $1$ 分。Bob 希望分尽量大，Alice 希望分尽量小。问最后能有多少分。
简要题解
只是套了一层博弈的壳。首先所有加和等于 $k$ 的可以看成一些对子。对于 $a + b = k$，如果 $a \neq b$ 则对子的数量最多为 $\min(cnt[a], cnt[b])$。如果 $a = b$ 则对子数量最多为 $\lfloor \frac{cnt[a]}{2} \rfloor$。显然最后答案是这个数，因为无法取到更多，而每次 Alice 如果取这些对子里的，那么 Bob 就取对应的，如果 Alice 取对子外的，Bob 就也任取对子外的即可。
复杂度
$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
*/
void solve() {
int n, k; cin >> n >> k;
int x;
vector<int> cnt(n * 2 + 1);
for (int i = 0; i < n; i++) {
cin >> x;
cnt[x]++;
}
int ans = 0;
for (int i = 0; i < k / 2; i++) {
ans += min(cnt[i], cnt[k - i]);
}
if (k % 2 == 0) {
ans += cnt[k / 2] / 2;
} else {
ans += min(cnt[k / 2], cnt[k / 2 + 1]);
}
cout << ans << '\n';
}
int main() {
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
Next: [CF] E. Graph Composition - Codeforces Round 998 (Div. 3)