P8226 「Wdoi-5」樱点收集 题解

· · 题解

题意：

一个人吃豆豆，沿路上有若干段豆豆，这个人挨着吃，吃 k 个就会立马吐光继续吃。某些相邻两段之间有垃圾桶，这个人可以选择一段不吃，问最多往垃圾桶里吐几次。

假设每一段都有豆豆。

首先考虑不能不吃的情况：

将每段豆豆数量做前缀和，统计有垃圾桶且前缀和模 k 等于0的位置数。

再加上可以有一段不吃的情况：

枚举跳过的一段，如果后面某一个位置的前缀和减去这段豆豆数后模 k 的值为 0， 那么它模 k 就等于这段豆豆数模 k。所以这一段后面统计前缀和模 k 等于 这段豆豆数模 k 的位置数，这一段前面仍然只统计前缀和模 k 等于 0 的位置数(均有垃圾桶)，二者相加即可。

由于 k 只有 10^6，开两个大小为 10^6 的数组 l 和 r，l[i] 和 r[i] 分别存储某一段前面和后面有垃圾桶且前缀和模 k 为 i 的位置数。假定这段初始时为 0 或 n+1，则先把全部有垃圾桶且前缀和模 k 为 i 的位置数储存在 r[i] 或 l[i] 中，从前往后或从后往前边枚举跳过的一段，边更新 l 和 r 和答案即可。

计算时若某一段无豆豆，则跳过，不用其前缀和更新。

时间复杂度：O(n)

代码：

#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

typedef long long LL;

const int N = 300010, M = 1000010;
int n, m;
LL a[N], s[N], res, K;
int nl[M], nr[M];
bool st[N];

int main(){
    scanf("%d%d%lld", &n, &m, &K);
    for(int i = 1; i <= m; i ++){
        int t;
        scanf("%d", &t);
        st[t] = true;
    }

    for(int i = 1; i <= n; i ++){
        scanf("%lld", &a[i]);
        s[i] = a[i] + s[i - 1];
        if(a[i] && st[i]) nl[s[i] % K] ++;
    }

    int res = nl[0];
    for(int i = n; i >= 1; i --){
        if(a[i] && st[i]) nl[s[i] % K] --;
        res = max(res, nl[0] + nr[a[i] % K]);
        if(a[i] && st[i]) nr[s[i] % K] ++;
    }
    printf("%d\n", res);
    return 0;
}