Codeforces 1082E
题意:给一个长度为$n$的序列,并且确定一个数$c$。你可以任选一个区间$[l,r]$, 对该区间$+k,k$可以为负数,使得最后的$n$个数中,等于$c$的数字的个数最多。问最多有多少个这样的数?
方法1
将所有数减去$c$,则答案就变成最后最多几个0.
然后如果是整个区间加减的话答案就是出现次数最多的数的个数。
现在是区间,分析一下发现其实和上面类似,只需要考虑一下多余的0怎么处理
考虑 22002
这个数据,这个数据如果将2减去则会破坏中间的0,那么如果操作这个区间对答案贡献为 $3-2=1$ 。那么我们发现,算出序列 0 的个数,然后扫一遍这种情况的区间就行了。
我们分颜色讨论,一个颜色肯定取的块是连续的(前缀、后缀、中间一段),那么我们可以像DP求最大字段和一样,如果前面的答案为负了,那么舍弃重新开始。对每个颜色进行这个操作即可。
方法2
知识点:
1、数组下标出现负值小心,加上基准值
//方法1
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
#include<utility>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
int n, c, a[500000 + 5], tax[1000000 + 5], bj[1000000 + 5], cnt0;
int bs = 500000;
void clean() {
cnt0 = 0;
}
int solve() {
clean();
cin >> n >> c;
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), a[i] -= c, cnt0 += (a[i] == 0);
int tot = 0;
int ans = cnt0;
ms(tax, 0), ms(bj, 0);
for (int i = 1; i <= n; ++i) {
if (a[i] == 0) ++tot; else { // 统计当前 0 的个数
if (tax[a[i] + bs] <= tot + bj[a[i] + bs]) { // 当前颜色 a[i] ,i 前面的块负了,舍弃
tax[a[i] + bs] = 0;
bj[a[i] + bs] = -tot;
}
++tax[a[i] + bs];
ans = max(ans, cnt0 + tax[a[i] + bs] - (tot + bj[a[i] + bs])); // 更新答案
}
}
printf("%d\n", ans);
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}