当前位置：首页 > article >正文

2024CCPC网络预选赛

article 2024/11/16 18:45:16

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

B. 军训 II

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

#include <bits/stdc++.h>
using namespace std;

#define int long long

const 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 long

const 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 long

const 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.kler.cn/a/303590.html