Codeforces 1082E(DP / 贪心)

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;
}
------ 本文结束 ------