比赛链接
本文原文发布于博客园，如您在其他平台刷到此文，请前往博客园获得更好的阅读体验。
跳转链接：https://www.cnblogs.com/TianTianChaoFangDe/p/18766146
开题 + 补题情况
坠机场，要是赛时打了的话就又回青了，前两题很快开出来了，第三题脑残了，一开始觉得只需要构造第一个数就行了然后爽吃两发罚时。
A. Final Verdict
瞎猜的，只要所有数的和除以 (n) 得到的值为 (x) 一定有解，暂时没想到如何证明，有空再来证一证。
点击查看代码
#include <bits/stdc++.h> #define inf 2e18 #define int long long const int N = 2e5 + 9; void solve() { int n, x;std::cin >> n >> x; std::vector<int> a(n); int sum = 0; for(auto &i : a) { std::cin >> i; sum += i; } if(sum % n == 0 && sum / n == x) { std::cout << "YESn"; } else { std::cout << "NOn"; } } B. Vicious Labyrinth
题目要让所有人离 (n) 的距离最小化。
我们对 (k) 分奇偶讨论：
- 如果 (k) 为奇数，那么我们只需要把 (n) 传送到 (n - 1)，其余位置传送到 (n)，那么经过一次传送后，就只有一个人在 (n - 1) 的位置，其他人均在 (n) 的位置，接下来偶数次只会在这两个位置反复横跳，答案为 (1)。
- 如果 (k) 为偶数，那么我们把 (n - 1) 传送到 (n)，其余位置传送到 (n - 1)，这样再来一次传送后，就只有一个人在 (n - 1) 的位置，其他人均在 (n) 的位置，接下来偶数次只会在这两个位置反复横跳，答案为 (1)。
由于不能往原位置传送，所以至少有一个人无法抵达 (n)，因此答案至少为 (1)，所以上述构造为最优解。
点击查看代码
#include <bits/stdc++.h> #define inf 2e18 #define int long long const int N = 2e5 + 9; void solve() { int n, k;std::cin >> n >> k; if(k & 1) { for(int i = 1;i <= n;i ++) { if(i == n)std::cout << n - 1 << ' '; else std::cout << n << ' '; } } else { for(int i = 1;i <= n;i ++) { if(i == n - 1)std::cout << n << ' '; else std::cout << n - 1 << ' '; } } std::cout << 'n'; } C. Breach of Faith
一开始以为只要把第一项当成未知项，然后把后面的数排一下序求一下就行了，直到我搓出了这个样例 (2, 3, 4, 5)，这个样例按这个想法来的话，求出来的值是 (-2)，显然不符合题意，并且除了这种情况，还有可能导致数字重复，同样不符合题意。
对于此题，我们对题目中的式子进行变形：(0 = -a_1 + a_2 -a_3 + ... +a_{2 times n} - a_{2 times n + 1})。
我们首先对所给 (b) 数组进行一下从小到大排序，因为这样可以一减一加后是正数，更容易命中答案（其实这个也是猜的，为什么要排序具体的也没细证）。
然后，我们对上面那个式子枚举每一项作为消失项，通过对上面的新式子进行移项求出这一项的值，然后判断一下这个值是否合法，如果合法，这就是满足题意的构造。
对于移项后其他项的和，可以通过记录奇偶前缀和来快速求出。
时间复杂度：(O(n log n))，(log n) 来源于我使用了 map 记录一个数字是否出现过。
点击查看代码
#include <bits/stdc++.h> #define inf 2e18 #define int long long const int N = 2e5 + 9; void solve() { int n;std::cin >> n; std::vector<int> a(2 * n + 2), b(2 * n + 1); std::map<int, bool> vis; for(int i = 1;i <= 2 * n;i ++) { std::cin >> b[i]; vis[b[i]] = true; } sort(b.begin() + 1, b.end()); std::vector<int> preodd(2 * n + 2, 0), preeve(2 * n + 2, 0); for(int i = 1;i <= 2 * n;i ++) { if(i & 1) { preodd[i] = preodd[i - 1] + b[i]; preeve[i] = preeve[i - 1]; } else { preodd[i] = preodd[i - 1]; preeve[i] = preeve[i - 1] + b[i]; } } for(int i = 1;i <= 2 * n + 1;i ++) { int ans = 0; ans += preodd[i - 1]; ans -= preeve[i - 1]; ans += preeve[2 * n] - preeve[i - 1]; ans -= preodd[2 * n] - preodd[i - 1]; if(i & 1) { ans = -ans; } if(!vis.count(ans) && ans > 0) { for(int j = 1;j < i;j ++) { a[j] = b[j]; } a[i] = ans; for(int j = i;j <= 2 * n;j ++) { a[j + 1] = b[j]; } break; } } for(int i = 1;i <= 2 * n + 1;i ++) { std::cout << a[i] << " "; } std::cout << 'n'; } 
