ACM

今天PKU_Team_Exercise3

开始了龙飞GG所说的2天一次比赛的时期,今天PKU进行Team_Exercise_3

换队友了,MM谢金晶

开始后感觉还不错,快速把题目扫了一遍就发现有ZOJ上的原题,可以我没做:(,一个是最长不下降子序列,一个是那个键盘的问题.反正队里题目还没有打印出来,于是商量好我做最长不下降子序列的D,让队友去做键盘I.

D是很简单的DP,连最后的序列都可以不用输出,并且数据很小,DP都是用最笨的方法去DP,提交后WA,检查了一下发现了几个可能影响结果的小bug,继续WA,被打击了.

刚好这个时候题目打印出来了,我就把机器腾出来让队友上去写键盘,跟她说了一下题目意思我就去读其他题目了.发现最近看题目特别有感觉,几乎所有的题目都能看懂了,并且很多BT题目都有心情慢慢看懂,不借助词典搞定,但是没发现太容易的(前面几个).

Knuthocean在我读过几个题目后大喊一声:D这个题目是最长上升子序列,不是不下降!是小于不是小于等于,我AC了!马上到机器上把那个’=’去掉,submit后AC,狠狠的骂了一顿PKU的OJ继续看题,然后队友很快也把键盘那个题目给弄出来了,

这个时候很多人都是4AC或者3AC了,真是急人…而PKU那个OJ也真是的,浪费偶那么多时间来改D,并且没有一次AC,罚时罚惨了.题目有问题也不说一下.

看题目后我感觉F比较容易,而队友认为H比较容易,于是分工好两人分别计算,我很快把F写了出来,提交后WA,然后就想是不是不是一组测试数据,并且那个过半到底是基于什么考虑的,屡次提交还是WA.明明是一个简单题却WA成这样,是个人都不能被这么打击啊,于是去写H,本来还以为要高精的,但是ddoonn__cc用了一个巧妙的方法转成了double以内的,反正精度只要小数点后5位,就用log10和pow把乘方改成了乘法.写好后发现数据根本不对,准备打印代码的时候看见自己又是低级错误,一个是把i写成k,一个是把i+1写出i-1,估计是气晕了,修改后提交,AC,终于尝到一次AC的感觉了,但是居然没有一次写AC,失败啊.

这时候我跟队友都觉得J是一个数学推理题,应该可以把那个高精除+高精乘+高精加转成高精乘+高精加,并且判别方法我提出了一个简单的方法,最后证明是对的,但是我当时无法证明其正确性,所以不敢写.于是我跟队友分工她去推公式,而我继续改F.

F在WA了无数次后并且把代码打出来给N多人看了无数次都认为没错后我彻底崩溃了,无奈中跟Knuthocean要来代码对字母(-_______-b也只有气急败坏的时候才这样),结果一样的思路和算法写出来差太远,本来不抱什么希望了后来突然描见输出的时候把n和p给写反了-___-b,因为自己的测试数据一直都是n==p,所以也没有发现这个问题,改动后就AC了.当时对自己的bs真是有如滔滔江水连绵不绝…

这个时候队友也推出了J的公式,我看了看,高精的单精乘方+高精加,直接用高精乘实现那个高精的单精乘法,然后加了一个高精加,TLE了T___T(给我一个RP差的理由先),想了想如何优化,被打击的让队友去写了,跟她说如何优化就OK了,果然很快队友就AC了.

这个时候过5个,队里还算比较好的,Knuthocean跟ddoonn__cc还有mast他们都说G可以贴龙飞的标程过,于是找到那个标程,看了看接口,叫ddoonn__cc说了说意思,自己写了个输入输出和转换函数就算了,提交后WA(-___-b,不要紧,习惯了),然后看了看怎么回事,这个时候dongfangxu已经过来登记结果了,我抗议比赛还没结束继续改代码,终于看到了龙飞的标程数组从1开始而不是0,小小修改后提交,AC,刚好dongfanxu过来,登记6AC,爽!!!!

今天的RP真是差到了极点,没有一个程序是一次写对的,并且回去后看队友过J的代码,跟我的算法也基本一样,没有优化什么,居然就0s过了,后来问别人了才知道可能是我对于t==1的情况没有考虑好.

不过最后结果还算能过得去,6AC,也是一次突破了吧,但是这次的题目也太简单了点,并且一共有10个题目,所以也没有什么好炫耀的,mast他们还过7个了呢.

对POJ极度不满,题目有错也不说,害我一开始就在D上面不停的WA,弄得信心全无,后来写代码都有心理障碍了,只要觉得能让队友搞定的都不去抢了,还主动让掉.应该也算一种团队能力吧:)

今天的woj_teamtest1

WHUACM2005第一次内部组队赛,人和上次PKU的一样,dragonflywww出题,3简单+2中等,都是最近上课讲的东西

本次要求2个人用一台机器,分工要搞好,提示可以使用打印机把代码打印出来,然后在纸上自己debug

分工是蓝蜂看后面两个,我看前面3个,他一开始就说D比较好弄,我看了后发现C的数据量比较小,是可以不用母函数DP直接DFS出来的,然后我上去写C,自己随便测了几个数据有问题,于是让蓝蜂上来写D,我把代码打印出来坐一边自己看去了

D是一个超级麻烦的题目…简单但是麻烦,是我最讨厌的难写但是能过的那种题目,跟上次PKU的A差不多,真是辛苦蓝蜂了:P

我在一边很快找到了C我的代码的问题所在,改变了几个值,同时对剪枝强化了一下,提交后AC,开心^___^

这时候我把所有的题目都好好看了一遍并且简化成了数学模型,A无疑是一个母函数的DP(事实证明这样做也是不对的,真正的标程是递推),B是一个计算几何题,人工来思考很简单,但是用code实现太麻烦,C就是一个01背包的变种,已经被AC了,D是一个模拟题,简单但是麻烦,E就是最短编辑距离,经典DP,但是上次龙飞来说过后一直没看,最近在写搜索算法,自己想了一下觉得太麻烦,就没写了

蓝蜂把D写好后测试了几个数据都OK,然后提交,但是WA掉了,他想了想重新测了个数据,果然有问题,这个时候他把代码打印出来在一边处理,我把A用搜索写了一遍,提交后TLE(不TLE才怪了),然后感觉用搜索出不来,把机器让给蓝蜂调D,我去看他的D决定自己去试试看

弄了比较久蓝蜂的D还是有问题,于是跟他说这个我来试试看,跟他说清A的意思,让他用母函数解决

我上机按照他读懂了的题目很快写出了代码,跟他一样,前3个条件(回文,只由两个数字组成,步长1的递增或者递减)都很好解决,最后一个循环的条件不好判断,不过我的是用数组实现的,调试相对容易,多花了些时间但是也搞定了,把所有可能的数据自己测试了一遍提交,AC通过

这时候A是蓝蜂在做,我看B能想出算法,但是计算几何实在是搞不定,而E我把问题复杂化了,反正时间也不多了,就当是进入垃圾时间了

OVER

晚上看解题报告发现C用搜索实在是幸运,本来这个也应该用母函数来解决的,不过数据比较小(是最坏情况,不是钻数据空子),并且我想了想按照我的剪枝绝对能PASS的,最后看Status,我的代码还是最快,最小内存,最小代码长度的^__^

E那个DP其实和LCS是一样的,但是我把问题复杂化了,so…不应该啊!!!!!

B的算法和我想的果然一样,不过我还没有考虑两根线重合的情况,但是就算算法对了写不出来也是白搭…-_______-b

A龙飞说是递推,没人过所以没有解题报告,但是Knuthocean说了他看了代码后的理解,不过还是没有看懂:(,太麻烦了,看标程的代码,也看不懂:(

感觉最失误的就是没有去做E,虽然自己以前没做过,但是想想也应该不难的,尤其是一开始自己就把问题复杂化了更是不应该,最后的rank一点也不好看:(

今天的PKU monthly

今天PKU的monthly,有钱,估计会吸引更多的人,并且现在是各高校集训时间,人会更多.事先去调查了一下,发现能过一题基本就能保证top100了,看到的最差是top125,最好是top45.前面12次loutiancheng拿了4次冠军,-____-b

今天开始分组弄,暂时还是2人组,偶的N多队友提议都被枪毙:(,不过也好,看看自己到底什么水平,其实大家也都是很不错的,刚好取长补短

一开始和蓝蜂分工,他从前面开始,我从后面开始,一开始他就耗在A上面,我也觉得不是很难,只是处理比较麻烦(偶最讨厌这种了)

我因为是换机器用,等把东西调试好都过了很久了,快速把所有题目扫描了一次,觉得H是最容易下手的,开始写,很简单的题,只用了不要一屏的代码就搞定了,在纸上推了一下提交,WA    T_T

重新考虑了一下,发现题目中的C完全是一个陷阱,根本不需要用,结果一改,代码更简单,AC了,但是时间都快过了1个小时,这个时候队里N多人都已经AC好久了,就是我排在后面,真是一失足成千古恨啊

然后看F,感觉是个DP题(事实上也是),但是数据量N大的说,虽然时间也有20s,写代码后感觉不好处理,估计会超时,蓝蜂说你写了就交吧,提交后等了N久,TLE     T_T

把能优化的地方全都给优化了一遍,感觉时间复杂度还是降不下来.10^6的输入数据,做出来至少要10^12的数量级,20s绝对不够,不过抱着死猪不怕开水烫的心态还是submit了一把,TLE,决定放弃F,这时已经过了2个小时了

把所有的题目再扫了一遍,还是没有可以下手的,于是看蓝蜂写A,他弄了N久都没出来,而这个时候一个机房的人都在弄A.我准备玩的时候被人说了一下,于是开始写A,基本算法已经在脑子里了,就是判断上下两个对应的数字就可以了,使用分开调试的方法花了一个小时左右基本搞定,但是发现数据大了就不对了:(,感觉是精度的问题,于是把需要大数据的地方都改成了long long,结果还是在非常大的数据量的时候有问题(感谢Grope提供了几个大数据的输出,不然怎么死的都不知道),后来调试的时候发现long long=long*long的时候long long得到的还是long范围内的值,一气之下把所有的long都用long long替换掉,看了看自我感觉良好,提交

这个时候N多的人在做F和D,都是限时超过20S的,等了半天才等到我,看时间已经剩下不到20分钟了,而机房没一个人搞定此题,焦急的等待绿色的Waiting变成Running,然后看着变成蓝色的Accepted,差点没幸福死

最后就是这样了吧,其他人也都没有AC,其他题目也还是下不了手

第一次在队里排NO.1,好爽…

今天的PKU_Team_Exercise_1

发信人: snoopy (★C.S★ ☆阿排☆), 信区: ACM_ICPC
标  题: 今天的PKU
发信站: 珞珈山水BBS站 (Wed Jul 27 21:01:19 2005), 转信

刚才看了看,原来是Team Exercise 1,knuthocean跟我说如果组队应该可以过更多,我同意

今天吃完午饭过来机房的时候已经快开始了,开始的时候迅速打开了8个网页分别看8个题目

第一个A看了一下就是递推,公式应该不难出来,往下看了看数据,高精度,应该用加法就可以
完全实现了.因为扯上了高精,就懒的第一个写,继续往后看,B瞄了一下图,但是没仔细看题目
,感觉应该也是比较容易的,然后是C,感觉还是几何题,看到D的时候马上决定从D开始,因为D
实在是太简单了

稍微看了一下题目理清思路就开始写了,很经典的汽水瓶换汽水的变种,提交WA,回头看了一
下代码就知道了,最后如果n==k没有考虑(不是没考虑,是写漏了),把>改成>=,AC

按照自己排定的难易顺序接着做B,发现题目不是我一开始想的那个,重新理了思路就在推方
程,想一步得出结果.但是发现无法得到一个式子只有一边有未知数的,发呆了一小会突然恍
然大悟,不就是二分迭代解方程么,很快搞定了代码,提交后WA,回头看了看感
觉公式没问题,把求解精度提高了一位,提交后就AC了(居然是这里出问题,典型菜鸟)

然后就是A的高精度了,一开始推递推公式的时候出了点问题,还好机房的其他同学从测试数
据上看出了错误.把以前看到的类似题目套了一下,发现公式错了,然后重新在纸上画了一下
就得出了s[i]=s[i-1]+2*s[i-2]的结论,s[1]=1,s[2]=3,(这里为我的WA埋下种子了),一开始
没用高精,只是算了一下验证正确性,把题目提供的测试数据中非高精部分都过了,然后放心
写高精加法了.提交,WA,马上怀疑我的数组开小了,但是20*6这么长的数字绝对可以满足题目
需要啊,但是为保险起见,还是把20改成了30来存储每个n对应的结果(数组每个元素纪录6位
数字,其实完全没必要开这么大,有20*6已经完全够了),同时确认了一下输入0的时候的输出
结果,Knothocean说是1,改了后AC.

回来看看C发现就是把一个圆锥面展开然后求扇形上两点之间的距离(平面几何),把公式推导
出来,然后考虑了一下特殊情况,两个点的最小夹角如何判断的问题,把测试数据过了后提交,
WA(今天的第四次,真是…),回头自己测试,发现虽然考虑了特殊情况,但是没有有效解决(汗
自己一个-___-b),仔细把代码调整好后就AC了

此时4WA4AC过4个,还算比较好的,并且时间也比较充裕(才过了2个小时,并且中间很长一段时
间还在休息-__-b),看后面的题目,发现意思都不好看懂,于是等Knuthocean和ddoonn_cc,他
们说G是国际象棋,听懂意思后发现不懂国际象棋的规则,于是baidu一下,到维基百科上面去
找到了规则,发现算上兵的升变什么的状态太复杂了,并且Knuthocean和ddoonn_cc都说太难
,不好处理,加上自己也比较懒,不太想写,直接去玩去了-_____-b非常不好的习惯和不好的心
态,H看了小强他们的讨论是欧拉图,不懂…

到快结束的时候mast和index过了E,Knuthocean和ddoonn_cc过了G,但是本来就没什么打算的
我什么也没过:(
总结:今天的做题策略中顺序部分还是安排的不错的,A做的稍微晚了点,做C之前居然还去发
了那么久***…可能是心里有些侥幸心理,反正现在不是比赛,后来剩下的3个小时居然就按
照Knuthocean和ddoonn_cc的话没做G了,E看不懂也不去看…

PS:最近几天听课郁闷死了,昨天的组合数学就几乎完全没听懂,下午龙飞GG的DP也只是把自
己知道的给复习了一遍,不知道的都和什么母函数有关,前天看到通知说要看书的时候已经没
时间了,今天上午也是同样郁闷…衰啊


RPWT is RTE PE WA TLE. ACMer记住了!!

※ 来源:·珞珈山水BBS站 bbs.whu.edu.cn·[FROM: 202.114.121.*]

集训感受[2]

昨天听课郁闷了,并且晚上还在折腾那台SIS+SATA,不过弄好了,但是没有写BLOG了,现在补上(27-07-05)

昨天在群公告里面看到要看组合数学的时候已经晚了…加上贪玩,也没太注意,结果上午一直被郁闷到吃午饭,基本都是不懂的,而Knuthocean居然听的是津津有味-___-b

下午龙飞过来讲DP,开始还是听的比较顺的,毕竟学过也用过,但是到后来的DP时,一和组合数学中的母函数扯上去,大脑马上down掉,一直就在发呆.痛苦的等龙飞把DP讲完然后和N多也是听的同样或者比我更郁闷的吃饭去了.

晚上去ZOJ找了简单题回复了一下自信,才算没有郁闷到底.

看来还是有些东西应该是先好好学学的,不过个人感觉集训的时候好像没什么时间可以好好静下来学学书本上的东西的,可能是我太敏感而不能安心吧.

PS:晚上吃完饭和回去后很长的时间内都在摆弄该死的SIS+SATA组合,晚上终于借软驱和软盘搞定了.happy一个

集训感受[0]

决定每天发一次感受,来总结一下这个暑假,希望每天都能有所收获,来源snoopy@bbs.whu.edu.cn

发信人: snoopy (★C.S★ ☆阿排☆), 信区: ACM_ICPC
标 题: 关于今天的RP和做题策略(总结)
发信站: 珞珈山水BBS站 (Sun Jul 24 16:29:03 2005), 转信

本来昨天被MAST激的决定今天一定要超过老杨而成为第一个AC的,结果是我第一个AC的A都到了一个小时以后,比Knuthocean慢了接近一个小时,更要命的是我居然还WA了一次

总的来说今天的做题策略很有问题,一开始看的A,感觉还可以,但是被那个乘方的表达式给唬住了,以为要用pow运算,加上当时错误的推断出每次%p得出的结果有问题,于是搁下了A去看其他的

按顺序过去,B看了一下,马上反应过来高精度,但是没想写,看有更简单的没,事实证明C的确比B要简单,着手写C

在C上面没有考虑32-bit这个条件,一直用long在提交,前面还提交了一个包含freopen的-___-| 确认改的没错了还是WA,这个时候最快的Cedar全过了,Knuthocean已经2AC了

重新回去写A,发现真是笨的可以,每次%p不会有任何问题,并且就是这么做的,改了一下,AC看时间是1个多小时了,并且还WA了一次-____-||

按顺序下去,写B,高精度,很久没写,手生了,不过也是比较轻松的,中间机器不知道为何慢的要死,重启一次,影响心情,AC

然后去改C,因为一直是WA,所以怀疑是写错了,别人都是PE,就我一个人在WA,看了半天还是没看出来,然后考虑那个32-bit的条件,改成unsigned long就过了

3个题目最后完成都是2个小时内,但是被罚惨了,特别是策略,如果A和C不出现那样的失误,今天未必会慢

但是ACM的世界里没有如果…那么…,所以,今天是失败的


RPWT is RTE PE WA TLE. ACMer记住了!!

※ 修改:·snoopy 于 Jul 24 16:29:22 修改本文·[FROM: 202.114.121.*]
※ 来源:·珞珈山水BBS站 bbs.whu.edu.cn·[FROM: 202.114.121.*]