2024CCPC网络赛

坐等补题

2024CCPC网络赛题解 - TJUHuangTao - 博客园

D 编码器-解码器

区间DP/矩阵乘法

区间 DP：(仍然没懂)

#define int long long
constexpr int mod = 998244353;
int dp[110][110][110];
void solve() {
    string s, t;cin >> s >> t;
    int n = s.size(), m = t.size();
    s = ' ' + s;t = ' ' + t;
    for (int i = 0;i < n;i++) {
        for (int j = 1;j <= m + 1;j++) {
            for (int t = 0;t < j;t++) {
                dp[i][j][t] = 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 < 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] << '\n';
}

E 随机过程

• $\sum _{i=0}^{m}min(n,{26}^i)$
• $\sum _{i=0}^m{26}^i\times (1-{(1-\frac{1}{{26}^i})}^n)$

J 找最小

(线性基)：zhuanlan.zhihu.com/p/718956714?utm_psn=1816223472529047553

交换 $a_i,b_i$ 后， $f(A)\to f(A)\oplus (a_i\oplus b_i)$，$f(B)\to f(B)\oplus (a_i\oplus b_i)$

得出 $C=A\oplus B$ 数组的线性基，即 $C_i$

#define int long long
void solve() {
    int n;cin >> n;
    vector<int> a(n + 1), b(n + 1);
    int fa = 0, fb = 0;
    for (int i = 1;i <= n;i++)cin >> a[i], fa ^= a[i];
    for (int i = 1;i <= n;i++)cin >> b[i], fb ^= b[i];
    vector<int> bsc(32);

    auto insert = [&](int x) {//模板类型
        for (int i = 63;i >= 0;i--) {
            if (x >> i & 1) {
                if (bsc[i] == 0) {
                    bsc[i] = x;return 1;
                }
                x ^= bsc[i];
            }
        }
        return 0;
        };
    for (int i = 1;i <= n;i++) {
        insert(a[i] ^ b[i]);
    }
    for (int i = 31;i >= 0;i--) {
        int now = max(fa, fb);
        int res = max(fa ^ bsc[i], fb ^ bsc[i]);
        if (now > res) {
            fa ^= bsc[i];fb ^= bsc[i];
        }
    }
    cout << max(fa, fb) << '\n';
}

G ：网络流