A
题意
设计一条线路要贴着6个墙面走，从 ((a,b)) 到 ((f,g)) ，线路长度最短。
题解
知识点：模拟。
分类取最短即可。
时间复杂度 (O(1))
空间复杂度 (O(1))
代码
#include <bits/stdc++.h> #define ll long long using namespace std; bool solve() { int w, d, h; int a, b, f, g; cin >> w >> d >> h; cin >> a >> b >> f >> g; int ans = h + min(abs(a - f) + min(b + g, 2 * d - b - g), abs(b - g) + min(a + f, 2 * w - a - f)); 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
题意
有 (n) 个人要去电影院，第 (i) 个人要求至少 (a_i) 个其他人去他才去，问最终能有多少种选人去电影院的方案，保证每种方案选完后所有符合要求的都去了。
题解
知识点：贪心。
从小到大排序。如果低要求的人能去就先去，保证要求高的人去之前能去的都去。如果低要求的都去不了，换成高要求的更去不了，不如先预选低要求的，看看后面能不能补上。如此，可以得到所有方案。
因为可以都不去，所以如果第一个人就有 (geq 1) 的要求时，显然是可以都不去的。
对于 (iin[1,n)) ，如果 (a_i leq i-1) 且 (a_{i+1} > i) ，说明 ([1,i]) 都能去，但不能直接选 (i+1) ，因为缺人需要继续安排后面的看看能不能补上，所以这里可以方案加一。
其他情况，([1,i+1]) 都能去则必须安排在一个方案；([1,i+1]) 都不能去，继续选，不能算做一个方案；([1,i]) 不能去，但 ([1,i+1]) 可以去，此时要继续往后选，让这个方案能去的人都去。
最后，上述判断包括不了全都去，因此特判方案加一。
时间复杂度 (O(n log n))
空间复杂度 (O(n))
代码
#include <bits/stdc++.h> #define ll long long using namespace std; int a[200007]; bool solve() { int n; cin >> n; for (int i = 1;i <= n;i++) cin >> a[i]; sort(a + 1, a + n + 1); int ans = 0; if (a[1] != 0) ans++; for (int i = 1;i < n;i++) { if (a[i] <= i - 1 && a[i + 1] > i) ans++; } ans++; 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; } C
题意
给出一个小写字母的字符串，每次修改可以使一个位置的字母替换成任意字母，求出修改的最少次数，使字符串的字母出现次数相同，并输出修改后的字符串。
题解
知识点：模拟，枚举，贪心。
注意到，直接枚举最后的个数很困难，但枚举最后有几种字母很容易，因此考虑枚举最后剩多少种字母。
接下来分两步走：
- 确定最少要变多少位置，同时确定最少答案情况的字母种数。
- 通过上一步确定的信息，遍历字符串更改。
第一步：
先将每个字母对应的出现次数记录好，同时保存字母本身的序号，方便排序后还能找到对应的字母。
枚举字母种数 (i) ，满足 (i mid n) ，则最终每种字母会有 (x = dfrac{n}{i}) 个。我们可以贪心地选择保留数量最多的前 (i) 个，这些字母中数量大于 (x) 是必须修改的，而后 (26-i) 个字母，全部都需要修改。于是，就可以求出 (i) 对应的修改次数 (delta) ，枚举取最小值，并记录最终种数 $div $ 和每种数量 (cnt)，即可。
第二步：
我们此时需要遍历字符串修改，因此需要通过字母序号得到字母的排名（从 (0) 开始）和数量，所以需要遍历第一步得到的排名对应数量和序号的数组获得。
若某个位置的字母的数量大于 (cnt) 或者排名大于等于 (div) 并且字母的数量大于 (0) 则需要修改，枚举 (26) 个字母找到排名小于 (div) 且数量小于 (cnt) 的填充进去即可。
时间复杂度 (O(n))
空间复杂度 (O(n))
代码
#include <bits/stdc++.h> #define ll long long using namespace std; bool solve() { int n; cin >> n; string s; cin >> s; vector<pair<int, int>> rk(26); for (int i = 0;i < 26;i++) rk[i] = { 0,i }; for (int i = 0;i < n;i++) rk[s[i] - 'a'].first++; sort(rk.begin(), rk.end(), greater<pair<int, int>>()); int div = 1; int ans = 1e9; for (int i = 1;i <= 26;i++) { if (n % i) continue; int x = n / i; int delta = 0; for (int j = 0;j < i;j++) delta += max(0, rk[j].first - x); for (int j = i;j < 26;j++) delta += rk[j].first; if (delta < ans) { ans = delta; div = i; } } int cnt = n / div; vector<pair<int, int>> pos(26); for (int i = 0;i < 26;i++) pos[rk[i].second] = { rk[i].first,i }; for (int i = 0;i < n;i++) { if (pos[s[i] - 'a'].first > cnt || pos[s[i] - 'a'].second >= div && pos[s[i] - 'a'].first) { pos[s[i] - 'a'].first--; for (int j = 0;j < 26;j++) { if (pos[j].first < cnt && pos[j].second < div) { s[i] = j + 'a'; pos[j].first++; break; } } } } cout << ans << 'n'; 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
题意
给出一个数组 (a_i in [1,10^9]) ，求出 (x in [0, 10^{18}]) 时 (a_1+x,cdots,a_n+x) 中完全平方数的数量的最大值。
题解
知识点：枚举，因数集合。
显然，必然存在 (x) 使得 (a+x) 是个完全平方数，答案至少为 (1) 。考虑答案为 (2) 及以上的情况。
我们可以先枚举所有两个数的组合 (a_i,a_j(i<j)) ，如果存在大于等于 (2) 的答案，必然会包括这些两个数的组合，因而我们可以通过两个数枚举出所有成立的 (x) ，对每个 (x) 在完整的数组中再跑一遍记录答案即可。
我们考虑如何得到使 (a_i+x,a_j+x) 都成为完全平方数的 (x) 。设 (a_i+x = s^2,a_j+x = t^2) ，直接枚举 (x) 复杂度是 (10^9) ，考虑枚举 (s,t) 相关的数。我们可以得到 (a_j-a_i = t^2-s^2 = (t+s)(t-s) in [1,10^9)) ， 因此我们可以枚举 (t+s,t-s) ，即枚举 (a_j-a_i) 的因子即可，我们最多只需要枚举 (sqrt {10^9}) 次即可，然后再求出 (t,s) ，就可以得到 (x) 了。
时间复杂度 (O(n^2sqrt{10^9}))
空间复杂度 (O(n))
#include <bits/stdc++.h> #define ll long long using namespace std; bool issqr(ll n) { ll x = sqrt(n); return x * x == n; } int a[57]; bool solve() { int n; cin >> n; for (int i = 1;i <= n;i++) cin >> a[i]; int ans = 1; for (int i = 1;i <= n;i++) { for (int j = i + 1;j <= n;j++) { int d = a[j] - a[i]; ll x = -1; for (int k = 1;k * k <= d;k++) { if (d % k || ((d / k + k) & 1)) continue; int s = (d / k + k) / 2; int t = (d / k - k) / 2; if (1LL * s * s < a[j] || 1LL * t * t < a[i]) continue; x = 1LL * s * s - a[j]; int cnt = 0; for (int k = 1;k <= n;k++) if (issqr(a[k] + x)) cnt++; ans = max(ans, cnt); } } } 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; } 
