2024CCPC网络预选赛

vp链接：Dashboard - The 2024 CCPC Online Contest - Codeforces

B. 军训 II

序列 a 从小到大排列或者从大到小排列时，不整齐度是最小的。方案数是所有相同数字的个数的排列数的乘积。如果首尾的数字不同的话，还要再乘个 2。

#include <bits/stdc++.h>
using namespace std;#define int long longconst int N = 1e3 + 10, mod = 998244353;
int n, a[N], fac[N];inline int read() {int x = 0, f = 1; char c = getchar();while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();return x * f;
}signed main() {n = read();fac[1] = 1;for (int i = 2; i <= n; i++) fac[i] = fac[i - 1] * i % mod;for (int i = 1; i <= n; i++) a[i] = read();sort(a + 1, a + n + 1);int num = 1, ans = 0, res = 1;for (int i = 1; i <= n; i++) {if (a[i] == a[i - 1]) res++;else {num = num * fac[res] % mod;res = 1;}}num = num * fac[res] % mod;if (a[1] != a[n]) num = num * 2 % mod;for (int i = 1; i <= n; i++) {for (int j = i; j <= n; j++) {ans += a[j] - a[i];}}printf("%lld %lld", ans, num % mod);return 0;
}

D. 编码器-解码器

设 $dp_{i, l, r}$ 表示考虑到 $S'_i$ ，字符串 T 的 l 到 r 区间的这个字符串在 $S'_i$ 中出现的个数。根据 $S'_i$ 的还原方式，可以得到状态转移方程为

$dp_i, l, r = \sum_{k = l - 1}^{r} dp_{i - 1, l, k} \times dp_{i - 1, k + 1, r}$

其中 $dp_{i - 1, l, k}$ 可以看作从 $S'_i$ 中左边的 $S'_{i- 1 }$ 得来的，可以看作从 $S'_i$ 中右边的 $S'_{i - 1}$ 得来的。

#include <bits/stdc++.h>
using namespace std;#define int long longconst int mod = 998244353;
int dp[105][105][105];
string s, t;signed main() {ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);cin >> s >> t;s = " " + s, t = " " + t;int n = s.size(), m = t.size();for (int i = 0; i <= n; i++)for (int j = 1; j <= m + 1; j++)for (int k = 0; k < j; k++) dp[i][j][k] = 1;for (int i = 1; i <= n; i++) {for (int l = 1; l <= m; l++) {for (int r = l; r <= m; r++) {for (int k = l - 1; k <= r; k++)dp[i][l][r] = (dp[i][l][r] + dp[i - 1][l][k] * dp[i - 1][k + 1][r]) % mod;for (int k = l - 1; k + 1 <= r; k++)if (s[i] == t[k + 1])dp[i][l][r] = (dp[i][l][r] + dp[i - 1][l][k] * dp[i - 1][k + 2][r]) % mod;}}}cout << dp[n][1][m];return 0;
}

E. 随机过程

对于最大节点数，考虑第 i 层的节点数，最多有 $min(n, 26^i)$ 个节点。

对于期望节点数，考虑计算第 i 层的节点数，每个节点不出现的概率是 $(1 - \frac{1}{26^i})^n$ ，所以出现的概率是 $1 - (1 - \frac{1}{26^i})^n$ ，那么第 i 层的期望节点数就是 $[1 - (1 - \frac{1}{26^i})^n] \cdot 26^i$ 。

#include <bits/stdc++.h>
using namespace std;#define int long longconst int mod = 998244353, N = 1e5 + 10;
int fac26[N];int qpow(int x, int k) {int res = 1LL;while (k) {if (k & 1) res = res * x % mod;x = x * x % mod;k >>= 1;}return res % mod;
}signed main() {ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);int n, m;cin >> n >> m;fac26[0] = 1;for (int i = 1; i < N; i++) fac26[i] = fac26[i - 1] * 26 % mod;int maxnum = 1, tmp = 1, ans = 1, inv26 = qpow(26, mod - 2);for (int i = 1; i <= m; i++) {tmp *= 26;if (tmp < n) maxnum = (maxnum + tmp) % mod;else {maxnum = (maxnum + (m - i + 1) * n % mod) % mod;break;}}for (int i = 1; i <= m; i++)ans += ((1 - qpow((1 - qpow(inv26, i) + mod) % mod, n) + mod) % mod) * fac26[i] % mod;cout << maxnum % mod << ' ' << ans % mod << endl;return 0;
}

K. 取沙子游戏

n 为奇数时，Alice 最开始取 1，后面都只能取 1，Alice 赢。
n 小于等于 k 时，Alice 可以一次性取完，Alice 赢。
n 为偶数时

k = 1，每人每次都只能取 1，Bob 赢。
由 1 可得，每个人期望留给对方的都是偶数，那么每个人取的都是偶数。

#include <bits/stdc++.h>
using namespace std;void solve() {int n, k;cin >> n >> k;if (n & 1 || n <= k) puts("Alice");else if (k == 1) puts("Bob");else {for (int i = 2; i <= k; i *= 2) {int tim = n / i;if (tim & 1) {puts("Alice");return;}}puts("Bob");}
}int main() {ios::sync_with_stdio(false); cin.tie(0);int t;cin >> t;while (t--) {solve();}return 0;
}

L. 网络预选赛

签到提，遍历一遍即可。

#include <bits/stdc++.h>
using namespace std;int main() {ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);int n, m;cin >> n >> m;string s[n + 2];for (int i = 1; i <= n; i++) { cin >> s[i]; s[i] = " " + s[i]; }int ans = 0;for (int i = 1; i < n; i++) {for (int j = 1; j < m; j++) {if (s[i][j] == 'c' && s[i][j + 1] == 'c' && s[i + 1][j] == 'p' && s[i + 1][j + 1] == 'c') ans++;}}cout << ans;return 0;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/423095.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！