Educational Codeforces Round 96 (Rated for Div. 2) 解题报告

CF1430D String Deletion

Educational Codeforces Round 96 第四题,贪心题。

题目链接

题意翻译

\( T \) 次询问,对于每一次询问:

给定一个长度为 \( n \) 的 \( 0 1 \) 串,每次操作可以选择一个位置 \( i \),消除第 \( i \) 位,然后把 \( 01 \) 串前面连续的一串 \( 1 \) 或者是一串 \( 0 \) 消除,求最大操作数。

题解

考虑最简单的情况,即 \( s = 010101 \cdots \) 或 \( s = 101010 \cdots \),设 \( s \) 的长度为 \( \text {len} \),显然答案为 \( \left\lceil \frac { \text{len} } { 2 } \right\rceil \)。

而如果 \( 0 / 1 \) 在某些地方连续出现了多次,我们在删去这些连续的字段之前贪心地把删除单个字符的操作放在这些字段里肯定是最优的。由于我们只关心连续字段的长度,因此可以开一个数组记录每个字段的长度,对于每次操作,先删掉任意一个还未被删去的连续字段中的一个字符,再删去最前面的连续字段。前者具有单调性,维护一下就可做到 \( \Theta ( n ) \) 的复杂度。

#include <bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
inline int read(void)
{
    reg char ch = getchar();
    reg int res = 0;
    while (ch < '0' || '9' < ch)
        ch = getchar();
    while ('0' <= ch && ch <= '9')
        res = 10 * res + ch - '0', ch = getchar();
    return res;
}

const int MAXN = 2e5 + 5;

int n;
char s[MAXN];

int main(void)
{
    reg int t = read(); //读入数据组数
    while (t--)
    {
        n = read();         //读入字符串长度
        scanf("%s", s + 1); //读入字符串
        reg int cnt = 0, ans = 0, las = 0;
        for (reg int i = 1; i <= n; ++i)
            if (s[i] != s[i - 1]) //统计答案
            {
                ans += min(i - las - 1, cnt - ans);
                ++cnt, las = i; //增加块的数量
            }
        ans += min(n + 1 - las - 1, cnt - ans); //特判
        cnt -= ans;
        printf("%d\n", ans + (cnt >> 1) + (cnt & 1)); //输出结果
    }
    return 0;
}
Pages: 1 2 3 4 5 6 7 8 9