洛谷九月月赛『GROI-R2』不空白的画布

你有连续的 $n$ 个方格，每个方格上有一个初始颜色 $c_i$，且保证 $1\le c_i \le k$。

你可以操作至多 $m$ 次，每个操作为改变某个方格颜色，要求改变后的颜色范围仍在 $[1,k]$ 内。

我们称一个极长相同颜色连续段为一块，要求求出经过至多 $m$ 次操作后的最多块数。

输入格式

本题有多组测试数据。

第一行输入一个正整数 $T$ 表示数据组数。

对于每组测试数据，第一行输入三个正整数 $n,m,k$，表示画布的长度，坦尼尔作画的次数上限和颜色的取值范围。

第二行输入一个长度为 $n$ 的整数序列 $c$，表示画布上每个位置的初始颜色。

输出格式

对于每组测试数据，输出一行一个正整数，表示记忆碎片最多有多少个。

样例输入

样例输出

1
2

3
5

样例解释

对于第一组测试数据，坦尼尔可以将从左到右的第二个位置涂成颜色 $1$，得到 $\{c_n\}=\{2,1,2\}$，块数为 $3$。

对于第二组测试数据，坦尼尔可以将从左到右的第二个位置涂成颜色 $1$，将从左到右的第三个位置涂成颜色 $3$，得到 $\{c_n\}=\{2,1,3,2,3\}$，块数为 $5$。

数据范围

$\text{Subtask}$	$\sum n\le$	$m\le$	$k\le$	分值
$1$	$10$	$10$	$3$	$10$
$2$	$5\times 10^5$	$1$	$5\times 10^5$	$10$
$3$	$10^3$	$10^3$	$10^3$	$15$
$4$	$5\times 10^5$	$5\times 10^5$	$3$	$25$
$5$	$5\times 10^5$	$5\times 10^5$	$5\times 10^5$	$40$

对于 $100\%$ 的数据满足 $1\le n\le 5\times 10^5$，$1\le \sum n\le 5\times 10^5$，$1\le m\le n$，$3\le k \le 5\times 10^5$，$1\le c_i\le k$。

大部分的解法是把长度为奇数的块和长度为偶数的块放在两个数组里，分别排序，先把奇数块切掉，再切偶数块，偶数块考虑特殊情况特判。
比赛时也是这种想法但是写挂了,后来换一种思路，一共跑两次循环，第一次循环处理序列中块的长度大于2的部分，每次处理时三个三个的看，每三个可以加两次，第一次判断此时是不是三个，是的话就将中间一个标记为修改，此时加块数加一，用一个isMod数组记录有没有修改过，这样如果前面一个被修改过那么后面不管是什么必定是一个新的块，也要加一，这时候可以通过isMod数组判断，也是能在一个循环内完成，但是有一种情况：比如长度是7两次3 3之后（第一个循环）会剩下6 和 7上的位置没有处理，但这种情况其实就相当于长度是二的块，也就是说，第一次遍历可以解决两种情况：
1：长度大于2的部分（可能会剩余最后两个，比如长度7会剩，6就不会）；
2：长度是1的情况
那么如果还有剩下的，那么必然是长度为二的或者是大于二的数剩余二的情况，也就是满足：
c[i] == c[i - 1] && c[i] != c[i + 1]&&!isMod[i-1]
一直遍历直到遍历完或者次数用完为止

#include <bits/stdc++.h>

#define N 500105
using namespace std;

int T, n, m, k, c[N];
bitset<N> isMod;

signed main() {
    cin.tie(nullptr), cout.tie(nullptr);
    ios::sync_with_stdio(false);
    cin >> T;
    while (T--) {
        int ans = 0;
        isMod.reset();
        cin >> n >> m >> k;
        for (int i = 1; i <= n; ++i) cin >> c[i];
        for (int i = 1; i <= n; ++i) {
            if (c[i] != c[i - 1] || isMod[i - 1]) ans++;
            else if (c[i] == c[i - 1] && c[i] == c[i + 1] && m) {
                isMod[i] = true;
                ans++, --m;
            }
        }
        for (int i = 1; i <= n && m; ++i) {
            if (c[i] == c[i - 1] && c[i] != c[i + 1]&&!isMod[i-1]) 
                ans++, --m;
        }
        cout << ans << endl;
    }
    return 0;
}

这个思路感觉代码还是比较精简的，只是思维量相对比较大，实现起来比较困难

洛谷九月月赛『GROI-R2』 不空白的画布

洛谷九月月赛『GROI-R2』不空白的画布