「JOI 2013 Final」彩灯

题面链接

電飾

题解

看标签是道模拟…结果整个过程一脸懵逼 用模拟的思想想了很久也没有入手的地方,我甚至以为这道题的标签是不是贴错了,于是看了别人的代码… 我才发现这道题…是个模拟好像没有问题

题的意思很简单,就是给你一段序列,给你一次修改的机会,你能修改的一段连续的区间,使其中的 “0“ 变为 ”1“, ”1“ 变为 ”0“,让你求修改后最长的区间长度

先考虑不修改的情况,也就是以当前位为开头的最长交替列的长度

1
2
3
10
val: 1 1 0 0 1 0 1 1 1 0
Length: 1 2 1 4 3 2 1 1 2 1

推导这个显然需要 O(n^2) 这已经超出了我们的预期,我们考虑优化

由题意显然可知 修改一段连续的 0 1交题串是没有意义的 于是可得

1
2
3
10
val: 1 1 0 0 1 0 1 1 1 0
Length: 1 2 0 4 0 0 0 1 2 0

推导这个就只需要 O(n),这符合我们的预期,我们尝试加上修改的机会

尝试暴力枚举修改,要使结果变得最优,我们一段连续的区间内的0 1串必须同时修改,那么枚举所有最长交替列长度非 0 的位置进行变换,看是否当前区间的第一位和前区间的最后一位相同,当前区的最后一位和下一区间的第一位相同,如果相同,那么就加上上一个区间的最长交替列长度,用一个变量维护一下最大值就可以得到答案

考虑更简洁的方法,因为我们知道,我们只能进行一次操作,也就是说最多影响三个区间,如果当前有三个区间,第一个区间的产生是因为当前区间的最后一位与第二个区间的第一位相同,同理,第三个区间的产生是因为当前区间的第一位与第二个区间的最后一位相同,于是我们就得到了结论,对于三个连续的区间而言修改中间区间答案一定是最优的,它们所能创造的最大价值就是它们三个的和,所有我们维护最大值的时候就可以直接调用这个结论了。

于是我们就得到了如下代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
//#define fre yes

#include <cstdio>
#include <iostream>

const int MAXN_INT = 100005;
int arr[MAXN_INT], brr[MAXN_INT];

int main() {
static int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &arr[i]);
}

int l = 0, tnt = 0;
while(l < n) {
l++;
tnt++; brr[tnt] = 1;
for (;arr[l] != arr[l + 1] && l < n; l++) brr[tnt]++;
}

int ans = 0;
for (int i = 1; i <= tnt; i++) {
ans = std::max(ans, brr[i] + brr[i + 1] + brr[i + 2]);
} printf("%d\n", ans);
return 0;
}
0%