漂亮数组

链接：https://ac.nowcoder.com/acm/contest/67744/E

---

题目描述

阿宁认为一个数组是漂亮数组，该数组需要存在一个总和是$k$的倍数的子数组。

现在阿宁有一个长度为$n$的数组$a$，阿宁想要将数组$a$分割出若干个数组，分割出的数组需要满足，按照分割顺序合并可以得到原数组$a$。

阿宁想知道将数组$a$分割，最多可以获得多少个漂亮数组？

输入描述:

第一行输入两个整数$n$，$k$。

第二行输入$n$个整数$a_i$。

$1≤n≤2×10^5$

$1≤k,ai≤10^9$

输出描述:

输出一个整数。

示例1

输入

text

6 3
1 1 4 5 1 4

输出

text

2

说明

分割成[1,1,4],[5,1],[4]，其中[1,1,4],[5,1]两个数组是漂亮数组。

---

题解

首先，对于一个给定的数组，如果第$a_i$个以前和第$a_{i+2}$个以后的都可以构成漂亮数组，那么我们来考虑一下将第$a_{i+1}$个数字放在前面还是后面。答案是后面，因为往前面这个数组里面再加入数字是没有意义的，不如留给下一个数组，这也就构成了我们这道题的思路：贪心。

接下看究竟什么样的数组才是漂亮数组。按题意，有两种情况：

第一种为数组的某一个子数组的和为$k$的倍数。这是我们将数组分为两部分，由前面的贪心思想可知，前一部分为无关项，后一部分为相关项，即前半部分的和为$b$，$b!=nk$，后半部分和为$nk$，考虑到sum的结果可能超过long long的范围，所以我们考虑取余，并且可以通过前缀和来减少时间消耗。即当前缀和%k的余数之前已经出现过的时候，组成一最小的漂亮数组。

第二种是该数组的和恰好是$k$的倍数，即前缀和%k的值为0。

下面是完整代码：

#include<bits/stdc++.h>
using namespace std;
long long k;
long long a[200005]={0};
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n>>k;
    long long ans=0;
    for (int i=1;i<=n;i++)
    {
        cin>>a[i];
        a[i]=(a[i]+a[i-1])%k;
    }
    set <int > st;
    int j=0;
    for (int i=1;i<=n;i++)
    {
        if (st.find(a[i]-a[j]+k)!=st.end() || (a[i]-a[j])==0)
        {
            ans++;
            j=i;
            st.clear();
        }
        else
        {
            st.insert(a[i]-a[j]+k);
        }
    }
    cout<<ans<<endl;
    return 0;
}