题解 - Vijos

0

gsrq LV 10 @ 2009-10-18 11:25:04

Orz 340508965

转一下

var

a,i,k,n:longint;

sum:int64;

b:array[0..100000] of longint; //表示余数为j时sum的总个数

begin

readln(n,k);

sum:=0;

for i:=1 to n do

begin

readln(a);

inc(sum,a);

inc(b[sum mod k]); //更新相应的b[]

end;

sum:=b[0]; //刚才说的注意的地方

for i:=0 to k-1 do

sum:=(sum+(b[i]*(b[i]-1))shr 1) mod 1234567;

writeln(sum);

end.

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

噢耶 (^o^)/ 秒杀呵呵很难得啊

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

先说说怎么做吧

SUM[i]是代表前i个数的和

当(SUM[i]-SUM[j]) MOD k=0 这时[j+1,i]就是满足的一个区间一个方案了

而我们求的是(SUM[i]-SUM[j]) MOD k=0 这样的方案总个数

我们又可以推出上式等价于SUM[i] MOD k=SUM[j] MOD k

所以我们就是求SUM[i] MOD k=SUM[j] MOD k 的方案个数了

假设 sum[i],sum[j],..sum[k]（共bn个）都是 MOD k 余数为k-1的sum

那么从上面bn个sum中任意选取两个就能得出(SUM[i]-SUM[j]) MOD k=0

那么在bn个sum中怎么配对呢

（下面的sum[bn]表示上述bn个sum中的第n个sum）

很简单先是sum[b1]与sum[b2] sum[b3] ...sum[bn] (bn-1 个)

　　然后sum[b2]与sum[b3] sum[b4] ...sum[bn] (bn-2 个)

　　然后sum[b3]与sum[b4] sum[b5] ...sum[bn] (bn-3 个)

　　 ............

　　最后sum[bn-1]与sum[bn]　　　　　　　　 ( 1 个)

　　方案总数=n-1+n-2+n-3+...+1=bn*(bn-1) div 2

（好像这是初中的知识吧？可是当时我看楼下的楼下的楼下....的题解我一时竟然还不明白为什么）

所以当sum mod k的余数为k-1时有bn*(bn-1) div 2个方案总数了

就这样依次得出余数为k-1 k-2 k-3 ...0的时候方案总数再相加一下得出答案

所以在读入一个数的时候就计算sum然后计算sum mod k 的余数

而b[j]表示余数为j的sum个数此时根据上面新得出的更新相应的b[j]

这样在读入完毕之后就可以根据b[j]直接计算总方案数了

特别值得注意的是！！！！

计算余数为0的方案总数时候还要加上b[0]　　也就是b[0]*(b[0]-1) div 2+b[0]

为什么？？因为余数为0的时候单独一个sum[i]就能成为一个方案了

还有比如div 2可以用shr 1 这样可以加快速度

呼呼(～ o ～)~zZ　　说得好累啊

我自己都快被讲糊涂了呵呵

希望有不懂这道题目的人能看懂....

这样就不算白忙了

huangruihaocst @ 2015-02-27 11:12:10

太赞了^_^
日臻完善 @ 2015-03-25 15:30:15

太感谢了！！！
haoziyu @ 2015-07-22 14:37:05

gan xie
guoqianli @ 2015-10-06 16:31:10

难得有这么细心为大家讲的人，好人有好报，顶一个！！！！！！！！！！！！！！！！！！！！!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

0

SUPER JUST LV 8 @ 2009-10-14 21:16:37

感谢340508965的妙解，犹如醍醐灌顶啊。

0

zxj19940106 LV 4 @ 2009-10-12 16:02:38

var l,n,k:longint;

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

procedure init;

　　　　 var i,j,q,r,t,all:longint;

begin

　　 readln(n,k);

　　 fillchar(a,sizeof(a),0);

　　 r:=0;

　　 all:=0;

　　 for i:=1 to n do

　　　　 begin

　　　　　　 readln(q);

　　　　　　 all:=all+q;

　　　　　　 if all>=k then all:=all mod k;

　　　　　　 r:=r+a[all];

　　　　　　 if all=0 then inc(r);

　　　　　　 if r>=1234567 then r:=r mod 1234567;

　　　　　　 inc(a[all]);

　　　　 end;

　　 writeln(r);

end;

begin

　　 init;

end.

0

527971925 LV 10 @ 2009-10-10 19:40:28

开始把题意看错，以为是DP，看了数据范围后郁闷了半天......

后来看题解才发现题意理解错了.....

倒............

搜一遍即得，在大脑中想想数格子的场景吧.....

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

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

按Ctrl+A看代码

var l,n,k:longint; a,b:array[0..100000]of longint;procedure init; var i,j,q,r,t,all:longint;begin readln(n,k); fillchar(a,sizeof(a),0); r:=0; all:=0; for i:=1 to n do begin readln(q); all:=all+q; if all>=k then all:=all mod k; r:=r+a[all]; if all=0 then inc(r); if r>=1234567 then r:=r mod 1234567; inc(a[all]); end; writeln(r);end;begin init;end.

0

zhanghanyuan LV 10 @ 2009-09-23 10:03:15

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

简简单单

0

prince_hao LV 10 @ 2009-09-13 14:10:49

编译通过...

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

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

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

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

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

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

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

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

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

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

只用加法就够了简单

0

芒果木瓜榴莲 LV 9 @ 2009-09-12 21:38:48

赞340508965的题解

要不然我还真不知道该怎么做

最近vijos超慢，用世界之窗浏览器根本打不开页面，现在只能用Opera

0

水莫世界 LV 9 @ 2009-09-10 16:31:21

意想不到的好方法…………

偶然在…………膜拜ing

———————————————————————成长中的菜鸟

0

fenghao LV 10 @ 2009-08-30 20:19:23

...竟然没想到桶排。。直接快排一个。。然后就耗时了。。无语了。。

0

~氮氧碘磷 LV 5 @ 2009-08-17 10:53:04

好方法 ~

0

永远的波拿巴 LV 10 @ 2009-08-14 21:05:07

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

(^o^)/ 20行 MS

0

zjianzhe LV 10 @ 2009-08-13 11:09:05

AC 100纪念~~~~

0

ufo172849z LV 10 @ 2009-08-12 20:23:55

囧。看错数据范围了。开了10000的数组，少了个0，RE了3个点。

0

yangfudong27 LV 8 @ 2009-08-11 16:33:30

十分感谢340508965的题解！

0

su6422 LV 8 @ 2009-08-08 10:42:36

竟然没秒！10ms汗死...........

0

lys_oson LV 8 @ 2009-08-04 14:53:44

余数为0的时候单独一个sum[i]就可以构成一个方案了。

所以余数为0时cn1+cn2

余数不为0时cn2

答案就是求和

0

sjsjsj LV 8 @ 2009-08-03 21:43:39

如果您在程序中使用了iostream;

请改为stdio.h

0

jerryR1 LV 9 @ 2009-08-03 21:20:39

谢谢楼下的楼下

^ ^

0

搁浅 LV 9 @ 2009-07-27 15:40:57

var n,k,i,v:longint;

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

total,sum:int64;

begin readln(n,k);

sum:=0;

fillchar(d,sizeof(d),0);

for i:=1 to n do

begin

readln(v);

sum:=sum+v;

inc(d[sum mod k]);

end;

for i:=1 to k-1 do

total:=(total+d[i]*(d[i]-1)div 2) mod 1234567;

total:=(total+d[0]+d[0]*(d[0]-1) div 2) mod 1234567;

writeln(total);

end.

大家注意了,读入的时候千万往不要用数组不然只有80分最后2个点存取非法 216

感谢楼下的妙解``

0

340508965 LV 10 @ 2009-07-24 16:29:24

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

噢耶 (^o^)/ 秒杀呵呵很难得啊

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

先说说怎么做吧

SUM[i]是代表前i个数的和

当(SUM[i]-SUM[j]) MOD k=0 这时[j+1,i]就是满足的一个区间一个方案了

而我们求的是(SUM[i]-SUM[j]) MOD k=0 这样的方案总个数

我们又可以推出上式等价于SUM[i] MOD k=SUM[j] MOD k

所以我们就是求SUM[i] MOD k=SUM[j] MOD k 的方案个数了

假设 sum[i],sum[j],..sum[k]（共bn个）都是 MOD k 余数为k-1的sum

那么从上面bn个sum中任意选取两个就能得出(SUM[i]-SUM[j]) MOD k=0

那么在bn个sum中怎么配对呢

（下面的sum[bn]表示上述bn个sum中的第n个sum）

很简单先是sum[b1]与sum[b2] sum[b3] ...sum[bn] (bn-1 个)

然后sum[b2]与sum[b3] sum[b4] ...sum[bn] (bn-2 个)

然后sum[b3]与sum[b4] sum[b5] ...sum[bn] (bn-3 个)

............

最后sum[bn-1]与sum[bn] ( 1 个)

方案总数=n-1+n-2+n-3+...+1=bn*(bn-1) div 2

（好像这是初中的知识吧？可是当时我看楼下的楼下的楼下....的题解我一时竟然还不明白为什么）

所以当sum mod k的余数为k-1时有bn*(bn-1) div 2个方案总数了

就这样依次得出余数为k-1 k-2 k-3 ...0的时候方案总数再相加一下得出答案

所以在读入一个数的时候就计算sum然后计算sum mod k 的余数

而b[j]表示余数为j的sum个数此时根据上面新得出的更新相应的b[j]

这样在读入完毕之后就可以根据b[j]直接计算总方案数了

特别值得注意的是！！！！

计算余数为0的方案总数时候还要加上b[0] 也就是b[0]*(b[0]-1) div 2+b[0]

为什么？？因为余数为0的时候单独一个sum[i]就能成为一个方案了

还有比如div 2可以用shr 1 这样可以加快速度

呼呼(～ o ～)~zZ 说得好累啊

我自己都快被讲糊涂了呵呵

希望有不懂这道题目的人能看懂....

这样就不算白忙了

---|---|---|---|---|---|---|---|---|--晒程序了---|---|---|---|---|---|---|---|---|--

var a,i,k,n:longint;

sum:int64;

b:array[0..100000] of longint; //表示余数为j时sum的总个数

begin

readln(n,k); sum:=0;

for i:=1 to n do

begin

readln(a); inc(sum,a);

inc(b[sum mod k]); //更新相应的b[]

end;

sum:=b[0]; //刚才说的注意的地方

for i:=0 to k-1 do

sum:=(sum+(b[i]*(b[i]-1))shr 1) mod 1234567;

writeln(sum);

end.

题解

125 条题解

连续数之和

信息

状态

开发

支持

题解

125 条题解

连续数之和

信息

状态

开发

支持

还没有账户？

登录