比赛链接
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\) 的要求时，显然是可以都不去的。
对于 \(i\in[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^2\sqrt{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;
}
