Codeforces Educational Round 47 题解
A. Game Shopping
给定 n 个商品和 m 个钱包，每个商品价格为 a[i]，每个钱包金额为 b[j]。从第一个商品开始，依次尝试用当前可用的钱包支付。若钱包金额足够购买当前商品，则使用该钱包（金额清零），并继续下一个商品；否则跳过该商品。求最多能购买多少件商品。
思路：模拟过程，维护当前可用钱包的索引，逐个检查是否满足条件。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1010;
int n, m;
ll a[MAXN], b[MAXN];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 0; i < n; ++i) cin >> a[i];
for (int i = 0; i < m; ++i) cin >> b[i];
int wallet_idx = 0;
int count = 0;
for (int i = 0; i < n && wallet_idx < m; ++i) {
if (b[wallet_idx] >= a[i]) {
wallet_idx++;
count++;
}
}
cout << count << '\n';
return 0;
}
B. Minimum Ternary String
给定一个仅由 '0', '1', '2' 组成的字符串。允许交换相邻的 '0' 和 '1'，以及 '1' 和 '2'，但不允许 '0' 和 '2' 直接交换。目标是通过任意次操作得到字典序最小的字符串。
关键观察：由于 '1' 可以与 '0' 或 '2' 交换，因此所有 '1' 应尽可能前移；而 '0' 与 '2' 之间无法交换，故它们的相对顺序保持不变。最优策略是：将第一个 '2' 之前的所有 '0' 放在最前面，接着是全部 '1'，最后是剩余部分按原顺序排列。
#include <bits/stdc++.h>
using namespace std;
string s;
vector<char> seq;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> s;
int ones = 0;
for (char c : s) {
if (c == '1') ones++;
else seq.push_back(c);
}
bool found_two = false;
for (char c : seq) {
if (c == '2' && !found_two) {
while (ones--) cout << '1';
cout << '2';
found_two = true;
} else {
cout << c;
}
}
while (ones--) cout << '1';
cout << '\n';
return 0;
}
C. Annoying Present
有 n 个位置，初始值全为 0。进行 m 次操作，每次给出参数 x 和 d。选择一个位置 i，对每个位置 j（包括 i）执行：a[j] += x + d × dist(i, j)，其中 dist(i, j) = |i - j|。求最终所有位置平均值的最大可能值。
分析：期望最大平均值等价于总和最大。当 d ≥ 0 时，应选择端点（如左端点）使距离总和最大；当 d < 0 时，应选中位点以最小化负距离影响。利用等差数列求和公式计算总贡献，并注意使用整数运算避免浮点误差。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, m, x, d, total_sum = 0;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
while (m--) {
cin >> x >> d;
total_sum += x * n;
if (d > 0) {
total_sum += (n - 1) * n / 2 * d;
} else {
if (n % 2 == 1)
total_sum += (n / 2) * (n / 2 + 1) * d;
else
total_sum += (n / 2) * (n / 2) * d;
}
}
printf("%.8f\n", static_cast<double>(total_sum) / n);
return 0;
}
D. Relatively Prime Graph
构造一个包含 n 个节点、恰好 m 条边的连通无向图，要求每条边连接的两个节点编号互质（gcd(u, v) == 1）。若无法构造，输出 "Impossible"。
思路：若边数少于 n−1 则不可能连通。由于 1 与所有整数互质，因此可保证连通性。枚举所有满足互质条件的点对 (i, j)，直到收集到 m 条边为止。时间复杂度约为 O(n²)，在数据范围下可接受。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
int n, m, cnt;
pair<int, int> edges[MAXN];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
if (m < n - 1) {
cout << "Impossible\n";
return 0;
}
for (int i = 1; i <= n; ++i) {
for (int j = i + 1; j <= n; ++j) {
if (gcd(i, j) == 1) {
edges[cnt++] = {i, j};
if (cnt == m) break;
}
}
if (cnt == m) break;
}
if (cnt == m) {
cout << "Possible\n";
for (int i = 0; i < m; ++i)
cout << edges[i].first << ' ' << edges[i].second << '\n';
} else {
cout << "Impossible\n";
}
return 0;
}
E. Intercity Travelling
Leha 从坐标 0 出发前往 n，途中每个整数点可能有休息站（概率各为 1/2）。连续行驶 k 站时，疲劳值为 a₁, a₂, ..., aₖ。若第 k 站有休息站，则疲劳值重置为 a₁；否则继续累加。求期望疲劳值乘以 2^(n-1) 后的结果。
思路：设第 i 段（从点 i 到 i+1）的期望贡献为 E_i。可以推导出：第 i 段的期望贡献乘以 2^(n−1) 等价于 a_i × 2^(n−i) + 其他项。通过数学归纳可得最终表达式，直接预处理幂次并求和即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 998244353;
const int MAXN = 1e6 + 5;
int n;
ll a[MAXN], pow2[MAXN];
ll result = 0;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
pow2[0] = 1;
for (int i = 1; i <= n; ++i)
pow2[i] = (pow2[i-1] * 2) % MOD;
for (int i = 1; i <= n; ++i)
cin >> a[i];
result = a[n]; // 特殊情况：最后一段必然贡献一次
for (int i = 1; i < n; ++i) {
ll term = (a[i] * (pow2[n-i] + (pow2[n-i-1] * (n-i)) % MOD)) % MOD;
result = (result + term) % MOD;
}
cout << result << '\n';
return 0;
}
