QQ20160502010828.jpg

随着最后一份成绩单发下,我的第一次GDOI就这样草草收场了。今天我在嗟叹之余来总结一下这几天以来的日程。

4.29:

由于是东道主我们并不用乘车,直接在自己的学校考就好了,实话说这个时间有点蛋疼,因为刚考完期中= =虐的我要吐了,还要马上来这么刺激的事,承受不能啊。

别校的小伙伴大伙伴五点半左右到场,我回家,没打算怎么去准备。


QQ20160502010850.jpg

4.30 Day 1

早上7点出发前往学校,买了两根士力架,领取参赛证(一袋东西),由于不知道发生了啥,8:20开考。

解压密码意思大概是 题目有毒2333 = =b 卖的一手好萌啊

打开PDF,心潮澎湃啊。

第一题,初中生数学题←这就是题目,我没记错的话题目大概是这样的:

输入k p0 n0

求当n = [n0 - pk] 时,n * (p - p0)的最大值。[x]为不超过x的整数(暂且理解为floor吧)。

有两个输出的,我只记得第一个输出了,第二个输出的话就是求分别设定两个p值p1, p2时,n * (p - p0)的最大值。

其中 n1 = [n0 - pk],  maxp1 = n * (p - p0), 然后 n2 = [n0 - pk], maxp2 = (n - n1) * (p - p0);

貌似 k p0 n0 都是实数?忘了。

这个题目是有部分分的。也就是说,他要求输出两个答案,对一个,就可以拿到该测试点的一半分。

我的做法(对于第一个答案):

既然要求 n = [n0 - pk], 那么对于pk可以组成的最大值,肯定是p = no / k。

那么我用一个for循环,i = 0 to n0,然后根据 p = i / k,计算记录最大值后输出不就行了吗?

数据范围 n <= 10^7 我这个是O(n)做法了,明显。

其实当时并不知道可不可以A..然后正解的话,待会说到讲题会讲到。


 

第二题,没错是可爱的字符串题。嗯嗯...

给定两个串S, T和k个区间,这K个区间对应在T串上的位置,表示在T串的这个位置,串的顺序可以任意改变,求:改变顺序后,S与T的LCS.区间可以利用多次。

懒(不)得(会)打暴力,因为第一个测试数据是 k = 1, n <= 10.用暴力水分的话时间复杂度是O(n! * n * m)的...哭哦

这题没做.

Yeah.


第三题,密室解谜题:

猜解密码。有K个槽,数字范围是0 ~ n?忘了,然后填进去后有三种提示:

  1. 你填对了
  2. 你没填对但真正的密码包含这个数字
  3. 你真的没填对

输入n, k,求期望最小步数。密码各位都不相同。

数学期望是啥?该买数论看看了...

还是不做。


第四题,%#¥%#&%¥%¥#%&……&题:

日哦题目描述太复杂了,我来简化一下:

输入一个图。

输入每个图的点的初始值。

然后,有三种操作:

  1. 给 x -> y 的最短路径经过的点加上一个值;
  2. (嗯..在说第二个操作前我先来说说初始值的作用吧:初始值其实就是每个点每个单位时间“生成”一样东西的数目,然后如果A到B存在一条边,那么你从A直接走到B,就会浪费一单位的时间,注意,只有当你走到那个点时,这个点才会开始并一直每单位时间生成一定量的东西,直到你走完整条路为止)求从 x -> y 的最短路径经过时,能生成的“产品”数量;
  3. 恢复到第N次修改时的状态。如果N = 0则变为初始值。

我靠,我是直接跳到了这题打算用最短路径做这题的。

然后因为我SPFA不熟,我选择了dijkstra...................

还要把dis[]用了bool储存..白白调试浪费30分钟

写出来了大概是(n^3)做法...

历史版本?直接开数组储存了...

当时估计是能过两个点的...


12:20 第一场比赛结束。

放饭,讨论。


15:30 开始讲题。

坑爹的事情开始了。


第一题正解:

数型结合,利用几何分析。

20160430_153328.md.jpg

我的第一个答案思路和讲题人差不多..分析出来时全场小伙伴都惊呆了,好吧只是我惊呆了。

第一个答案,O(n)做法,无须多说。

第二个答案!!!!!!!!!

O(1)做法!!!!!!!!!!

貌似是直接把第一个答案乘上某个数,输出!(好像是3/2)

卧槽!!!!!!!!!!!!

牛逼了...


 

第二题正解:

10%的数据肯定是暴力啦。

正解是用DP,递推式略长...没看懂,好吧。
20160430_155832.md.jpg

注意区间合并。


第三题正解:

DP!

四维数组DP!我靠逆元是什么鬼???

坚定了我要买数论的决心。

递推式两行,不说了。


第四题正解:

暴力做法20%啦。

正解是动态树做法。树链剖分 + 可持久化 + 强制在线....

日了,根本不会动态树...

持续懵逼中...


17:30 发下成绩单

第一题 50 分...果然...

第四题:

超内存!!!!!

沃日!!!!!

3000*50000*4/1024/1024 = 572.20 > 512 靠!!

做人不能太贪心啊!!!!

爆零!!!!

总分50,实话说对于我这种渣渣...我还是有点开心的,毕竟第一次参加这么难得比赛...


Day1 总结:

内存!

算法熟练程度!(然而第二天,我马上就吃了这个亏了...)


5.1 Day2

五一劳模节。七点十分起床了..

校牌不见了,只好在机房找到了借书证顶替一下...

没买巧克力...

8:00 开考,解压密码:不要帅(甩?)锅~~


第一题:

给出一个有向图,允许当 A->B,B->C时,直接连通A->C,代价修改为某个值,修改操作为lim个。

我的思路:

我!!艹!!

又是最短路!!!!!!!为什么昨晚没复习SPFA啊!!!!!

晕哦,只好dijkstra了,还是用邻接矩阵存的图,哭哦

只暴力计算lim = 1的情况,其余要么贪心,要么输出-1.

嗯。为水题而奋斗。


 

第二题:

给出一个含有起点终点的图,输出一条哈密顿回路的路径。数据保证有解。n<10.

图的元素:起点终点,障碍,桥(分桥上桥下,=这样的,在桥上不可以上下走,在桥下不可以左右走)

我的思路:

DFS啊..赤裸裸的搜索题..

于是三四题都不看了。

第一次在比赛写搜索题,写了两个小时。

样例过了,手写数据也过了。

但是!!!

最后15分钟,我写出了错误数据(桥的标记及其处理没判断好,不知道是走过了桥上,还是走过了桥下!!!)!!

沃日!!!!!

最后15分钟,无力,无力回天了。

祈祷着能过两个点。


 

第三题:没看


 

第四题:

给出一个只包含0和1的图和一个值len,你可以把任意的0换成1,但完成所有修改后条件如下;

  1. 所有的0必须连通;
  2. 所有的1必须连通;
  3. 得出1连通块的周长(与0或边界接触的)至少有一半是原1的周长;
  4. 用无限个这个1的连通块可以不重叠无空隙地覆盖满无限大的平面;
  5. 不记得了。
  6. 没有6.

要输出的就是周长=给定的len时,把0转换成1的最小次数。

我的做法:

printf("NO");

嗯。很暴力对吧?

待会你就知道了。


 

12:20 第二场考试结束,楼下因为跳闸加时20min(可怜的孩子...)


 

15:00 讲题。


第一题:

20160501_151229.md.jpg

真的是最短路径!!!

SPFA再加点东西就好了!!

唉,懒得吐槽。。
20160501_151737.md.jpg


 

第二题:

DFS + 玄学剪枝
20160501_152126.md.jpg
20160501_152144.md.jpg

讲题人不断在问有没有用网络流的....
20160501_152212.md.jpg
20160501_152315.md.jpg

祈祷能过两个点吧..

超时应该不会,但也有可能是我自己出的数据太水了,反正如果是我自己的数据的话当n = 7时, 4ms可以完成计算。


第三题:

点分治,没听懂,还有什么双连通分量,树状数组(只有这个我会)...完了,多看书啊。


第四题:

只有五个测试点,讲题人说,他没有设答案为NO。

全场泪奔,鼓掌...
20160501_155350.md.jpg
↑我的内心

然后讲题人又说其实有一个数据,把1连通块中间的洞填上了,就OK了....

哭哦。

正解是&……*%*……(&没听懂,割多边形。

出题人说这道题平均分哭死,他回去会被打死的...


16:00 讲完题,出成绩!!!

服了。

第一题10分,第二题爆零(全是WA, 而且时间全是0.01s!!!!我靠!!!顶多时间不会是0.01s吧??我做错了什么???打错了什么吗???),第四题,水题失败。

两日考试总分60.

哭哦。


18:30 噩耗传来,三等奖分数线90.

唉,完了,铜牌都没了。

我的第一次GDOI,大概也是最后一次GDOI,就这样,完蛋了。


5.21 1:05 并没有第三天,于是我只好打一下总结来弥补一下我受伤的心灵了...

大总结:

  • 我对某些算法和数据结构的掌握程度还远远不够高!虽然可能做出来了相关的题,但其实我是不懂的...
  • 差不多考完的时候,还是检查一下输出有没有问题吧;
  • 分不是那么容易水的,但还是要做一个有想法的人;
  • 词穷,没了。

感谢您能看到这里。我这种蒻蒟还是滚回去睡觉吧。

晚安。祝有下次并下次好运吧。

毕竟OI之路还有很长,也许很短。

爆照一张:

QQ20160502010839.md.jpg