GDKOI2016总结——被虐之旅

前言

一个被虐的旅程。。。
这次GDKOI的比赛虽然基本全上暴力,但是居然只有两道题得了分:30+30=60!我感觉整个人都不好了。。。

day0

在去广州的路上,本来心情很好,但是坐在我斜后面的那位同学像往常一样抓紧时间装逼,结果我的好心情一扫而光。
晚上和舍友腐了整个晚上的电视剧。

day1

早上

8:00~9:30
我抱着一种极其不好的心态进入考场:一旦我一不小心考地很好怎么办(谁知被虐了。。。)?但是,当我打了完那个无厘头的密码后,打开了题目瞬间傻眼了。。。#¥%……&(此处省略1000个脏话)什么B~题啊!!!吓得惊魂未定的我突然想起还要比赛,于是定了定神,好,进入看题状态!“第一题,恩,题目名真神奇,又有故事看了——等等,好像不太简单诶”(汗,自言自语中)。看到第二题,一看:期望值的求法我前几天不就研究过吗,哈哈哈,能100+,接着窃窃自喜的我算了一下样例,但是在紧要关头,居然左算右算还是不知道样例是怎样出来的,好吧0+,跳过。由于前面两道题有点小(小!?)恶心,感觉有些头晕脑胀,忽略了可以做多条路的情况,就欣喜地认为这道题很简单,100+!第四题,居然没故事#¥%……看样子还是一道难题(什么题啊?)!不过爆力还是可以的,130+了(“希望越大,失望越大”,噢)!
9:30~10:30
开始打第三题了。10:15,打完了,于是我出了一些小数据检验,全过了。
10:30~11:15
开始打第四题了。“好复杂啊!就打个暴力都那么麻烦”。不知不觉,我就抱怨了半个多小时。打完了,就出了几个数据,因为出的数据太渣,都过了。没想到爆零了。。。
11:15~11:30
回到第二题,又疯狂地算数据中。最后,我还是放弃了,为什么怎么也算不出来啊!只好输出了样例。。。应该能坑一点分的,嘻嘻(后话:可恶的是,出题人居然不给过,看来下次再也不能输出样例数据了,防止出题人耍贱!!!)
11:30~11:45
还剩半个多小时了!!只能打第一题了,一开始看到这道题,有修改操作和查询操作,显然就是线段树,但是想了很久怎么也想不到如何打线段树,最后果断放弃,打了个爆搜。
11:45~12:00
检查ing,不过没检查到。心情不太好。
12:00~12:10
神游中。

题目

魔卡少女

得分:30
本来还想坑多几个数据点,想方设法打了很多优化,可还是一个点也没坑道。
题意:给出N个数,有修改操作和查询操作,查询区间[L,R]的所有子区间的异或和。
题解:因为每张卡的魔法值小于等于1000,所以可以把每一位拆开,分别存在10个线段树之中,大概就随便搞搞就可以了。

不稳定的传送门

得分:0
题意:在一个有向无环图中,每一条边都有一个用费和一个成功的概率,失败返回出发点,求最优的期望用费。
题解:没听懂。

寻宝

得分:0
忽略了可以做多条路的情况,一不小心就过了样例,最后就xx了。
题意:题意有点麻烦,大概就是说有很多个房间,在进入每一个房间前都要走进一些指定的房间才能进去,每进入一个房间都会得到一个伤害值和一个宝藏值,求最小的伤害值之和除以宝藏值之和。
题解:先打一个拓扑排序把有用的点找出来,接着建一个最大闭合图,最后做一遍网络流就可以了。

地图

得分:0
无奈,暴力惨遭爆零。
题意:给出一个矩阵,其中有一些点是不知道状态的,要求三个题目给出或自己枚举的点相互连通的方案数。
题解:大概就是插头dp。

休息时间

(晚上,和舍友腐了整个晚上的电视剧。。。)

day2

(吐槽一下下:酒店的早餐很难吃)

早上

8:00~8:40
我再次抱着一种极其不好的心态进入考场:我一定要翻盘,洗刷掉我的耻辱!于是,输入了那个“碟中谍”密码。
恩,总格字数才小于等于20,应该又是一道状压神题,可惜情节不够丰富啊。第二题,有点恶心,qt居然能活10^100000天啊!?给那么多天给我复习,还不如别活了,B~。什么!数学不好还想拖累我们#¥%……。第三题吧,wei啷!又是一道字符串题,还是回文串,我竟然忘了“manacher”。原本自信的我,瞬间崩溃了。额——小学生数学题,莫非是一道大水?神马!那么猥琐,有Sigma,还有逆元!这是要爆零的节奏啊。
8:40~9:00
我认为嘛,第一题在所有题目中,好像是最简单的,还能打分段。于是,我立刻分段的的模板打了出来。我算了算样例,美梦被惊醒了:不过样例的-1是怎样算出来的啊,莫非是传说中的博弈题(轰隆隆,感觉脑子被炸了一样),不过,我竟然没打过打博弈类的题。看来只能放弃了,不爽啊。
9:00~9:20
还是第二题的爆搜好打一点儿,于是我转战第二题。
过了一会,监考老师把第二题样例解释写在黑板上(不过我没注意到,否则就能加多20分了,惨!)
先打个质数表吧,50分应该是能拿到的,于是我打开了Pascal,进行了打表大业。先打别的题吧。
9:20~10:30
恩,“项链”,好像似曾相识的样子,不就是gdkoi上年的题目嚒!呃,不对,好像高级很多,文件还加多了“2”字!不过嘛还是回文串的题,既然不会"manacher"那就打O(N^2)暴力咯,反正也能过20分嘛。再加点小优化,应该就能坑分了。
10:30~10:50
第四题10分
10:50~11:10
好了,质数表没打完,只能打染色大战。我再次研究起第一题,但还是失败了,最终还是不清楚样例是怎么算出来的。于是我决定“直接输出”(噔噔噔噔噔!!!(汗(⊙﹏⊙)b))。不过有了昨天的经验,我决定,不能在输出样例了,出题人太贱了!所以,我分段输出了“-5”和“-200”(有点小恶心)。
11:10~11:11
对第一题的各种幻想:一不小心20分就好意思了(呵呵,无语)。
11:11~11:30
为什么两个多小时还没打完表!算了,break掉吧。诶,不行,代码限制,只能打在程序中打吧。最后,我还是放弃了打表,直接打第二题。
11:30~11:50
小学生数学题,爆搜!
11:50~12:10
checking。

染色大战

得分:0
题意:给出一个矩阵中,两个人轮流把一个白色的格子变成黑色的,如果出现了22的黑色格子,那么获得该22黑色格子的所指定的分数,并可以再选一个(直到矩阵全黑为止),假设两人都是大神,求两位大神的分数差。
题解:博弈记忆化爆搜,状态压缩矩阵的状态,当前状态要转移到字节最优状态就可以了。

QT与泰剧

得分:0
本来20分可以拿定了,但是看错了题,以为要是质数就不能选。
题意:给定区间[T+1,S],求区间中被3整除且不全由2,、3、5、7组成的数有多少个。
题解:数位dp。

项链

得分:30
虽然是爆搜O(N^4),但由于太优美,坑到30分。
题意:有一串项链,求用其中一段重新拼成的项链是对称的的项链的最长长度。
题解:大概是把字符串复制一份,弄个manacher什么的,就乱搞一下,貌似就可以了。

小学生数学题

得分:0
题意:求(1+1/2+1/3+1/4+···+1/n) mod p^k的值。
题解:各种乱推。

day3

开学

尾声

惨。

感慨

这次比赛看到了很多的大神,感觉智商吧啦吧啦地往下掉。。。

总结

一、看题不能用太多时间,否则会耽误打题的时间。
二、打完题后要多出点数据来检验,以防前功尽弃,想想:当看见辛辛苦苦打完的题居然爆零时,是不是就好像世界都塌了一样。
三、不要把题目看得太简单,要知道,像这种比赛,对于我这种小渣渣来说,是不可能会简单的。
四、如果前一天考砸了,千万不要想着要翻盘,“希望越大,失望越大”。
五、想方设法大水法,重中之重。
六、保持一个好的心态,不要胡思乱想。

原文地址:https://www.cnblogs.com/chen1352/p/9008506.html