题解：CF76C Mutation

GYHL · 2025-02-19 19:09:44 · 题解

本蒟蒻第一次写紫题题解，大佬轻喷。

洛谷传送门

codeforces传送门

题目大意：

题目写的很直白明了，这里不写了。

思路：

我们即询问有多少种删除的字符集是合法的，只需要对于每种删除的字符集计算出相邻字符产生的代价即可。

考虑对于两个位置 (i,j)，其能产生代价当旦仅当中间的字符被删光且 i,j 都没被删，考虑中间的字符集为 T，那么产生贡献的即为所有 T 的不包含 s_i,s_j 的超集 S。

首先显然要有 T 不包含 s_i,s_j。于是乎我们发现，如果我们钦定了 i，再枚举一个字符 C，那么 i 右侧第一个字符 c 才有可能产生贡献，那么有贡献的 (i,j) 就只有 O(nk) 对。

考虑对于一组 (S,a,b) 产生的贡献,其中 a,b 表示 s_i,s_j，即为不可删的字符。我们只需要对 f_s,f_{s\cup a,b} 进行一个 +m_{a,b} 的贡献，f_{s\cup \{a\}},f_{s\cup \{b\}}，进行一个 -m_{a,b} 的贡献即可。

然后我们对 f 进行高维前缀和即可得到代价数组 g。

这样的话时间复杂度为 O(n\cdot k+2^k\cdot k)。

代码：

AC记录

#include<bits/stdc++.h>

using namespace std;
const int N = 2e5 + 10, K = 25;
int n, k, T, sum, b[K], t[K], a[K][K], f[1 << K], ans;
string s;

void init() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> k >> T >> s;
    for (int i = 0; i < n; i++) {
        s[i] -= 'A';
    }
    for (int i = 0; i < n; i++) {
        sum |= 1 << s[i];
    }
    for (int i = 0; i < k; i++) {
        cin >> t[i];
    }
    for (int i = 0; i < k; i++) {
        for (int j = 0; j < k; j++) {
            cin >> a[i][j];
        }
    }
    return ;
}

int main() {
    init();
    memset(b, -1, sizeof b);
    for (int i = 0; i < k; i++) {
        f[1 << i] = t[i];
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < k; j++) {
            if (b[j] >= 0) {
                if (!((b[j] >> j) & 1) && !((b[j] >> s[i]) & 1)) {
                    f[b[j]] += a[j][s[i]];
                    f[b[j] | (1 << j)] -= a[j][s[i]];
                    f[b[j] | (1 << s[i])] -= a[j][s[i]];
                    f[b[j] | (1 << j) | (1 << s[i])] += a[j][s[i]];
                }
                b[j] |= (1 << s[i]);
            }
        }
        b[s[i]] = 0;
    }
    for (int i = 0; i < k; i++) {
        for (int j = 0; j < 1 << k; j++) {
            if ((j >> i) & 1) {
                f[j] += f[j ^ (1 << i)];
            }
        }
    }
    for (int i = 0; i < 1 << k; i++) {
        if ((i & sum) == i && f[i] <= T && i != sum) {
            ans++;
        }
    }
    cout << ans;
    return 0;
}