The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

2010 ACM-ICPC Multi-University Training Contest(5)总结

          今天是我们第一次参加多校联合集训的比赛,比赛开始前,我们还是按照以前的惯例进行分题,我看后面,小波波看前面,阿登看中间,大概十分钟以后,我们看了下board,发现10011008已经有人过了(快得令人汗颜啊,于是我们马上开始看1008,题意大概是给你N个数,这N个数只能是0或者是1,题目让你求出不包含101的数字串有多少个。起初我们想用数学方法去计算,但是发现去重很麻烦,一时卡住了,后来小波波突然想到一个dp的方法,AC了。然后大家开始看1001,小波波想到如果所有的结点被扩展的时候花费的步数是偶数,那么输出YES,否则NO,但是用DFS穷搜所有路径的想法复杂度太高被我否决掉了,既然DFS不行,BFS行不行呢,其实结点只需要最多扩展两次就行了,如果对原图进行一下BFS复杂度大概只需要O(n),我和阿登合计了一下,觉得可行,然后阿登就开始敲了。我和小波波开始看其他题目,我看了1007,小波波看10051005要求good sequences,推公式,既然要都相同或者都不相同,那么对M做一个全排列是满足要求的,还有就是所有数是一样的也满足要求,我想了一下,也没发现什么反例,这个时候阿登的代码敲好了,但是一开始wa,我们把代码发到阿登机器上再检查一下,小波波先写代码,提交,不过一开始wa了,是算法还是特殊数据的问题?这个时候阿登说他找到了源程序里面的Bug,提交,过了。对于1005,我们发现一组特例,就是当n等于1, 其实对它做全排列和所有数字都一样其实是一种情况,另外还有一种M等于2的情况也是特例,改了一下,也过了。我一直在考虑1007其实就是一个比较典型的行列转换的问题,我记得以前在FOJ上做过,刘汝佳的书上也有提到,当时是用双向广搜,但是n,m<10,而这道题n,m<=100,用搜索肯定不行,怎么办呢,把原矩阵的第一列全部处理成0,然后用枚举目标矩阵中的每一列,再列进行排序,如果排序后两个矩阵完全相等,输出YES.这题敲代码也确实比较快,但是交上去却wa了,于是我和小波波一起逐行检查,终于发现原来是一个<=写成<了,囧啊!改了之后就过了。。。无语。我在查代码的时候,阿登看了1009,说是线段树,于是我把代码发到自己机器上,阿登开始写线段树,刚开始过这道题的人很少,就寥寥几个,但是阿登非常确定是线段树,那就敲吧。在我过了1007之后没多少时间,1009也过了。这时比赛还有大概一个小时吧,我们想再开一题,于是就各自看了几道AC率比较低的题目,阿登看了下最后一题说最后一题可以做,就是用链表模拟一下,但是对于取反操作,如果用单链表的话,一次取反操作复杂度是N,操作次数一多肯定超时,这题有点遗憾,我当时再看1003,等我看完最后一题,我觉得其实可以用双向链表的,后来大家也觉得双向链应该是正解,但是却没有时间了,只能赛后再研究下了.

posted on 2010-07-27 21:38 abilitytao 阅读(685) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理