寒假训练第四周（牛客训练营）

E-漂亮数组_2024牛客寒假算法基础集训营4 (nowcoder.com)

这题想多了，以为是一个dp优化，没想到贪心即可，dp比较弱，赶紧优化

题解：找一个区间满足k倍即可，我们直接累加然后模k如果出现两次模k等于同一个数那么这个区间就是k的倍数记录即可

简单贪心，没想到

#include <bits/stdc++.h>
//#pragma GCC optimize("Ofast")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
//#define double long double
 #define int long long
#define endl '\n'
using namespace std;
const int N=2e5+9,M=1e1;
const int INF = 0x3f3f3f3f3f3f3f3f;
const int mod=998244353;
typedef pair<int,int> PII;


void solve()
{
    int n,k;
    cin>>n>>k;
    map<int,int> mp;
    mp[0]=1;
    int sum=0;
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        sum+=x;
        int p=sum%k;
        if(mp[p])
        {
            ans++;
            mp.clear();
            sum=0;
            mp[0]=1;
            continue;
        }
        mp[p]=1;
    }
    cout<<ans<<endl;
}
signed main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int T=1;
//    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}