2012-06-04

6月第一个周末比赛好多啊，做了其中的4个，很爽:

比赛	开始时间
Astar 2012 R1a	2012.6.2 10:00
ipsc 2012	2012.6.2 18:0 0
TCO 2012 R2c	2012.6.3 00:00
Astar 2012 R1b	2012.6.3 10:00

结果不是很重要，关键是又稍微思考了下, 但这样没有规律的思考是无法提高的，倒是也得想办法弄一个周期性较强的训练时间, 挨个稍微说一下吧。

• Astar 2012 R1a

题目ID	标题
A	度度熊就是要第一个出场
B	小小度刷礼品
C	集合的交与并
D	轮子上的度度熊

这场做了B和D吧, B就是很土的算1到N里面有多少个以x结尾的数, D的话我暴力了一下，大数据会超时，不过来不及想优化了, 感觉没有优化写起来就像很无聊的DP。 另外A其实是可做的，bfs一下应该就可以了, 跟印象中某ZOJ月赛一题有像，也跟今年的WF的镜面反射的题目有点相似(题型)。 感觉运气好可以晋级吧，毕竟只做了1题多一点点而已。

• ipsc 2012
  与毛哥一起搞了今年的ipsc, 用的是我们当年组队的名字 ACOrz , 可惜daxia没来一起做。稍微迟到了半小时，毛哥已经把A过了，然后看了C, F, I了。C我尝试了两三次，无果，后面先放弃了。放弃C之后就很顺了，跟毛哥一起砍了一些大众题目。依次是
  • G
    算有向图最大长度的链。由于图挺特殊的，只有一个出度，故也挺好算。
  • I
    md5 decrypt 挺好用的，直接将大小数据都过了= =国内的网站就不行，还要收费- -
  • F
    毛哥暴力了小数据，然后我们在只有两个硬币的情况下做简单演算, 得到 p1*(1-p2)+p2*(1-p1)=1/2 这个式子，直接解出 p1 = 1/2 or p2 = 1/2 , 于是也很容易了。
  • C1
    C1 后面我又试了下记忆化搜索，于是就过了= =, 一开始dp比较随意了，改成记忆化暴力所有可能于是过了。猜测大数据也是类似搞法，不过状态可能稍微多了，未作深究。
  • B
    B毛哥猜得很欢乐， B1还好，B2我们真是非常惊险，猜到第30次才得到答案(最多猜测30次)，毛哥还用啥迭代法来逼近来着。
    
    最终ipsc排名一百多名，算是本周最欢乐的比赛了，当然还有很多没有切出来, 回头可以再看看。
    

• TCO 2012 R2c
  ipsc 做到了晚上11点结束，12点就是 TCO R2c了，能不能拿衣服就看这场了。悲剧的是比赛前20分钟家里断网了，折腾了好些,搞好的时候已经12点20分了，顾不上就奔去了。300分是一个有点代码量的枚举，写到了144分。。500打开只有半小时了，看了下，这不就是土土的树状数组吗！马上搞啊搞，在最后10分钟的时候样例一直过不了，还有一个即simple的样例，没来得及看明白 比赛结束了。后面再看了下，发现题目看错了= = 顺序有点小变化，当然做法还是树状数组。感觉构造还是挺巧妙的，多增加了啥，该扣除啥。另外本次的900pt貌似也可做，没来得及看，某些人直接搞900晋级了，真给力。

• Astar 2012 R1b
  由于2号搞到比较晚，起床的时候已经是10:30了，外加还得洗碗= = 题目现在看不到了，仍然是4道题。最终做了B, C。B是二分加并查集，挺简单的。C 简单yy了一个贪心，感觉想简单了。A是算n个数中选若干数异或值的最大和次大，没想明白， 别人说是’搞基’ 。 D没有想法。 这场要晋级的话也比较悬，重在参与~

总之，整个周末还是挺紧凑以及有趣的(还出去骑了两次车)，每次比赛后都留下一些未解之谜，现在不能像以往一一攻克并提高战斗力了，不过真想把不会的继续搞懂！