ZOJ Monthly August 2008 and SRM 414 and dd's Contest

今天做了两场比赛,ZOJ Monthly和SRM.
总体感觉还是不错,coding速度有待提高.思路准确性不够.coding准确性尚可.
ZOJ去晚了,做了几道弱智题,拿了rank 60.其实早去半小时,就能top 25了...
ZOJ月赛好多人组队参加...下次考虑和jl等人组个队.
SRM,基本发挥水平,250+500全部Pass,可惜250和500开始想的都有问题,加上我C++的coding速度很慢,最后加起来也不到500分.我那个room都是强人,六个red...于是cha人的时候,打开一个代码,就提示我这个已经被cha了,再打开一个,又提示...最后一个代码也没看完就都cha干净了...现在rating是1671,涨得不多...

对了,还有dd的一个模拟赛,那个我写了三道题的标程.交到TOI的时候,第三题又因为%lld和%I64d的问题挂掉了...我忘了TOI是Linux系统,直接交了%I64d...

ZOJ Monthly

中午去图书大厦,下午回到家,winsty告诉我有月赛...然后那时候人家都比了一半了.
这次月赛是ZOJ内部集训的题目,于是某道题我就得利了...可是重写的程序精度还是出了问题,最后2Y掉.就是1008题,这题AC率好低...传说中的万人坑.
然后1006,1002和1001都1Y掉了.

1008
这题注意精度,十分注意精度...没别的了.

1006
统计每个数在a和b中分别出现的次数,然后对每个数对应的两个次数取个最小值,最后把这些最小值都+起来.用了map和迭代器,STL果然好用.

1002
小学奥数题,竟然想了半天没想出来...后来MM群里有人提醒我(HL牛?),就是那个一个人牵着一匹马(一头驴也一样...)从A走到B途中要去河里喝水...问最短路径...后来又扯到Fermat原理...但不管怎么说,就是作(b, 0)关于三角形那条斜边的对称点...然后对称点和(0, a)连线,求出这条连线与斜边的交点,就是反射点...没有精度问题.

1001
写个暴力,跑,然后打表...dd的题目真恶搞...

SRM 414 Div 1

第一次做Div 1,题目还不是很难.

250
这道题一开始想复杂了,一直在想怎么处理第一个表格从一天的什么时刻开始填的问题...后来发现一天最多有10^6个时刻,于是直接枚举...然后最后Pass掉.很囧...这道题白白掉了一大半的分数.

500
这道题开始想的就是正确的,贪心.可是细节处理出了问题.
算法是每个string记录当前取到了哪个字母,每次取字典序最小的一个字母.
细节上,当两个字符串当前字母一样的时候,需要比较剩余后缀的字典序.注意abc比abcd的字典序靠后,而不是一般我们认为的靠前.
一度以为时间复杂度太高会被cha,事实证明pass了.

dd_engi的NOIP模拟赛

题目难度适中.dd的题质量还是不错的.

生命游戏
纯模拟...没什么可说的,判断的时候注意边界.还有n和m的输入顺序,是先m后n.

正则表达式简化版
还是模拟...很恶心的题,这题我没写标程.

魔法塔防
这套题最有意思的一道题!很容易想到n^3的DP,其实只需要证明一点:红色的一定在最后.尝试反证法.

公司聚会
很裸的Tree DP.我写了多叉转二叉,不过dd的标程写法很独特.详情请期待dd的题解.