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

Hello_Coding · 2025-05-23 23:30:38 · 题解

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。

具体详见代码，如下。

#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!