省赛总结

此次省赛是acm生涯中的最后一次比赛了,虽然拿到三等奖,但是如果不是策略上的问题是可以拿下二等奖的,略遗憾,在此做下总结:

Problem A:

这道题是道水题,但是需要注意每个人的工作效率都是一样的.另外还有个陷阱,推出公式后需要化简(当然如果你觉得你精度控制没问题用double也可以),消除中间值有小数的问题.几分钟看懂题意后推出公式给沈子编码,秒A

Problem B:

看了一眼,是道模拟,由于是一眼题,一开始就由沈子编码,也是一次性AC

Problem C:

这道题也是模拟,可以做出来,但是直接编码比较麻烦,而且我们做到这道题的时候还只A两道,但是还有一道也可以做出来,当时看了下榜,前面的队伍已经A出4道来了,所以当时有点急,加上提交WA了两次,沈子可能有点急了,后来切到其他题后往返了两次还是不行,于是沈子转攻另外一道题,我尝试使用STL来解决这个问题,由于没有试过map里面用string,所以开始发现数据装不进去,蛋疼了一会儿发现是读取组数T后忘记吃掉换行了,完了使用2个map和3个list来模拟,AC.但是这道题浪费不少时间,完了沈子接着A掉了另外一道,顿时压力骤减.

Problem D:

这道题没看明白是什么模型,比赛结束之前想到了可能是用字符串模拟二进制进行位运算,但是今天在uva上开的Contest上测试是错的,是遗憾也不是遗憾.

Problem E:

典型的字典树,开始由我来编码,建树,插入,删除,查找,但是运行的时候不知道哪里越界了,调了半天没调出来,浪费了十多分钟.后来A掉C题后沈子用哈希搞定了这道题.

Problem F:

这道题应该是网络流的最小费用最大割,可惜我们的网络流是比赛前一个星期才跟上的进度,只能熟练解决最大流问题,考虑到这个模型出的比较多,于是带上了一份最大割的模板,可惜的是这道题不是裸模板题,我看了半天没看出来汇点在哪里,可惜.

Problem G:

根据经验来看应该是道递推或者排列组合问题,无奈推导很久没有结果,遂放弃,后来A完5道后继续推,还是没有解决掉.

Problem H:

京子翻译的,题意不清楚了,貌似是搜索之类的还是凸包来着,沈子复审后觉得难度较大,先解其他题目去了,后来卡到F和D上面之后就没去看这道题了.

Problem I:

也是京子翻译的,大概就是推箱子之类的问题,但是编码量特别大,后面因时间问题就没去解答

Problem J:

最长公共递增子序列,开始处理策略理清楚,浪费不少时间,后来由沈子修改模板后AC.

Problem K,L:

没审题,看了下没看出模型就放弃掉转攻其他题了.

acm生涯到此差不多结束了,随之结束的是我的大学生活,接下来的生活中,我会用我们A到最后一秒也不放弃的精神来做好每件我选择做的事情!

just do it!