题解：CF76C Mutation

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

题目大意：

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

思路：

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

考虑对于两个位置

(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记录

CPP

#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;
}

题解：CF76C Mutation

文章操作

题目大意：

思路：

代码：

相关推荐

评论

题解：CF76C Mutation