Contestant. Rank 1245. Rating +30.
A. Walking Master
题意
给定两个点 \((a, b), (c, d)\)，定义对于点 \((x, y)\) 的操作为下面任选一：
\(x + 1, y + 1\)；
\(x - 1\)
输出从 \((a, b)\) 走到 \((c, d)\) 需要的最小操作数，无解输出 \(-1\)。
思路
画个图即可。
首先，我们需要向上移动 \(d - b\)，如果 \(d - b < 0\) 就是无解。
此时，横坐标变为 \(a + d - b\)，还需要向左移动 \(a + d - b - c\)，如果 \(a + d - b - c < 0\) 也是无解。
若有解，输出 \(d - b + a + d - b - c\)。
时间复杂度：\(O(1)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
const int N = 2e5 + 10;
void solve(){
int a, b, c, d;
cin >> a >> b >> c >> d;
if(b > d || a + d - b < c) cout << -1 << '\n';
else cout << a + d - b - c + d - b << '\n';
}
signed main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t;
cin >> t;
while(t --) solve();
}就还是那么签（
B. Mex Master
题意
给定一个序列，定义答案为 由相邻数相加构成的新序列中 不在 这个序列中的 最小自然数。将序列重新排序，输出最小答案。
思路
首先，若 \(0\) 的个数小于等于 \(\frac{n + 1}{2}\)，那么一定可以在连续的两个 \(0\) 里面插入一个数，使最后的序列没有 \(0\)，答案即为 \(0\)；
其次，若整个序列的最大值大于 \(1\)，那么我们只需将 \(1\) 全部放到后面，然后第一个 \(1\) 之前不要放 \(0\) 即可，答案即为 \(1\)；
接着，若整个序列的最大值为 \(1\)，那么一定有一个 \(1\) 会和 \(0\) 去相加，使最后的序列出现 \(1\)，而因为 \(0\) 的个数足够多，我们只需在所有 \(1\) 之间插 \(0\)，就可以避免出现 \(2\)，答案即为 \(2\)；
否则，整个序列都是 \(0\)，答案一定是 \(1\)。
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
const int N = 2e5 + 10, inf = 0x3f3f3f3f3f3f3f3f;
void solve(){
int n;
cin >> n;
map<int, int> cnt;
int mx = 0;
for(int i=0;i<n;i++) {
int cur;
cin >> cur;
mx = max(mx, cur);
cnt[cur] ++;
}
if(cnt[0] <= (n + 1) / 2) cout << 0 << '\n';
else if(cnt[0] == n) cout << 1 << '\n';
else cout << (mx == 1 ? 2 : 1) << '\n';
}
signed main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t;
cin >> t;
while(t --) solve();
}一开始想错了（（
C. Sequence Master
题意
若一个长为 \(2n\) 的序列，它的所有长度为 \(n\) 的子序列满足选定的数的 乘积 与剩余数的 和 相等，那么定义其为好序列。
给定一个长为 \(2n\) 的序列 \(p\)，选定一个好序列，定义答案为 \(\sum|p_i - q_i|\)，输出答案的最小值。
思路
猜想
首先，我们来以小见大，看看 \(a, b, c, d\) 如何成为一个好序列：
拿出其中两个式子：\(ab=c+d, ac=b+d\)，我们可以得出 \(b = c\) 或 \(a = -1\)。
同理，那么我们不妨猜测整个序列都是相等的数 \(x\)，或者会有至少一个数 \(t\) 不是 \(-1\)。
讨论1
下面我们来探讨一下第一个条件的局限性：
首先，它是一定成立的，毕竟 \(x=0\) 一定是一个解，但可能出现其他解；
若只有两个数，那么 \(x\) 可以为任意值；
若只有四个数，满足 \(x ^ 2 = 2x\)，\(x = 2\)；
若超过四个数，那么我们不难发现 \(x ^ k = kx\) 对于 \(k\) 为偶数的情况下是无整数解的。
讨论2
下面我们来探讨一下第二个条件的局限性：
我们无法让大于等于 \(2\) 个数不为 \(-1\)，列式可发现无实数解；
\(n\) 为奇数的时候，依然无解；
其余情况，我们可以解得 \(t = n\)。
总结
最后，答案即为上面条件所算出的答案的最小值。
时间复杂度：\(O(2n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
const int N = 2e5 + 10, inf = 0x3f3f3f3f3f3f3f3f;
void solve(){
int n;
cin >> n;
int ans = inf;
vector<int> a(2 * n);
for(int i=0;i<2*n;i++) cin >> a[i];
if(n == 1){
if(a[0] > a[1]) swap(a[0], a[1]);
ans = a[1] - a[0];
}else if(n == 2){
ans = 0;
for(int i=0;i<4;i++) ans += abs(a[i] - 2);
}
if(n % 2 == 0){
int mn = inf, sum = 0;
for(int i=0;i<2*n;i++){
sum += abs(a[i] + 1);
mn = min(mn, abs(a[i] - n) - abs(a[i] + 1));
}
ans = min(ans, sum + mn);
}
int sum = 0;
for(int i=0;i<2*n;i++) sum += abs(a[i]);
ans = min(ans, sum);
cout << ans << '\n';
}
signed main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t;
cin >> t;
while(t --) solve();
}漏了奇数的情况，md
有更直接的做法，这里比较麻烦