2020浙江省程序设计竞赛小记

Posted by

这次浙江省省赛还是比较幸运的,刚好在铜牌线上面几个名次,没有打铁,比赛结束的时候一直以为一定是打铁了…中间掉线了一次,我是用自己手机的热点给电脑网络的,然后刚好打到一半的时候,电信因为我手机欠费把我电话给停机了,造成了几分钟的混乱…所以说下次比赛前应该先把话费充好.

比赛前准备是随机开ADE这三题,我最开始是在读A的,陈浩发现E题的标题是<< Easy DP Problem>>,由于我前段时间写的DP比较多,于是我们交换了题目,也就开始了我接下来五个小时的噩梦…各自读了一会儿题目后发现A题已经有人过了,于是判定A是此次的签到题(其实它不是),戴总就去写A了. 起初我判断E应该是一个通过滚动数组优化的普通DP问题,于是开始尝试将二维压缩成一维,这里花费了一些时间.然后过去了大概三四十分钟,我们还是一题没出的状态,看了一眼榜单,似乎后面的K才是签到题,于是我和陈浩就开始读K了.陈浩读的快一些,并且很快想出了解法于是他就先去把K给过了,此时时间大概是51min.A题是一个模拟题,戴总交了一发后发现TL了,主要是每一个年份的差值运算上嵌套了一个循环,导致时间复杂度太大,后来讨论出一种初始化打表并且使用前缀和计算的方法优化时间复杂度,并不是非常顺利地过了A题.后来我对E题也有了新的想法,它是类似NOIP提高组初赛中的一种题型,根据给出的代码来推断这个代码的究竟是使用了什么算法,再根据这个算法的性质直接写出给的测试数据的答案(在得知具体是什么算法后写出答案是显然的).的确E它不是一个DP题目,而是根据DP去推出一个计算公式,于是我开始推导公式了.此时榜单上通过人数最多的是B题和E题,于是更加坚定了我是可以写出E题的信心.然后陈浩和戴总去写B题了.中间过去了大约一个小时,我们在这两个题目上并没有进展.看了一眼榜单发现I题的人数挺多的,于是陈浩和戴总去做I题了.在3h~4h这个时间段里我写出了一个E题的暴力算法,保证答案正确的情况下用来测试后续需要提交代码的正确性,并且推出E题的一个较弱的公式:\sum{i^2} + sum(m+l-1)-sum(min(m,k)+l-1),交了一发发现答案错误,于是开始Debug.陈浩和戴总在I题上也有一些进展,戴总在写了几段代码后发现题目实际上是一个图论的题目,作为图论选手的她顺利地将这道题过掉了.此时是三小时过半了,我和陈浩讨论出了正确的公式是\sum{i^2} + \sum_{i}^{k} max ({b})也就是说对b数组中最大的k个值进行求和而不是先前的前缀和求法,后来得知这种对动态区间k个最值进行求和的方法是需要使用可持久化线段树这种数据结构的.在接下来的所有时间我们都在寻找一种方式来得到这个最值,但是没有结果,一直到比赛结束我们也才写了3题.

后来听说有学长在最后十分钟开始写c题并且顺利过掉的,中间还有一些思维加数学的题目,尝试一下还是有可能冲进4题的.主要是由于我对自己的DP能力太过自信,死磕E题,没有去读其他的题目才导致这次省赛只出了3题,如果在封榜后我去读一下其他题目,这次省赛的结果可能都会比现在要好…然后暴露的一些问题:1.需要经常看榜单寻找当前能做的题目,尽量去读每一道题目可能就藏了一道适合你的;2.加强数据结构的学习,此次的B和E都是依靠数据结构才能通过的题目,在高级数据结构上的不足导致出不了这两题;3.加强练习,多写题总是没错的.

官方难度K A C I F G E H B D L J,感觉这次的榜完全被带歪了.
2020ZJCPC铜,太感动了。感谢队友,感谢学校和学院和志愿者,感谢主办方.

Leave a Reply

邮箱地址不会被公开。 必填项已用*标注