牛客 Algorithm Choosing Mushrooms

选择一段区间，使得该区间的和是k的倍数

利用(a+b)%k= t , (a+b+c+d)%k= t, 则(c+d)%k = 0 所以c+d是k的倍数

对于前缀和取模在排序即可o(n)得到答案

#include<bits/stdc++.h>using namespace std;typedef long long ll;const int maxn = 2e5 + 5;ll sum[maxn];struct node{ int p, num; } a[maxn];bool cmp(node x,node y){return x.num == y.num ? x.p < y.p : x.num < y.num;}int main(){int n, m, x, start = 0, maxx = 0;ll ans = 0;scanf("%d%d",&n,&m);a[0].num = 0; a[0].p = 0;for(int i = 1; i <= n; i++){scanf("%d",&x);sum[i] = sum[i-1]+x;a[i].num = ((ll)a[i-1].num+x)%m;a[i].p = i;}sort(a+1,a+n+1,cmp);for(int i = 1; i <= n; i++){if(a[i].num == a[i-1].num){ans = max(ans,sum[a[i].p]-sum[start]);maxx = max(maxx,a[i].p-start);}else start = a[i].p;}printf("%lld %d\n",ans,maxx);return 0;}