现在的位置: 首页 > 综合 > 正文

悲催的PKU ACM 3980

2013年08月17日 ⁄ 综合 ⁄ 共 1376字 ⁄ 字号 评论关闭

读研那会儿,偶然发现了这个http://acm.zju.edu.cn/onlinejudge/(现在回忆起来大约是在CSDN算法论坛泡的时候有人提起的,原谅我这读本科不是计算机专业的人吧),于是就兴致满满的一道一道做,直到做完了1008。突然觉得很没意思,那些AC率低的一般都是NP问题,翻来覆去就是如何剪枝,而这个是最伤脑细胞的。然后呢,就不做了。最近听说浙大得了ACM比赛的世界冠军,上去又看了看,8年了,我的数据居然还在(不然也不记得做到哪了,其实我最佩服我居然还记得8年没有的账号密码)。

然后又去http://poj.org/看了看,域名都换了,不知道是我记错了还是数据都丢了,账号登不上去,于是我又注册了一个,发现记忆中的账号还能注册,是数据丢了还是我从来没注册呢?

~!@#,居然还有中文题目,好,让我选一道水题——年纪大了,脑子不好使了。于是我就看中了3980这道AC过60%的题目,做一个取余的函数。想来取余运算几乎所有语言都有,让我先试试内置的怎么样。于是从1000题拷贝了一段示例代码,稍微修改如下(主要是我不太会写I/O):

#include <stdio.h>

int main()

{

    int a,b;

    while(scanf("%d %d",&a, &b)) printf("%d/n",a%b);

    return 0;

}

 

提交,~!@#¥,居然TLE,果然不简单(看官先别喷,我只是如实叙述而已,就像上面说的,没经过训练的写对I/O是个很大的问题),然后我就开始Google取模快速算法,未果——看起来不是存在什么秘密武器。回头看了一下题目,b<=32767,好像构造个表啥的能快吧,那天就这么过去了。

 

第二天再看,好像那个while循环有问题,查了一下手册,果然死循环了,再修改如下:

#include <stdio.h>

int main()

{

    int a,b;

    while(scanf("%d %d",&a, &b) != EOF) printf("%d/n",a%b);

    return 0;

}

 

提交,AC,不过耗时396MS,看了一下排行榜,瀑布汗。

注意到a < b时,a mod b = a,再修改了一下,缩短了15MS,看来不是正途。看了一下讨论,有人说C的125MS,一直我选的是GCC编译,于是我也换C编译,用的是最直白那个版本,嗯,我也125MS了,然后加上“优化”,得,141MS,我也知道while中有if不好,也不用这样吧。

于是我注意到排行榜中很多都是pascal,虽然我没学过,我也现学现卖(主要又是从1000题里拷贝的示例代码):

program p3980(Input,Output);

var

  a,b:Integer;

begin

  

while not eof(input) do

begin

Readln(a,b);

Writeln(a mod b);

end;

end.

~!@#¥,79MS(我刚才提交时,63MS),于是我再改进如下:

program p3980(Input,Output);

var

  a,b:Integer;

begin

  

while not eof(input) do

begin

Readln(a,b);

if a<b then writeln(a) else Writeln(a mod b);

end;

end.

~!@#¥,47MS!

于是,我爆了粗口……

 

 

【上篇】
【下篇】

抱歉!评论已关闭.