Practice.
A. Planets
题意
对于一个序列，定义操作为下面二选一：
序列的其中一个元素减一，代价为 \(1\)；
将某一个元素改为 \(0\)，代价为 \(c\)。
现在，给定一个序列 \(a\)，根据 \(a_i\) 的值出现的次数构造新的序列 \(c\) (\(c_i\) = \(cnt_i\))，输出将序列 \(c\) 所有元素修改为 \(0\) 所需的最小代价。
思路
判断每个元素的大小与 \(c\) 的关系，答案就是 \(\displaystyle{\sum_{i=1}^n min(cnt_i, c)}\)。
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define fs first
#define sc second
const int N = 110;
void solve(){
int n, c;
cin >> n >> c;
vector<int> cnt(N);
for(int i=0;i<n;i++){
int cur;
cin >> cur;
cnt[cur] ++;
}
int ans = 0;
for(int i=0;i<N;i++){
ans += cnt[i] >= c ? c : cnt[i];
}
cout << ans << '\n';
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while(t --) solve();
}签到
B. Meeting on the Line
题意
给定 \(n\) 个人在数轴上的位置，以及每个人的等待时间 \(t_i\)，找出一个点 \(x_0\)，满足所有人中 每个人离 \(x_0\) 的距离 \(dist_i\) 与 \(t_i\) 的和 的最大值 最小。
思路
首先，如果没有 \(t\) 数组，那么这道题具有结论：\(x_0 = \frac{x_{max} + x_{min}}{2}\)。
此结论可以用类似递推的方式证明，有关归纳证明参考 这里。
那么，我们先假设 \(x_0\) 已知，来看看单独一个人的情况：
如果这个人位于 \(x_0\) 左侧，那么他需要的总时长为 \(x_0 - (x_i - t_i)\)；反之，他需要 \(- x_0 + (x_i + t_i)\)。
观察上述式子，我们不妨用 \(x_i - t_i\) 和 \(x_i + t_i\) 替换 \(x_i\)。 由于结论 \(x_0 = \frac{x_{max} + x_{min}}{2}\)，也就是 \(- x_0 + x_{max} = x_0 - x_{min}\)， 我们不难发现，因为 \(\max(x_i - t_i, x_i + t_i) = x_i + t_i, \min(x_i - t_i, x_i + t_i) = x_i - t_i\)，所以 取最大值和最小值时 一定可以满足 我们所取的值 就是我们在上述情况 \(1\) 中所提到的每个人需要的总时长。
因而，我们只需按照上述操作计算即可，复杂度是线性的。
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define fs first
#define sc second
const int N = 110, inf = 0x3f3f3f3f3f3f3f3f;
void solve(){
int n;
cin >> n;
vector<int> x(n), p(2 * n);
for(int i=0;i<n;i++) cin >> x[i];
for(int i=0;i<n;i++) {
int cur;
cin >> cur;
p[i * 2] = x[i] + cur;
p[i * 2 + 1] = x[i] - cur;
}
int mn = inf, mx = -inf;
for(int i=0;i<2*n;i++) mn = min(mn, p[i]), mx = max(mx, p[i]);
cout << (mn + mx) / 2 << ((mn + mx) % 2 == 0 ? "" : ".5") << '\n';
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while(t --) solve();
}好抽象的做法（
C. Minimum Notation
题意
给定一个由 \(0-9\) 内数字构成的字符串，定义操作为选择任意一个下标 \(i\)，删除 \(s_i\)，并将 \(\min(9, s_i + 1)\) 插入到任意位置。
输出任意次操作后，字符串的最小字典序。
思路
首先，除了 \(8, 9\)，我们不能对他元素操作多于一次。
其次，我们一定需要让最小的元素在开头。
那么，我们找出最小的元素 \(x\) 的初始位置，然后向后遍历，找出最后一个 \(x\) 出现的位置，然后从这个位置开始，继续找第二小的元素的初始位置和结束位置，如此循环直到遍历到字符串末尾。这样，我们可以取出一个子序列，这个子序列内的元素我们都不需要操作。
而对于其他的元素，我们只需将其加 \(1\) 并插入到对应的位置，让最后的字符串 "非降序" 即可。
上述的一个简单做法就是将取出的子序列对应的下标做上标记，然后从前往后遍历，将未标记的值加上 \(1\)。遍历结束后，将字符串升序排序即可。
时间复杂度：\(O(n \log n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define fs first
#define sc second
const int N = 110, inf = 0x3f3f3f3f3f3f3f3f;
void solve(){
string s;
cin >> s;
int n = s.size();
vector<vector<int>> pre(10, vector<int>(n + 1));
vector<int> ed(10, -1), cnt(10, 0);
for(int i=1;i<=n;i++){
ed[s[i - 1] - '0'] = i;
cnt[s[i - 1] - '0'] ++;
for(int j=0;j<10;j++){
pre[j][i] = pre[j][i - 1];
if(j == s[i - 1] - '0') pre[j][i] ++;
}
}
int start = 0;
string res;
for(int i=0;i<10;i++){
if(ed[i] <= start) continue;
for(int j=0;j<pre[i][ed[i]] - pre[i][start];j++) res += (char)(i + '0');
cnt[i] -= pre[i][ed[i]] - pre[i][start];
start = ed[i];
}
for(int i=0;i<10;i++){
for(int j=0;j<cnt[i];j++) res += (char)(min(9ll, i + 1) + '0');
}
sort(res.begin(), res.end());
cout << res << '\n';
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while(t --) solve();
}反而比B题简单
D. Prefixes and Suffixes
题意
给定两个长为 \(n\) 的字符串 \(a, b\)，定义操作为选择一个 \(k \in [1, n]\)，将 \(a\) 的前 \(k\) 个字符和 \(b\) 的后 \(k\) 个字符交换。
输出任意次操作后能否将两个字符串变为相同的字符串。
思路
我们先观察样例的操作特点，不难 得到下面的结论：
我们在不断交换 \(\{a_i, b_{n - i - 1}\}\) 的左右顺序，并更改着 \(i\) 的大小。
那么，我们只需统计 \(\{\min(a_i, b_{n - i - 1}), \max(a_i, b_{n - i - 1})\}\) 的个数，如果这个个数是偶数，那么我们一定可以将其安排在类似于 "回文" 的对称位置。
或者更具体地说，我们统计得到了 \(\color{rgb(149,117,205)}{\{a, c\}}\), \(\color{rgb(186,104,200)}{\{a, c\}}\), \(\color{rgb(124,179,66)}{\{b, d\}}\), \(\color{rgb(76,175,80)}{\{b, d\}}\), \(\color{rgb(0,172,193)}{\{b, d\}}\), \(\color{rgb(3,155,229)}{\{b, d\}}\)，那么我们一定能构造其为 \(\color{rgb(149,117,205)}{a} \color{rgb(124,179,66)}{b} \color{rgb(0,172,193)}{b} \color{rgb(3,155,229)}{d} \color{rgb(76,175,80)}{d} \color{rgb(186,104,200)}{c}\), \(\color{rgb(186,104,200)}{a} \color{rgb(76,175,80)}{b} \color{rgb(3,155,229)}{b} \color{rgb(0,172,193)}{d} \color{rgb(124,179,66)}{d} \color{rgb(149,117,205)}{c}\) （不唯一）。
上述例子的 "回文" 性体现在，如果我们将 \(abbddc\) 中 \(c\) 用 \(a\) 替换，\(d\) 用 \(b\) 替换，那么会得到 \(abbbba\)，这是回文的。
如果是奇数的话，显然我们只能把他放在中间，因而奇数个数的对最多只能有一个。
满足上述条件即可。
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define fs first
#define sc second
const int N = 110, inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
int n;
cin >> n;
string s1, s2;
cin >> s1 >> s2;
map<pii, int> cnt;
for(int i=0;i<n;i++){
pii now = {s1[i], s2[n - i - 1]};
if(now.fs > now.sc) swap(now.fs, now.sc);
cnt[now] ++;
}
int f = 0;
for(auto e : cnt){
if(e.sc % 2 == 1){
f ++;
if(e.fs.fs != e.fs.sc) f = -inf;
}
}
cout << (f >= 0 && f <= 1 ? "YES\n" : "NO\n");
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while(t --) solve();
}绕，但是有趣