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

lmz105 · 2025-05-15 15:12:20 · 题解

思路

对于所有日程均为工作日的情况，直接判断可调休天数是否大于等于 2，是的话输出调休天数，否则输出 0。

对于其他情况，我们考虑每调休一天可以增加几天充实休假日，可以发现有三种情况：

• 两天单独一天的休息日，且它们之间只需要调休一天就可以链接在一起，用字符串表示为 01010 -> 01110，这种情况可以增加 3 天。
• 单独一天的休息日，在它的前一天或后一天调休，用字符串表示为 010 -> 110 或 010 -> 011，这种情况可以增加 2 天。
• 在一段充实休假日前面或后面调休，用字符串表示为 110 -> 111 或 011 -> 111，这种情况可以增加 1 天。

接下来只要让增加的充实休假日最多就行了。

代码

#include <bits/stdc++.h>
#define ll long long
//#define rw() ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#ifndef rw()
#ifdef __linux__
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#endif

namespace FX {
    template<typename T> inline void r(T &in) {
        in = 0;
        bool bo = 0;
        char ch = getchar();
        while (!isdigit(ch)) {
            bo ^= (ch == '-');
            ch = getchar();
        }
        while (isdigit(ch))
            in = (in << 1) + (in << 3) + (ch ^ 48), ch = getchar();
        if (bo) {
            in = -in;
        }
    }
    template<typename T> inline void w(T out) {
        static char op[25];
        int top = 0;
        if (out < 0) {
            putchar('-');
            do {
                op[++top] = -(out % 10) + 48, out /= 10;
            } while (out);
        } else {
            do {
                op[++top] = out % 10 + 48, out /= 10;
            } while (out);
        }
        while (top)
            putchar(op[top--]);
        putchar('\n');
    }
    template<typename T, typename... Ts> inline void r(T &in, Ts &... ins) {
        r(in), r(ins...);
    }
    template<typename T, typename... Ts> inline void w(T out, Ts... outs) {
        w(out), w(outs...);
    }
    inline void w(const char *p) {
        while (*p) {
            putchar(*p++);
        }
    }
}
#undef getchar
#undef putchar
using namespace FX;
#endif
using namespace std;
ll n, q, la, c, cnt[6];
string s;
vector<ll>v;

int main() {
    r(n, q);
    cin >> s;
    s = "0" + s + "0";
    for (ll i = 1; i < s.size(); i++) {
        n -= (s[i] ^ 48);
        if (s[i] == s[i - 1]) {
            c++;
            s[i - 1] = '0';
        } else {
            if ((s[i - 1] ^ 48) && c > 1) {
                cnt[2] += c;
                s[i - 1] = '0';
            }
            c = 1;
        }
    }
    for (ll i = 0; i < s.size(); i++) {
        if (s[i] ^ 48) {
            v.push_back(i);
        }
    }
    if (n != s.size() - 2) {
        if (v.size()) {
            c = 1;
            for (ll i = 1; i < v.size(); i++) {
                if (v[i] == v[i - 1] + 2) {
                    c++;
                } else {
                    cnt[1] += (c >> 1);
                    cnt[0] += (c & 1);
                    c = 1;
                }
            }
            cnt[1] += (c >> 1);
            cnt[0] += (c & 1);
        }
        while (q--) {
            ll x;
            r(x);
            x = min(x, n);
            if (cnt[1] >= x) {
                w(x * 3 + cnt[2]);
            } else if (cnt[1] + cnt[0] >= x) {
                w(cnt[1] * 3 + (x - cnt[1]) * 2 + cnt[2]);
            } else {
                w(cnt[1] * 3 + cnt[0] * 2 + cnt[2] + x - cnt[1] - cnt[0]);
            }
        }
    } else {
        while (q--) {
            ll x;
            r(x);
            x = min(x, n);
            if (x > 1) {
                w(x);
            } else {
                w(0);
            }
        }
    }
    return 0;
}