Solution

先说明一下，有同学可能会对题意有一些误解。经过模拟样例我们可以发现，“最多能获得的充实休假日数量”指的是充实休假日的天数，也就是说，形如 11011011 的安排应该是算

6

个“充实休假日”，而非

3

个。

整体思路：贪心。
考虑将某个

s_i

从

0

变为

1

的贡献值。分三种情况讨论：

当 $s_i$ 为形如 01010 中间的那个 0 时，将其从 $0$ 变为 $1$ 将增加 $3$ 个“充实休假日”；
当 $s_i$ 为形如 010 左侧或右侧（仅能一侧）的那个 0 时，将其从 $0$ 变为 $1$ 将增加 $2$ 个“充实休假日”；
当 $s_i$ 为形如 011 左侧或 110 右侧的那个 0 时，将其从 $0$ 变为 $1$ 将增加 $1$ 个“充实休假日”。

观察数据范围，询问次数

q \le 10^5+1

，显然要求

O(1)

查询。因此需要预处理。
贪心策略告诉我们，我们应优先考虑贡献值最高的 a 情况，其次 b，最后 c。值得注意的是，c 情况会在 a 与 b 之后考虑，因此做完 a、b 情况后剩余的 0 一定满足 c 情况的 011 或 110。
对于每一个

k

，先尽量做 a，如果还有剩余再尽量做 b，还有剩余就做 c。我的代码进行了一些小改动，精简了一下。

对于这种分类讨论题，基本都有特判的坑。此题若字符串

s

全为 0，不在讨论范围内，需要特判：如果

k=1

，不存在“充实休假日”；否则

k>1

，则“充实休假日”天数为

k

。

具体详见代码，如下。

CPP

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 1e5 + 5;
int n, q, k, cnt = 0, ans = 0, chg[N];
string s;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin >> n >> q >> s;
	s = '0' + s + '0';
	
	// spj
	bool all_zero = *max_element(s.begin(), s.end()) == '0';
	
	// init
	int t = 0;
	for (int i = 1; i <= n + 1; i++) {
		if (s[i] == '1') t++;
		else {
			if (t > 1) chg[0] += t;
			t = 0;
		}
	}
	
	// +3
	for (int i = 0; i <= n - 3; i++) {
		if (s.substr(i, 5) == "01010") {
			chg[++cnt] = 3;
			s[i + 2] = '1';
		}
	}
	
	// +2
	if (s.substr(1, 2) == "10") {
		chg[++cnt] = 2;
		s[2] = '1';
	}
	if (s.substr(n - 1, 2) == "01") {
		chg[++cnt] = 2;
		s[n - 1] = '1';
	}
	for (int i = 1; i <= n - 2; i++) {
		if (s.substr(i, 3) == "010") {
			chg[++cnt] = 2;
			s[i] = '1';
		}
	}
	
	// +1
	while (cnt < n) chg[++cnt] = 1;
	
	// get sum
	for (int i = 1; i <= cnt; i++) chg[i] += chg[i - 1];
	
	// ans
	while (q--) {
		cin >> k;
		if (all_zero && k == 1) cout << 0 << '\n';
		else cout << chg[k] << '\n';
	}
	return 0;
}

题解：P12505 「ROI 2025 Day2」充实的假期

文章操作

Solution

Thanks for your time!

相关推荐

评论

题解：P12505 「ROI 2025 Day2」充实的假期