来自"NOCOW"

由于所选的数是连续的,则可以枚举每一个区间,这样的时间复杂度是 O(N^2)的. 下面讲一下O(N)的算法: 对于这N个数,从第一个数加到第I个数,我们记作S[I], 1.假如有S[I] MOD N=0,那么1~I即为一个可行解, 2.假如S[I] MOD N=S[J] MOD N(I<J),那么I+1~J即为一个可行解

这不是也是N^2的吗？…………怎么变成O(N)的了

---

VAR
  a,f:array [0..10000] of longint;
  i,j,k,n,x,y:longint;
Procedure work(a,b:longint);
BEGIN
  x:=a;
  y:=b;
  k:=b-a+1;
END;
BEGIN
  readln(n);
  k:=Maxlongint;
    for i:=1 to n do
      BEGIN
        readln(a[i]);
        f[i]:=(f[i-1]+a[i]) mod n;
          if f[i]=0 then work(1,i);
      END;
    for i:=1 to n do
      for j:=i+1 to n do
        if f[i]=f[j] then work(i+1,j);
    if k=Maxlongint then writeln(0)
      else
        BEGIN
          writeln(k);
            for i:=x to y do writeln(a[i]);
        END;
END.
//from lzoi_ys

楼上的好像是O(N^2)额。。。 发个O(N)的~

#include <iostream>
using namespace std;
int N,a[10001],sum[10001]={0},f[10001]={0};
int main()
{
    cin >> N;
    for (int i=1;i<=N;i++)
        cin >> a[i];
    for (int i=1;i<=N;i++)
    {
        sum[i]=(a[i]+sum[i-1])%N;
        if (f[sum[i]] || (sum[i] == 0))
        {
            cout << i-f[sum[i]] << endl;
            for (int j=f[sum[i]]+1;j<=i;j++)
                cout << a[j] << endl;
            break;
        }
        f[sum[i]]=i;
    }
    return 0;
}
//by zzy