寒假训练第四周（牛客训练营）
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; }