Accepted 有效得分：100 有效耗时：0ms

水题...O(n)算法直接一次秒掉.....

找出人数差为k出现的最左端位置和最右端位置，然后全部扫一遍过去就好了.....

多写楼下的牛们指点

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

program p1195;

var a:array[0..100000] of longint;

v,c:array[-100000..100000] of longint;

i,j,k,l,m,n,sun,ans:longint;

begin

readln(n);

for i:=1 to n do

begin read(a[i]);if a[i]=0 then a[i]:=-1;end;

for i:=1 to n do

begin c[i]:=c+a[i];

if v[c[i]]=0 then begin

if c[i]=0 then if i>ans then ans:=i;

if c[i]0 then v[c[i]]:=i;

end

else if i-v[c[i]]>ans then ans:=i-v[c[i]];

end;

writeln(ans);

end.

O(N)的，，秒杀

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

每次用integer就错

好题啊。

我们把0换成-1，那么所求的就是和为0的最长序列。

用sum[i]表示 1~i 的和，使 sum[i]-sum[j]=0, i-j是答案。

这样的话我们就要找到一个最小的j满足，sum[j]=sum[i]。我们就可以用一个数组保存sum[j]这个值最早出现的j的值。故只需不断累加，和更新HASH，时间复杂度O(n)。

一开始hash全部赋最大值，hash[0]:=0！！！

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 728ms

├ 测试数据 08：答案正确... 166ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：894ms

虽说知道有O（N）的，可咱不会啊

我的方法是，F，表示第I的人时男女的差，然后我就在O(N!）的情况下加了点优化，运用的MAX，然而第一次第7个点没过，我就把数组下标加了个0,再交AC

894ms好悬2

Cpp环境下的

开全局变量，一定要开全局变量，忒大了

同时考虑‘0’

9

1 1 1 1 0 0 0 0 0

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

O(N)...神似基数排序的方法秒杀...

膜拜Vivid Puppy

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

c数组用来记录前i个人中，男女相差多少，根据性质，如果两个不同的时候i,j却有一样的男女相差数，那么，从i+1到j的男女相等--

不理解的可以看看大牛们怎么说的，再不行就看看我的源程序，记得一定要开大数组，用longint！！

Program P1195;

var c:array[0..100000] of longint;

f:array[-100000..100000] of longint;

max,x,i,j,n,m:longint;

Begin

readln(n); c[0]:=0;

for i:=1 to n do

begin

read(x);

c[i]:=c;

if x=1 then inc(c[i]) else dec(c[i]);

if (i>max) and (c[i]=0) then begin max:=i; continue; end;

if f[c[i]]=0 then f[c[i]]:=i

else if i-f[c[i]]>max then max:=i-f[c[i]];

end;

writeln(max);

end.

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 728ms

├ 测试数据 08：答案正确... 181ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：909ms

18行的程序，3次UNAC,就是因为'0'的问题...

Orz神牛们

type

wu=record

x,y:longint;

end;

var

n,i,j,k,m,ans:longint;

a:array[0..100000] of longint;

f:array[-100000..100000] of wu;

begin

readln(n);

a[0]:=0;

for i:=1 to n do

begin

read(m);

a[i]:=a;

if m=0 then inc(a[i])

else dec(a[i]);

end;

for i:=-n to n do

f[i].x:=-1;

ans:=0;

for i:=0 to n do

begin

if f[a[i]].x=-1 then f[a[i]].x:=i

else

begin

f[a[i]].y:=i;

m:= f[a[i]].y-f[a[i]].x;

if m>ans then

ans:=m;

end;

end;

writeln(ans);

end.

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 728ms

├ 测试数据 08：答案正确... 166ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：894ms

十五行程序的回报。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

阅读理解能力哎......时间复杂度是nlog(n),也就是一个快排.

可以O(n),不过貌似常数大点.

设a0[i]--1..i中0的个数

a1[i]--1..i中1的个数,

题目要求求一对数i,j,满足a0[j]-a0=a1[j]-a1且i-j+1最大.上式移项,得a0[j]-a1[j]=a0-a1.设a[k]=a0[k]-a1[k],则原式就是a[j]=a[j-1].然后从1..n扫一遍,开个哈希表h1[i]表示数i在a中第一次出现的位置;

n..1回扫,hash表h2[i]表示数i在a中最后一次出现的位置.求h2[i]-h1[i]最大值

复杂度O(n)

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

多谢llzzpp999和hydralisk的思路!!

模仿某撼地神牛的回复……

流动的水没有形状，漂流的风找不到踪迹，任何AC都取决于心！

今天是Matrix67的非常男女计划，所有人按照身高排成一排，越来越多的人企图配对结婚！遗忘了两个月的问题，今天晚上将重新提起！

唯一看透真相的是，外表看似小孩，头脑却是大人，他的名字就是……#!@%*(&!$@!%!@^

被老师砸醒。。。

晕死了，怎么做啊

庆祝100ac100题..

边读边做hash O(n) .....so cool 秒杀

此题有两种处理方式:

第一种就是二分答案然后扫一遍.O(nlogn)

不过还有更容易的解决方式,就是使用hash表:

我们把男生看成1,女生看成-1

那么就是要求部分和为0的最长段,我们用hash[x]记录最早出现前缀和为x的下标

然后扫一遍取最大即可,O(n).