比赛链接:https://codeforces.com/contest/1397
A. Juggling Letters
题意
给出 $n$ 个字符串,可在字符串间任意移动字母,问最终能否使这 $n$ 个字符串相同。
题解
如果可以,因为 $n$ 个字符串相同,所以每个字母的数量一定是 $n$ 的倍数。
代码
#include <bits/stdc++.h> using namespace std; void solve() { int n; cin >> n; vector<int> cnt(26); for (int i = 0; i < n; i++) { string s; cin >> s; for (char c : s) ++cnt[c - 'a']; } bool ok = all_of(cnt.begin(), cnt.end(), [&](int x) { return x % n == 0; }); cout << (ok ? "YES" : "NO") << " "; } int main() { int t; cin >> t; while (t--) solve(); }
B. Power Sequence
题意
给出一个大小为 $n$ 的数组 $a$,允许操作如下:
- 重排数组,无花费
- 将一个数 $+1$ 或 $-1$,花费为 $1$
找出使得数组 $a$ 满足 $a_i = c^i$ 的最小花费。
题解
指数增长,枚举 $c$ 即可。
因为 $3 le n le 10^5, 1 le a_i le 10^9$,所以可以将上限设为 $10^{14}$,一旦有 $c^i$ 大于这个上限就停止枚举。
代码
#include <bits/stdc++.h> using ll = long long; using namespace std; int main() { int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; i++) cin >> a[i]; sort(a.begin(), a.end()); ll ans = LLONG_MAX; for (int c = 1; true; c++) { bool too_big = false; ll change = 0; ll cur = 1; for (int i = 0; i < n; i++) { change += abs(a[i] - cur); cur *= c; if (cur > 1e14) { too_big = true; break; } } if (too_big) break; ans = min(ans, change); } cout << ans << " "; }
C. Multiples of Length
题意
给出一个大小为 $n$ 的数组 $a$,操作如下:
- 选择一个区间,给其中的每个数加上区间长度的一个倍数
共要进行 $3$ 次操作,找出使得数组 $a$ 满足 $a_i = 0$ 的一种方案。
题解
$gcd(n,n-1)=1$,所以选择一次长为 $n$ 的区间,两次长为 $n - 1$ 的区间。
代码
#include <bits/stdc++.h> using ll = long long; using namespace std; int main() { int n; cin >> n; vector<ll> a(n); for (int i = 0; i < n; i++) cin >> a[i]; if (n == 1) { cout << 1 << ' ' << 1 << " " << -a[0] << " " << 1 << ' ' << 1 << " " << 0 << " " << 1 << ' ' << 1 << " " << 0 << " "; return 0; } cout << 1 << ' ' << n << " "; for (int i = 0; i < n; i++) { cout << -a[i] * n << " "[i == n - 1]; } cout << 1 << ' ' << n - 1 << " "; for (int i = 0; i < n - 1; i++) { cout << a[i] * (n - 1) << " "[i == n - 2]; } cout << 2 << ' ' << n << " "; for (int i = 1; i < n; i++) { cout << a[i] * (i == n - 1 ? n - 1 : 0) << " "[i == n - 1]; } }
D. Stoned Game
题意
有 $n$ 堆石子,两个人每次从另一个人没取过的石子堆中拿走一颗石子,无法再取者败,判断最终胜者。
代码
#include <bits/stdc++.h> using namespace std; void solve() { int n; cin >> n; vector<int> a(n); int sum = 0; for (int i = 0; i < n; i++) { cin >> a[i]; sum += a[i]; } sort(a.begin(), a.end()); if (a.back() > sum - a.back()) cout << "T" << " "; else cout << (sum & 1 ? "T" : "HL") << " "; } int main() { int t; cin >> t; while (t--) solve(); }