CF1465-D. Grime Zoo

题意：

一个长度为n，由\(0,1,?\)这三个字符构成的字符串，字符串中\(01\)子串贡献\(x\)值，\(10\)的子串贡献\(y\)值，现在让你把\(?\)替换成\(0\)或\(1\)，问你整个字符串的总贡献最少可以是多少？

子串是指可以通过删去字符串中的一些字符得到的字符串。不同的\(01\)或\(10\)子串只需要让他们其中的一个\(0\)或\(1\)来自字符串中不同的位置即可。

思路：

先说一个结论：当\(x<y\)的时候，无论两个\(?\)（后面分别称这两个\(?\)为\(c_l\)和\(c_r\)）之间的的\(0\)和\(1\)的数量是多少、他们是如何排列的，\(c_l\)取\(0\)，\(c_r\)取\(1\)的时候，这个字符串的总贡献一定小于\(c_l\)取\(1\)，\(c_r\)取\(0\)的时候的总贡献，即\(w_{c_l=0,c_r=1}<w_{c_l=1,c_r=0}\)。反之\(x>y\)的时候也能得到类似的结论。

证明如下：

假设\(c_l\)和\(c_r\)之间有\(n_0\)个\(0\)，\(n_1\)个\(1\)，那么当\(c_l=0,c_r=1\)的时候，这段字符串的总贡献\(w_{c_l=0,c_r=1}=(1+n_1)*x+n_0*x+w=(1+n_0+n_1)*x+w\)，其中\(w\)是\(c_l,c_r\)之间的字符产生的贡献；当\(c_l=1,c_r=0\)的时候，这段字符串的总贡献\(w_{c_l=1,c_r=0}=(1+n_0)*y+n_1*y+w=(1+n_0+n_1)*y+w\)，那么\(w_{c_l=0,c_r=1}-w_{c_l=1,c+r=0}=(1+n_0+n_1)*(x-y)=(r-l)*(x-y)\)。

从上面的式子可以得出结论：\(x<y\)时，\(w_{c_l=0,c_r=1}<w_{c_l=1,c_r=0}\)；\(x>y\)时，\(w_{c_l=0,c_r=1}>w_{c_l=1,c+r=0}\)。

这样就可以枚举字符串中的每个位置，将当前枚举的位置之前的所有\(?\)替换为\(1(或0)\)，之后所有的\(?\)替换为\(0(或1)\)，计算整个字符串的贡献，取最小的一个即可。

但是这样枚举，暴力计算总贡献，时间复杂度为\(O(n^3)\)，所以可以通过前缀和进行优化：用前缀和分别维护前\(i\)个字符和后\((n-i+1)\)个字符中\(0\)和\(1\)的数量以及分别维护前\(i\)个字符和后\((n-i+1)\)个字符构成的字符串的总贡献，这样就可以将复杂度从\(O(n^3)\)降为\(O(n)\)。具体的计算方法及实现细节见代码及代码注释。

AC代码：

这段代码使用了一些小技巧，比如将\(x<y\)和\(x>y\)这两种情况归结为一种情况、前缀和的统计方式。具体的在代码以及代码注释中有所体现。

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

typedef long long ll;

const int Maxn = 100005;

const ll INF = 0x3f3f3f3f3f3f3f3f;

char s[Maxn];

int char_pre[Maxn], char_suf[Maxn]; // 前i个字符中1的数量，后i个字符中0的数量

ll cnt_pre[Maxn], cnt_suf[Maxn];	// 前i个字符构成的愤怒值，后i个字符构成的愤怒值

void solve() {

	ll x, y;

	scanf("%s %lld %lld", s + 1, &x, &y);

	int n = strlen(s + 1);

	if (x > y) { // 让01 > 10 的情况转化为 01 < 10的情况，这样把情况做了统一

		std::swap(x, y);

		for (int i = 1; i <= n; i++) {

			if (s[i] == '1') {

				s[i] = '0';

			} else if (s[i] == '0') {

				s[i] = '1';

			}

		}

	}

	for (int i = 1; i <= n; i++) {

		if (s[i] == '1') {

		// 这里之所以记录1的数量而不是0，是因为在x<y的时候'0'和'?'是被归到一类里面，这样容易统计

			char_pre[i] = char_pre[i - 1] + 1;

			cnt_pre[i] = cnt_pre[i - 1] + (i - char_pre[i]) * x;

		} else { // 这里把'?'看作为0

			char_pre[i] = char_pre[i - 1];

			cnt_pre[i] = cnt_pre[i - 1] + char_pre[i - 1] * y;

		}

	}

	for (int i = n; i > 0; i--) {

		if (s[i] == '0') {

			char_suf[i] = char_suf[i + 1] + 1;

			cnt_suf[i] = cnt_suf[i + 1] + (n - i + 1 - char_suf[i]) * x;

		} else { // 这里把'?'看作为1

			char_suf[i] = char_suf[i + 1];

			cnt_suf[i] = cnt_suf[i + 1] + char_suf[i] * y;

		}

	}

	ll ans = INF;

	for (int i = 0; i <= n; i++) {

		// 枚举每个位置，如果这里的字符是'?'那么就会当作'0'处理（见34行）

		// 注意这里的i最开始是从0开始的，而不是从1，是为了处理第一个字符为'?'的情况

		ans = std::min(ans, cnt_pre[i] + cnt_suf[i + 1] +

			1LL * char_pre[i] * char_suf[i + 1] * y +

			1LL * (i - char_pre[i]) * (n - i - char_suf[i + 1]) * x);

		/*

		i以及i之前的字符构成的字符串（所有的?看作0）的总贡献 +

		i之后的字符构成的字符串（所有的?看作1）的总贡献 +

		i以及i之前的字符中1的数量（所有?看作0） * i之后的字符中0的数量（所有?看作1） +

		i以及i之前的字符中0的数量（所有?看作0） * i之后的字符中1的数量（所有?看作1）

		*/

	}

	printf("%lld\n", ans);

}

int main() {

	solve();

	return 0;

}

巴特西

CF1465-D. Grime Zoo

CF1465-D. Grime Zoo

题意：

一个长度为n，由\(0,1,?\)这三个字符构成的字符串，字符串中\(01\)子串贡献\(x\)值，\(10\)的子串贡献\(y\)值，现在让你把\(?\)替换成\(0\)或\(1\)，问你整个字符串的总贡献最少可以是多少？

子串是指可以通过删去字符串中的一些字符得到的字符串。不同的\(01\)或\(10\)子串只需要让他们其中的一个\(0\)或\(1\)来自字符串中不同的位置即可。

思路：

证明如下：

从上面的式子可以得出结论：\(x<y\)时，\(w_{c_l=0,c_r=1}<w_{c_l=1,c_r=0}\)；\(x>y\)时，\(w_{c_l=0,c_r=1}>w_{c_l=1,c+r=0}\)。

这样就可以枚举字符串中的每个位置，将当前枚举的位置之前的所有\(?\)替换为\(1(或0)\)，之后所有的\(?\)替换为\(0(或1)\)，计算整个字符串的贡献，取最小的一个即可。

AC代码：

这段代码使用了一些小技巧，比如将\(x<y\)和\(x>y\)这两种情况归结为一种情况、前缀和的统计方式。具体的在代码以及代码注释中有所体现。

最新文章

热门文章