(旧存档) 杭电多校第三场-D题

D 签到

题意

给你一个长度为 $n$ 的序列，你可以任意将相邻的两个元素合并为一个元素，该两个元素的权值将会相加。你可以进行无限多次操作，问多次操作后，序列中最多有多少个 $p$ 的倍数。

思路

因为是连续合并两个元素，那么多次相邻合并可以看成合并一个区间。那么相当于问你，有多少个不相交的区间，它的和是 $p$ 的倍数。

显然，若区间 $[l, r]$ 的和为 $p$ 的倍数，那么 sum[r] % p - sum[l - 1] % p = 0

那么我们只需贪心统计有多少个 sum[r] % p = sum[l - 1] % p 的不相交区间即可，也就是先选满足要求的区间，时间复杂度 $O(n)$

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
int sum[N], que[N];
bool vis[N];

int main() {
    int t, n, p;
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d", &n, &p);
        for (int i = 1; i <= n; ++i) {
            scanf("%d", &sum[i]);
            sum[i] = (sum[i - 1] + sum[i]) % p;
        }

        int ans = 0, tot = 0;
        for (int i = 0; i <= n; ++i) {
            if (vis[sum[i]]) {
                while (tot) vis[que[--tot]] = false;
                ans++;
            }
            vis[sum[i]] = true;
            que[tot++] = sum[i];
        }
        while (tot) vis[que[--tot]] = false;
        printf("%d\n", ans);
    }
    return 0;
}