1

Codeforces Round #844 (Div. 1 + Div. 2, based on VK Cup 2022 - Elimination Round...

 1 year ago
source link: https://www.cnblogs.com/BlankYang/p/17056807.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

Codeforces Round #844 (Div. 1 + Div. 2, based on VK Cup 2022 - Elimination Round) A-D

比赛链接

设计一条线路要贴着6个墙面走，从 (a,b)(a,b) 到 (f,g)(f,g) ，线路长度最短。

知识点：模拟。

分类取最短即可。

时间复杂度 O(1)O(1)

空间复杂度 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;}

有 nn 个人要去电影院，第 ii 个人要求至少 aiai 个其他人去他才去，问最终能有多少种选人去电影院的方案，保证每种方案选完后所有符合要求的都去了。

知识点：贪心。

从小到大排序。如果低要求的人能去就先去，保证要求高的人去之前能去的都去。如果低要求的都去不了，换成高要求的更去不了，不如先预选低要求的，看看后面能不能补上。如此，可以得到所有方案。

因为可以都不去，所以如果第一个人就有 ≥1≥1 的要求时，显然是可以都不去的。

对于 i∈[1,n)i∈[1,n) ，如果 ai≤i−1ai≤i−1 且 ai+1>iai+1>i ，说明 [1,i][1,i] 都能去，但不能直接选 i+1i+1 ，因为缺人需要继续安排后面的看看能不能补上，所以这里可以方案加一。

其他情况，[1,i+1][1,i+1] 都能去则必须安排在一个方案；[1,i+1][1,i+1] 都不能去，继续选，不能算做一个方案；[1,i][1,i] 不能去，但 [1,i+1][1,i+1] 可以去，此时要继续往后选，让这个方案能去的人都去。

最后，上述判断包括不了全都去，因此特判方案加一。

时间复杂度 O(nlogn)O(nlog⁡n)

空间复杂度 O(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;}

给出一个小写字母的字符串，每次修改可以使一个位置的字母替换成任意字母，求出修改的最少次数，使字符串的字母出现次数相同，并输出修改后的字符串。

知识点：模拟，枚举，贪心。

注意到，直接枚举最后的个数很困难，但枚举最后有几种字母很容易，因此考虑枚举最后剩多少种字母。

接下来分两步走：

  1. 确定最少要变多少位置，同时确定最少答案情况的字母种数。
  2. 通过上一步确定的信息，遍历字符串更改。

先将每个字母对应的出现次数记录好，同时保存字母本身的序号，方便排序后还能找到对应的字母。

枚举字母种数 ii ，满足 i∣ni∣n ，则最终每种字母会有 x=nix=ni 个。我们可以贪心地选择保留数量最多的前 ii 个，这些字母中数量大于 xx 是必须修改的，而后 26−i26−i 个字母，全部都需要修改。于是，就可以求出 ii 对应的修改次数 deltadelta ，枚举取最小值，并记录最终种数 divdiv 和每种数量 cntcnt，即可。

我们此时需要遍历字符串修改，因此需要通过字母序号得到字母的排名（从 00 开始）和数量，所以需要遍历第一步得到的排名对应数量和序号的数组获得。

若某个位置的字母的数量大于 cntcnt 或者排名大于等于 divdiv 并且字母的数量大于 00 则需要修改，枚举 2626 个字母找到排名小于 divdiv 且数量小于 cntcnt 的填充进去即可。

时间复杂度 O(n)O(n)

空间复杂度 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;}

给出一个数组 ai∈[1,109]ai∈[1,109] ，求出 x∈[0,1018]x∈[0,1018] 时 a1+x,⋯,an+xa1+x,⋯,an+x 中完全平方数的数量的最大值。

知识点：枚举，因数集合。

显然，必然存在 xx 使得 a+xa+x 是个完全平方数，答案至少为 11 。考虑答案为 22 及以上的情况。

我们可以先枚举所有两个数的组合 ai,aj(i<j)ai,aj(i<j) ，如果存在大于等于 22 的答案，必然会包括这些两个数的组合，因而我们可以通过两个数枚举出所有成立的 xx ，对每个 xx 在完整的数组中再跑一遍记录答案即可。

我们考虑如何得到使 ai+x,aj+xai+x,aj+x 都成为完全平方数的 xx 。设 ai+x=s2,aj+x=t2ai+x=s2,aj+x=t2 ，直接枚举 xx 复杂度是 109109 ，考虑枚举 s,ts,t 相关的数。我们可以得到 aj−ai=t2−s2=(t+s)(t−s)∈[1,109)aj−ai=t2−s2=(t+s)(t−s)∈[1,109) ， 因此我们可以枚举 t+s,t−st+s,t−s ，即枚举 aj−aiaj−ai 的因子即可，我们最多只需要枚举 109−−−√109 次即可，然后再求出 t,st,s ，就可以得到 xx 了。

时间复杂度 O(n2109−−−√)O(n2109)

空间复杂度 O(n)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;}

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK