A
题解
知识点：贪心。
对于一个轨道，要么一次性清理，要么一个一个清理。显然，如果行星个数大于直接清理的花费，那么选择直接清理，否则一个一个清理。即 ∑min(c,cnt[i])，其中 cnt[i] 表示轨道 i 的行星个数。
时间复杂度 O(n)
空间复杂度 O(1)
代码
#include #define ll long long using namespace std; int cnt[107]; bool solve() { int n, c; cin >> n >> c; memset(cnt, 0, sizeof(cnt)); for (int i = 1;i <= n;i++) { int x; cin >> x; cnt[x]++; } int ans = 0; for (int i = 1;i <= 100;i++) ans += min(c, cnt[i]); cout << ans << '\n'; return true; } int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t = 1; cin >> t; while (t--) { if (!solve()) cout << -1 << '\n'; } return 0; }
B
题解
方法一
知识点：三分。
按位置从小到大排列，显然约会花费是一个关于 x0 的单谷函数，因此可以三分位置。
由于位置最大有 108 ，但点的个数只有 105 ，考虑先用 map 存储有序对 (x,t) ，其中 t 是位置 x 的人最大打扮时间，因为比这个时间少的一定不影响结果。遍历结束以后把 map 内容移到 vector 中用 pair 存储用以三分，check 函数则只要遍历一遍 vector 即可。
时间复杂度 O(nlogmax(eps))
空间复杂度 O(n)
方法二
知识点：贪心。
把 t 等效进位置，如果 xi 在 x0 左侧，则等效位置是 xi−t ;如果 xi 在 x0 右侧，则等效位置是 xi+t 。
所有点的左侧等效位置最左的位置，就是等效区间左端点；所有点的右侧等效位置最右的位置就是等效区间的右端点。
如果等效区间的左右端点来自于不同两点的等效点，那么等效区间的中点一定在这两点之间，否则原来的点必有一个能覆盖另一个点，等效区间的左右端点就属于同一个点的等效点。
时间复杂度 O(n)
空间复杂度 O(n)
代码
方法一
#include #define ll long long using namespace std; int x[100007]; map<int, int> mp; vector<pair<int, int>> v; double check(double mid) { double mx = 0; for (auto [i, j] : v) { mx = max(mx, abs(i - mid) + j); } return mx; } bool solve() { mp.clear(); v.clear(); int n; cin >> n; for (int i = 1;i <= n;i++) { cin >> x[i]; mp[x[i]] = 0; } for (int i = 1;i <= n;i++) { int T; cin >> T; mp[x[i]] = max(mp[x[i]], T); } for (auto [i, j] : mp) { v.push_back({ i,j }); } double l = 0, r = v.back().first; while (abs(r - l) >= 1e-7) { double mid1 = l + (r - l) / 3; double mid2 = r - (r - l) / 3; if (check(mid1) <= check(mid2)) r = mid2; else l = mid1; } cout << fixed << setprecision(10) << l << '\n'; return true; } int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t = 1; cin >> t; while (t--) { if (!solve()) cout << -1 << '\n'; } return 0; }
方法二
#include #define ll long long using namespace std; int x[100007], T[100007]; bool solve() { int n; cin >> n; int l = 1e9, r = 0; for (int i = 1;i <= n;i++) cin >> x[i]; for (int i = 1;i <= n;i++) cin >> T[i]; for (int i = 1;i <= n;i++) { l = min(x[i] - T[i], l);///最左侧等效点 r = max(x[i] + T[i], r);///最右侧等效点 } cout << fixed << setprecision(8) << (l + r) / 2.0 << '\n'; return true; } int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t = 1; cin >> t; while (t--) { if (!solve()) cout << -1 << '\n'; } return 0; }
C
题解
知识点：贪心。
因为要字典序最小，那么一个数字他后面没有更小的数字则可以保留，其他都应该删除，所以从右往左找一个合法的保留序列，其他的数字加一，并且都是位置随意的，于是可以插入到保留下来的序列，并使插入后的序列是从小到大字典序最小的排列。因此直接把保留序列外的数字加一以后，对整个序列排序即可。
也可以直接桶排序。
时间复杂度 O(nlogn)
空间复杂度 O(n)
代码
#include #define ll long long using namespace std; bool solve() { string s; cin >> s; int mi = 10; for (int i = s.size() - 1;i >= 0;i--) { if (s[i] - '0' <= mi) mi = s[i] - '0'; else s[i] = min(s[i] + 1, '9' + 0); } sort(s.begin(), s.end()); cout << s << '\n'; return true; } int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t = 1; cin >> t; while (t--) { if (!solve()) cout << -1 << '\n'; } return 0; }
D
题解
知识点：构造。
注意到操作不会改变无序对 (ai,bn−i+1) 数量以及种类。
引理：a=b ，当且仅当无序对是回文的。
充分性：
当 a=b 时，如果 i 处存在一组无序对 (x,y) ，则必然会在 n−i+1 产生相同一组无序对 (y,x) ，除非当 n 为奇数时，可以在中间产生一个元素相同的无序对 (x,x) ，因此 a=b 时，无序对必然成回文状。
必要性：
当无序对是回文的，则第 i 组无序对 (x,y) 可以对应第 n−i+1 组无序对 (y,x) ，即 ai=bi ,所以 a=b 。
充要条件：YES 当且仅当无序对 (ai,bn−i+1) 中元素不同的无序对有偶数个，元素相同的无序对仅在 n 为奇数时至多 1 种有奇数个。
充分性：
根据引理，显然满足右边条件。
必要性：
显然没有任何限制时，给出的无序对条件能排列成回文的，现在尝试证明其必然可构造无序对回文。
注意到操作 k=i 可以使得 a[1⋯k] 和 b[k⋯n] 交换位置，即 (a[k],b[n−k+1]) 这一组无序对被置换到了 1 号位置，同时 (a[1],b[n]) 这一组无序对被置换到了 i 号位置，但这不会改变 a[k+1⋯n] 和 b[1⋯k−1] 的顺序，即第 k+1 到 n 组无序对及其实际元素顺序没有改变。因此，如果我们想要将无序对通过操作变成一个我们想要的顺序，可以从右往左构造。
假设 i+1 到 n 的无序对都安排好了，现在 i 号位置想要 j(j≤i) 号位置的无序对时，可以先 k=j ，将 j 号替换到 1 号，然后 k=i ，将 1 号替换 i 号，过程中 i+1⋯n 的无序对不会改变，包括实际元素顺序。
上述操作最后结果是无序对 j 替换到 i ，且 j 号无序对元素的实际顺序不会改变。但如果我们希望实际元素的顺序也发生改变，我们可以加一个步骤 k=1 在中间，即通过 k=j,k=1,k=i 替换 i 号后的 j 号元素实际顺序与原来是相反的，这也是为什么我们只需要知道无序对顺序即可，因为元素实际顺序是可以随时改变的。
通过上述操作我们可以实现无序对的任意排列，以及无序对实际元素的顺序。因此无序对满足回文条件时，必然可以构造出无序对回文。于是根据引理，得到 a=b 。
时间复杂度 O(n)
空间复杂度 O(n)
代码
#include #define ll long long using namespace std; string a, b; int cnt[26][26]; bool solve() { memset(cnt, 0, sizeof(cnt)); int n; cin >> n; string a, b; cin >> a >> b; for (int i = 0;i < n;i++) { int x = a[i] - 'a', y = b[n - 1 - i] - 'a'; if (x > y) swap(x, y); cnt[x][y]++; } bool ok = true; int esum = 0; for (int i = 0;i < 26;i++) { for (int j = i;j < 26;j++) { if (i == j) esum += cnt[i][j] & 1; else ok &= !(cnt[i][j] & 1); } } if (ok && esum <= (n & 1)) cout << "YES" << '\n'; else cout << "NO" << '\n'; return true; } int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t = 1; cin >> t; while (t--) { if (!solve()) cout << -1 << '\n'; } return 0; }