Educational Codeforces Round 177 (Rated for Div. 2)
A. Cloudberry Jam卡累利阿森林中最珍贵的浆果是云莓。为了用云莓制成果酱，我们需要取等量的云莓和糖，然后烹煮。也就是说，如果你有 \(2\) 公斤的云莓，你需要 \(2\) 公斤的糖。然而，使用 \(2\) 公斤云莓和 \(2\) 公斤糖制作出的果酱，并不会得到 \(4\) 公斤的果酱，而仅仅只有 3 公斤，因为在烹煮过程中会有部分果酱蒸发。具体来说，在标准烹煮过程中，果酱会蒸发掉四分之一（25%）。为了制作 \(n\) 个每个重 \(3\) 公斤的果酱罐头，需要多少公斤的云莓？
\(n \leq 10^8\)
每两公斤云莓生产三公斤果酱，答案就是 \(n \times 2\)。
代码#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef pair<int, pair<int, int> > piii;
typedef long long ll;
const int N = 2000086, MOD = 998244353, INF = 0x3f3f3f3f;
ll res;
int n, m, cnt, w;
int main() {
int T;
cin >> T;
while (T--) {
cin >> n;
printf("%d\n", n << 1);
}
return 0;
}C. Disappearing Permutation
给定一个从 \(1\) 到 \(n\) 的整数排列，这是一种大小为 \(n\) 的数组，其中每个整数从 \(1\) 到 \(n\) 恰好出现一次。现在给定一个排列 \(p\)，它包含从 \(1\) 到 \(n\) 的整数。你需要处理 \(n\) 个查询。
在第 \(i\) 个查询中，你将 \(p_{d_i}\) 替换为 \(0\)。每个元素恰好被替换为 \(0\) 一次。查询中所做的更改是累积的，也就是说，在第 \(i\) 个查询之后，所有的整数 \(p_{d_1}, p_{d_2}, \ldots, p_{d_i}\) 都变为零。
每次查询之后，你需要找出修复数组所需的最小操作次数；换句话说，将当前数组转换为任意从 \(1\) 到 \(n\) 的排列（可能转换为原排列 \(p\)，也可能转换为其他排列）。
你可以执行的修复数组的操作是：
选择一个整数 \(i\)（\(1\le i\le n\)），将数组的第 \(i\) 个元素替换为 \(i\)。
注意，每个查询的答案都是独立计算的，也就是说，你实际上并不执行任何操作，只需要计算出最小的操作次数即可。
\(n \leq 10^5\)
对每个位置 \(i\) 向 \(p_i\) 连一条有向边，这样形成的图会分成若干不相交的环。某个点 \(i\) 如果被替换成了 \(0\) 或者其他数，那么数组就会缺失 \(p_i\)，\(i\) 的出边指向的点 \(p_i\) 就必须被操作。对于每一个环，如果环中存在至少一个点被替换成了 \(0\)，那么环上所有点都需要进行操作。
代码#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef pair<int, pair<int, int> > piii;
typedef long long ll;
const int N = 2000086, MOD = 998244353, INF = 0x3f3f3f3f;
ll res;
int n, m, cnt, w;
ll x;
void solve() {
ll sum = 0, res = 0;
for (int i = 1; i < n + 1; i++) sum += w;
ll r = sum * m;
for (int i = 1; i <= m; i++) {
if (r - sum + w >= x) res += n;
else {
for (int j = 1; j <= n; j++) {
res += r >= x;
r -= w;
}
break;
}
r -= sum;
}
printf("%lld\n", res);
}
int main() {
int T;
cin >> T;
while (T--) {
cin >> n >> m >> x;
for (int i = 1; i < n + 1; i++) scanf("%d", w + i);
solve();
}
return 0;
}D. Even String
你想构造一个由小写拉丁字母组成的字符串 \(s\)，使得满足以下条件：
对于所有满足 \(s_i=s_j\) 的索引对 \(i\) 和 \(j\)，它们之间的差值是偶数，即 \(|i-j|\mod2=0\)。
构造任意字符串太简单了，所以你会得到一个包含 26 个数字的数组 \(c\) —— 表示字符串 \(s\) 中每个字母要求出现的次数。也就是说，对于每个 \(i\in\)，拉丁字母表中的第 \(i\) 个字母应恰好出现 \(c_i\) 次。
你的任务是计算满足所有这些条件的不同字符串 \(s\) 的数量。由于答案可能非常大，请将结果对 \(998244353\) 取模。
\(c \leq 5 \times 10^5\)
题目的限制等价于对于每一个字符，要么所有都放到奇数位置，要么所有都放到偶数位置。考虑对每一个字符放置位置的奇偶性分配好后，令 \(N_{odd}\) 为奇数位置数量，\(N_{even}\) 为偶数位置数量，\(S\) 为选择放在奇数位置的字符的集合，不同的字符串个数有 \(\frac{N_{\mathrm{odd}}!}{\prod_{i\in S} c_i!} \times \frac{N_{\mathrm{even}}!}{\prod_{i\notin S} c_i!} = \frac{N_{\mathrm{odd}}! \cdot N_{\mathrm{even}}!}{\prod_{i=1}^{26} c_i!}\) 个。合法的奇偶位置分配方案数可以通过 dp 计算。
代码#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef pair<int, pair<int, int> > piii;
typedef long long ll;
const int N = 2000086, MOD = 998244353, INF = 0x3f3f3f3f;
ll res;
int n, m, cnt, w;
int d;
bool st;
void dfs(int r) {
res++;
st = 1;
if (!st]) dfs(w);
}
void solve() {
memset(st, 0, sizeof(bool) * (n + 10));
res = 0;
for (int i = 1; i < n + 1; i++) {
if (!st]) dfs(d);
printf("%lld ", res);
}
puts("");
}
int main() {
int T;
cin >> T;
while (T--) {
cin >> n;
for (int i = 1; i < n + 1; i++) scanf("%d", w + i);
for (int i = 1; i < n + 1; i++) scanf("%d", d + i);
solve();
}
return 0;
}
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]