codeforces contest 1082 E. Increasing Frequency

Posted on | In , | Comments:
| 14k | 12 mins.

原题在这

这题搞了好久，大意是讲给一个长为n的数串，让其中某一个子区间的数都+k，然后使得整个串里等于c的数个数尽可能大，问最大多少

串里的数范围挺宽的，先想这个+k，实际上就是尽可能多的把不是c的变成c，尽量少把c变成其它的，要注意这里k选定了以后，能变成c的数就只有是c-k

由于串里的c一开始的数量是确定的，于是最终c的数量=原来c的数量+(变成了c的数的数量-变成了别的数的c的数量)，其实我们就是要求括号里的最大值

dp

代码是我看了别人的提交后写的，感觉这里能想到dp的都是神仙吧，(这都什么人呀!!!!)

理解了这个dp后我才修好了我下面写的贪心

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iostream>

using namespace std;

#define MAXN 500005

int n, c;

// 答案 = c的次数(不变)+最佳的(区间内非c的某种元素出现次数-c的出现次数)

int cl[MAXN];
int pre[MAXN];// 保存遍历过程中i上一次出现的位置
int dp[MAXN];// dp[i]以i位置结尾处的最佳结果
int dpo[MAXN];// 以c-i作为k的最佳结果

int main(int argc, char const *argv[]) {

	scanf("%d%d", &n, &c);

	int t;

	int result = 0;

	for (int i = 1; i <= n; ++i) {
		scanf("%d", &t);

		if (t == c) {
			cl[i]++;
		}
		cl[i] += cl[i - 1];// 前缀数组


		if (t == c) {
			dp[i] = max(0, dp[i - 1] - 1);// 要么c所在位置不选，则以此处为结尾的最佳差值为0；要么选上,则继承以上一个位置结尾的差值再减去1
		} else {// 不为c时
			dpo[i] = max(1, (dpo[pre[t]] + 1) - (cl[i] - cl[pre[t]])); // 从上次这个t出现的位置（不包括）到这个位置结束这段区间，要么从当前位置重新开始一个区间(1)（肯定比不开始(0)好），要么接上上一段区间，其它情况都不如这两种情况；
			dp[i] = max(dp[i - 1], dpo[i]);//要么不是当前的t为参照进行变换(dp[i-1])，要么是(dpo[i])
		}

		pre[t] = i;

		result = max(result, dp[i]);
	}

	result += cl[n];//最后得加上总序列中c出现的次数

	printf("%d\n", result);

	return 0;
}

贪心

这题一开始考虑数据范围很大，二层三层循环啥的肯定gg，然后想到求一段给定数列的子区间和的最大值的方法，那种方法只要一次遍历数组不断更新前缀和的最小值，然后每次更新max(当前的前缀和-之前找到的最小值)

这里也效仿一下，对所有除了c以外出现的数都这么求
注意这里计算最小前缀和的时刻我放到了遇到t并处理之前，然后再计算当前前缀和，然后再相减更新结果

注意在这里k是有很多取值的（因为串里的数在一个情况下都能变成c），我们这里一并进行运算了，这些k的取值情况之间相互是没有联系的，具体的看代码吧

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iostream>

using namespace std;

//用了类似于一次遍历数组求区间最大和的那种办法的思想（即遍历数组不断max(当前前缀和-min(历史上的前缀和))），对除了c以外的那些数都做这种计算


#define MAXN 500005

int n, c;

int cl[MAXN];//c的出现次数前缀数组

int mins[MAXN];//历史上(i出现次数-那时c出现次数取最小值的时候)i出现次数的值
int minpos[MAXN];//i出现上述最小值的位置
int nows[MAXN];//当前出现i的次数

int main(int argc, char const *argv[]) {

	scanf("%d%d", &n, &c);

	int result = 0;

	int t;

	for (int i = 1; i <= n; ++i) {
		scanf("%d", &t);

		cl[i] += cl[i - 1];

		if (t == c) {
			cl[i]++;
		} else {

			//每次在遇到t时,先计算一下在这次t出现之前的最小前缀和，不考虑除t和c以外的其它元素，因为此时k=c-t已经确定，其它数在这种情况下没有影响
			if (nows[t] - cl[i] < mins[t] - cl[minpos[t]]) {
				mins[t] = nows[t];
				minpos[t] = i - 1;
			}

			//然后再考虑这次t的出现，处理t
			nows[t]++;

			//相减更新结果
			result = max(result, ((nows[t] - cl[i]) - (mins[t] - cl[minpos[t]])));

		}
	}

	result += cl[n];

	printf("%d\n", result);
	return 0;
}