C++ 实现最长区间和被 7 整除

#include #include using namespace std; typedef long long LL; const int N = 50010 * 4; int n; int a[N],s[N]; int h[N],e[N],ne[N],idx; void add(int a,int b){ e[idx] = b,ne[idx] = h[a],h[a] = idx++; } int L[N],R[N],cnt; void build(int u,int l,int r){ if(l == r){ L[u] = R[u] = l; add(u,l + n); return; } int mid = l + r >> 1; build(u << 1,l,mid),build(u << 1 | 1,mid + 1,r); L[u] = L[u << 1],R[u] = R[u << 1 | 1]; add(u,u << 1),add(u,u << 1 | 1); }

void insert(int u,int l,int r,int x,int y,int k){ if(L[u] >= x && R[u] <= y){ add(k,u); return; } int mid = L[u] + R[u] >> 1; if(x <= mid) insert(u << 1,l,mid,x,y,k); if(y > mid) insert(u << 1 | 1,mid + 1,r,x,y,k); }

int q[N]; bool st[N]; int bfs(int start){ int hh = 0,tt = -1; q[++tt] = start,st[start] = true; while(hh <= tt){ int t = q[hh++]; for(int i = h[t];i != -1;i = ne[i]){ int j = e[i]; if(!st[j]){ q[++tt] = j; st[j] = true; } } } return tt; } int main(){ cin>>n; memset(h,-1,sizeof h); for(int i = 1;i <= n;i++){ cin>>a[i]; s[i] = s[i - 1] + a[i]; } for(int i = 0;i <= n;i++){ int r = s[i] % 7; add(r,i + n); } build(1,1,n); for(int i = n;i >= 1;i--){ int r = s[i] % 7; insert(1,1,n,i + 1,n,r + n); } int res = 0; for(int i = 0;i < 7;i++){ memset(st,0,sizeof st); for(int j = 0;j <= n;j++){ if(st[j + n]) continue; if(j == n) continue; if(j != 0) add(j + n - 1,j + n); int k = (i - s[j] % 7 + 7) % 7; for(int t = h[k];t != -1;t = ne[t]){ int l = e[t] - n; if(l > j) break; if(l == j){ res = max(res,1); }else{ int tot = bfs(l); res = max(res,j - l + 1 + tot); } } } } cout<<res<<endl; return 0; }