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一点也不好看:(