NOI 2006:终点?起点?

我回来了…… 这几天搞物理,没上网……NOI 2006 就这样过去了……第一天,除了WXS,大家都考得不好,心情于是都不好,想着第二天翻盘。LTY50,我40,ZH40,别人10分、30分等。第二天,LTY成功翻盘,我差一点,ZH也差得不多……第一天,WORM不知道哪里错了,-70。。。 HAPPYBIRTHDAY的TREAP也不知道哪里错了,-60。。。 NETWORK最郁闷,二分把(a+b)div 2写成了b div 2,-40。。。第二天,BAG竟然高精度把数组开小了…… -40。。。 剩下一道网络流,写都写出来了,结果最后累加的时候写错一个字母…… -80。。。 就这个字母,导致了out……最后只有181分了…… 250是分数线……这次就是小错误实在太多了…… 每道题,除了提交答案,就有错误……还是陈老师说得好,“你平时所有的弱点,都会在比赛的时候反映出来”。一点不错啊,平时我就常常要submit几次的……这次很幸运的碰到了MSN上的JR同志,比我靠前2名……看见了从前常常在SGU上看见的zhengzeyu同志,夏令营金奖啊 大牛啊…… 以后一定要加倍仔细啊!…… 细节决定成败是一点也没有错的,但前提条件是先达到一定水平…… 这也算是经历了一次挫折了吧…… 也是好事……正在用这一个月搞物理,目标两等或以上。为了一种…… 信仰吧…… OI暂时放一下吧这几天把标准教材看了一遍…… 做了一些题…… 打算再找几本书看看…… 比如WXS推荐的…… 就是比较懒得出门……

我见过的编译时间最长的Pascal程序……

今天写的SGU 221,其实也就是记忆化搜索+高精度,结果每次编译都要很长时间…… 原来以为是电脑慢的关系…… 但是等到重起之后,还是非常慢……于是决定好好测试一下…… 结果还是很有意思的……直接FPC sgu221.pas,显示12.2sec! 怪不得那么慢……如果dcc32 sgu221.pas,显示3.84sec,多次平均,大约3.7sec左右…… dcc的确快啊! 但还是很慢……于是,我对工作文件夹里面的近400个pas文件进行了dcc的编译测试,结果只有sgu167可以与其抗衡,dcc在3.0sec左右,fpc在11.7sec左右…… sgu221的编译时间少见得长啊……这两个pas有个共同的特点:dcc显示的data大小都很大,sgu221有10MB,sgu167有16M(还打一些……),不知道有什么关系。两个文件在130-140行左右,也不长啊…… 似乎Pascal编译器对复杂的数据结构比较敏感(sgu167有一个4维数组,221也是)……

SGU 183:好算法与差算法&好实现与差实现

看见SGU 183没有过,就想去过了他……条件:n=10000 m=100 time limit=250ms开始的时候,自己想了O(n*m^2)的算法,DP的,O(n*m^2)个状态,O(1)转移,太慢-2s……后来发现每次新的状态只有m个,其余都是原来的移位,于是通过修改,达到了O(n*m*logm)。其中,O(m*logm)是排序m个数的时间。这样是413ms,慢了一点…… 但是我想不到更快的排序方法了……于是就改变状态,像题解的那样,结果那样的O(n*m^2)需要4.xs… 改成O(n*m)的,结果还是超时,3xxms.. 正确的算法也需要优化啊……于是先优化,26xms,再优化,26xms,再优化,终于,只要23xms了…… 感觉平时写代码总是写得很烦,写得太复杂了。应该注重代码的简化……

SGU 132 Accepted !~

虽然报告上都说132是简单题,但是…… 做起来还是很麻烦的,主要是超时问题。很多人用二进制表示状态,但我用二进制想了n次也没有想通,比如如何计算新增块数?(后来通过阅读周大牛的程序,原来他的状态是三进制的,状态转移/方法是三进制的)于是我先用了3进制,用0表示空格或竖的下面,1表示横的,2表示数的上面。这样的好处是状态少(408个),但是导致了上一行的某个0不能判断是不是空格,严重问题…… 假如2改成竖的下面,导致了同样的问题,只是换到下面一行了…… 后来改用四进制,但是状态太多了…… 最后还是用3进制,但是0表示空格,1表示横的或者竖的下面。这样状态多了(2187=3^7)个,速度慢…… 顶级数据4x s……一天,突然发现了一个优化:在判断能否放入地形的同时能够判断水平空格。这样只要17 s了……原先是预先把两行相容关系存下来(408*408 byte),但是现在,内存不够了(1M)…… 后来想出了位压缩的办法…… 就可以了…… 再加上一些优化…… 只要6 s了……L大牛给了一个优化:预先把一个数对应的三进制存下来。这样,计算两行的可行性变快了50%,但计算两行可行性还是要1.3-1.4 s……(原来2s左右)接下来,一天没有想法。 昨天发现,相容两行的数量很少,只有174k对。今天对此进行优化:开了个大表,枚举这一行的时候,能够直接读出他的可行的上一行(可行就是指2有对应的1)。这样,进行动态规划的时间减少到了很少的时间…… 主要时间花在状态枚举上,这时也只要0.6 s了…… 最终,0.7xx s AC 了…………………… 一周了……

流水账~

SGU 189终于过了..原来是一个小的逻辑错误~不应该昨天去外婆家,亲戚都说我瘦了~ 看来要好好注意身体,毕竟"身体是革命的本钱"么现在有个奇怪的现象:早上起床常没精神,然后一天都时常打哈欠.但是只要去电脑前坐一会儿就会有精神,不知道什么原因.USOPEN06做得不好~时间没分配好~太郁闷了by mobile

SGU 121 AC!

终于AC了~~~修正了非常多的小BUG,使用随机测试非常多次,终于AC了~从最初的100行左右,涨到了22x行~~~新年新气象啊~下面是验证程序~ 不过不判无解的~const maxn=100; var c,t,p,q,n:longint; l,r:array[1..maxn,1..maxn]of longint; d:array[1..maxn]of longint; col:array[1..maxn,1..2]of byte; s:string; begin assign(input,’sgu121.in’);reset(input); readln(n); for t:=1 to n do begin read(p); while p<>0 do begin inc(d[t]); l[t,d[t]]:=p; read(p); end; end; close(input); p:=0; assign(input,’sgu121.out’);reset(input); readln(s); if s=’No solution’ then begin writeln(‘Reported No solution…’); exit; end; reset(input); for t:=1 to n do begin read(p);c:=0; while p<>0 …

Continue reading ‘SGU 121 AC!’ »