浙大OJ月赛总结





今天我和即将陪我参加今年杭州赛区ICPC的队友刘利祥、王锐坚一起做了浙大OJ的月赛。查看Ranklist请点击传送门
这是我不知道隔了多久重新回归月赛。最终我们以6题的成绩排名第15,还是比较满意的。NKU的两支队伍也很厉害,都做出了5个题目,分别排名第23和第30,比我在的时候强多了。
说说这次比赛的过程以及解题思路。
首先A题,没有题目描述,输入样例就是题目描述。实际上直接看输入输出就知道题目让干什么了,最水的一题。我采取一贯的风格,继续抓紧读题,有人过了就立即敲。果然,看了没几题就有人过了A题,于是我立即去做,很快AC,而且是1y,思路很简单,一个字符一个字符的读,如果是字母就放入buffer然后继续读,不是就先处理一下buffer中的单词并输出,然后再输出刚读入的这个字符。
B题当时看完就觉得大概可做,不过不是水题,所以就暂时放下继续读,读到E题的时候因为刘利祥说I题很简单并且有一个队过了,我就去看I题,看完后不是很懂,和刘利祥确定题意后发现的确很水,只要算一下路径的总长度,然后按顺序一个点一个点的走,按比例算一下等分点的坐标就好了。交之前为了以防万一还处理了一下重点的情况,虽然并不确定会有这样的数据。提交后也是1y。
此时刘利祥在想F题,王锐坚在想E题,两题都是已经有人过了的。F题就是一个DP,难度不是很大,只是要处理一下分数。另外由于需要高精度,刘利祥决定用Java写。在他写F题的时候,我和王锐坚又一起讨论了一下此时已经有人过的B题、E题和J题,都有一点点想法但不是很确定,王锐坚说E题应该可以贪心,但我对贪心的正确性不是很有把握。B题我没有注意到测试数据组数很大,单纯的以为枚举就可以,推出了一个方法,结果造成一次TLE,另外刘利祥提交F题的时候交成了B题,又造成一次RE,还好F题是1y。
这时王锐坚去写E题的贪心算法,写完后提交WA了。我们怀疑有可能贪心不对,但是后来越想越觉得贪心没有问题,不过还是暂时放置了。其实这个时候王锐坚提出可能trap的顺序可以任意,但是由于题目中没有说,被我否定了,这是我的一个错误决定。
然后我和刘利祥讨论了一下C题,觉得有门,我就去写。当时C题想的很复杂,复杂度最坏情况下都到10亿了,写的时候才发现有更好的思路。首先先求0点为起点到其他所有点的最短路,然后求的过程中可以得到一个序列。顺序扫一遍这个序列可以求出由0点出发到每个点为止的最短路有多少种走法,逆序扫一遍可以求出由每个点出发,到后面所有点的最短路有多少走法。要求的结果就是这两个值的乘积。写完后提交又WA了。这时候我们已经卡在两道题目上了。
此时,刘利祥和王锐坚已经又考虑了一下B题,进一步觉得贪心没有问题。然后我只好听从他们的建议,修改王锐坚E题的代码,对数组d进行排序后再算,竟然奇迹AC,这里白白卡了我们这么久。
然后王锐坚的B题也已经想出了一个方法,化成了类似于A*B=D的式子,D已知,要求A和B的话只要枚举分解就行了,枚举分解应该会少很多,速度应该能提高。于是他去写B题,我和刘利祥一起过一遍我C题的代码。一起看了很久也没发现错误,突然刘利祥说可能最后一步乘法出了问题,每个数不超过10^10,乘在一起不超过10^20,这样就超过long long了,应该最后一步用一个小高精度的处理。于是我打断正在写B题的王锐坚,把原来的(A*B)%mod改成了A/100000*B%mod*100000%mod+A%100000*B%mod,其实是个等价变换,也可以看成是100000进制的高精度乘法。这样提交就AC了。其实主要算法都对,竟然卡在了这种地方。
不一会,王锐坚说B题也过了,效率真高。然后我们一起看了看Rank,发现还有D,G,J也许可做,此时还剩下40分钟,我又重新看了一下G和J,花了10来分钟仍然没有思路,而刘利祥把D看完以后说这题不难。跟我们讲了一下,果然可做。于是我简单敲完读入部分后换刘利祥继续写。但是这题还是需要写一小会的,最后20分钟来不及写完,比赛就结束了。
这个成绩还可以,如果在现场,估计是金银之间的水平,期待现场能发挥的更好。
这些题目除了E题有点描述不清的嫌疑以外其余题目都不错。最后附上watashi大牛的完整解题报告传送门

本文来自Dora Blog,题目为浙大OJ月赛总结,转载请注明出处。
如果你喜欢我的博客,请订阅本博客的RSS以更方便的阅读
欢迎关注我的新浪微博:http://weibo.com/diaorui1987