//zory GDKOI2018日志&游记 | Zory的个人博客

GDKOI2018日志&游记

Zory at GDKOI2018

先讲讲我比赛之前的心情:
以我现在的实力当然就是来打酱油的啦
而且因为沉迷于升学毕业之类的乱七八糟的东西,
尽管无比渴望有一天能回到像NOIP2017之前那样纯粹地沉浸在信息学竞赛中的日子,
却不得不沉迷学习日渐憔悴,有点像一场豪赌吧,赌的就是我的OI生涯,
希望我能实现目标,让高中的时候能有更高的效率弥补如今的损失。

比赛之前当然就是复习啦~
其实这几天看我以前博客复习的时候还顺便修改

2018.01.24 Wednesday

上午

颓废于日了狗的主席树

下午

颓废于日了狗的主席树

晚上

复习主席树、Qtree、欧几里得

2018.01.25 Thursday day0

上午

复习匈牙利

下午

出发……
坐车,听了一小时的歌
酒店依旧柏高,却没有当初激情

晚上

复习KMP,十点半睡觉
惯例:

2018.01.26 Friday day1

上午

早上六点半起床,其实还是有点困的,早餐人贼多
为了避免上次NOIP的失误,仔细检查了要带的东西,
而且这次居然允许试机,就赶快把文件夹完全弄好,
并且打开记事本把密码保存下来,避免心态爆炸(忠告呀)。
密码:DajiDali,chickenDinner!
感觉这几次密码都很有趣

其实题目的难度不是一眼就能看出来的,毕竟都是原创题
然而,每一道题都思考一遍之后,得出了一个可怕的结论:
没有哪怕任何一道一眼题(解释一下,是指看不出做法而不是说无法AC)
四小时暴力,犹如脱胎换骨,却也无可奈何
感觉其实复习也没有用,自己实力不够做题少的话,
知道也不会用,看不出倪端。
所以就是去见见世面,了解难度的,事实上这个目的也的确达到了。

那么讲讲题目:
第一题地铁,打Case,m=1,20分
第二题取名,暴力,20分,手推一下KMP
第三题中点,暴力,10分,不知为何错了20分
第四题排列限制相邻两数差,暴力,10分
总分:20+20+10+10=60
正解:
第一题:反向最长路(表示一脸懵逼哈)
第二题:AC自动机,太久没用过完全忘记是什么了,别人提醒才想到
第三题:(a*1000+b),二维转一维,化公式为卷积,FFT加速
第四题:不知所云……

总之也就丢了20分而已,忽然觉得初中组根本不是来拿分的,
比谁暴力稳罢了,意义不大,也拉不开差距。
很多实力超强的大佬因为各种失误居然和我分数差不多,
可想而知分数的参考意义极低。

下午

听讲课

看到传说中的马耀华,袁无为,郭嵩山

出题人好像是中大ACM队的吧,嗯严紫熙师兄也在其中咧
马耀华大佬很活跃,急于展示自己的想法

晚上

复习Manacher
欢快的狼人杀,各种蛇皮操作,骚套路……

2018.01.27 Saturday 讲课

上午

一下睡到了7:30,有点作
讲课就是那本GDOI资料集里面的内容
上午是数论入门和树上启发式合并
感觉有用的东西


然后发现自己被黄镇大佬感化了,决定等字符串复习完之后全力搞数论

下午

中午吃完饭后去和lxj去万达吃牛杂和双皮奶
然后被xgc感化决定翘课,因为感觉帮助不是太大

晚上

和爸妈去家庭聚餐
复习ExKMP

2018.01.28 Sunday day2

上午

嗯早餐人少多了,默默喝牛奶

T1是点阵匹配,跟曼哈顿距离有关系,题目的各种数据范围看起来可以打Case?
我估了估大概能拿20分
T2是最短路判断,我想了一个贪心算法,假如正确就有60分
T3是推荐序列限制区间重复,dfs爆搜,复杂度上20分
T4是给球涂色,数论题,我试图推公式,然后经过一番艰苦的计算,
惊讶的发现可以O(N)!那就能AC了

这时候大概是9:30,考试是8:10到12:10,剩下两个半小时。
这个时候做出的决定往往是关键

综合上述猜测,我决定打T4,因为T2太不确定了,
于是先仔细检查了半个小时,更正了一个错误,心里想着AC的几率很大,
当时心里满满的开心与感动,感觉很多人会没注意到第四题,望而生退,
而我坚持下来,好歹拿个AC,一等就稳了……
接着又码了一个小时,已经是11:00了。
然而,忽然发现了一个可怕的事实,某个以为能O(1)计算的某部分的值,
居然跟当前变量有关,硬生生变成了O(N^2),当即无语……
我试了试数据,发现非常慢,很可能只有10分,可能是因为逆元常数大吧,
因为我不会线性,只会用a^(mod-2),虽然套了快速幂。

但我依旧是心怀希望的,或许可以用高中某个数学公式计算出那个部分?
又或者这个东西满足某个玄学规律?于是我两管齐下,然而并没有什么卵用,
怀恨而死,最后半小时抽空把第三题dfs打了,但样例2过不去,懒得调了,
总觉得T4已经很接近正解了。

还是把这个问题共享出来吧,或许有人知道怎么算的可以评论走一波
就是F[k]=给L个球涂且只涂k种颜色的方案数
我当时的想法是:F[k]=k^L-sigma(p=1~k-1)[ F[p]*C(p,k) ]

出来以后,保守估计感觉只有10分……

下午

讲题的时候只是稍微听了听前面三题,
看到了传说中的王之栋

然后就到了激动人心的第四题……
BUT!10分做法,XXXXX,20分做法,XXXXX
彻彻底底的懵逼,完全听不懂,心态爆炸好吧,所谓神仙打架

出分数的时候更加不爽,我居然没有成绩,
跟着很多人去复评的计算机准备室,看到ACM队的大佬们
然后发现是文件没有收取到,去原本的语音4室,还好文件不会还原,
用U盘拷贝回来,然后上文说到的师兄用他的帅气macbook帮我测评,
经过各种神奇的指令,大概是连接服务器什么的,
然后看到第四题前面两个点居然TLE,无语了,我本来只是担心跑的慢而已,
居然还错了,是我模太多次了吗?调出来看,我和答案仅仅是不同,还好并不是负数。
然后最后测试T3时居然有个绿色的东西——暴力居然拿了10分,本来都快忘记了
所以就没有爆0了哈哈

总结一下

总分60+10=70=初中三等
我这次真的缺少激情,因为已经一无所有,也就没有失去时候的痛苦。
清楚自己没有多少实力,但也渴望着去改变。
希望迈上高中后,我得以有质的飞跃吧……
如果大家觉得索然无味,可以看看yzh大佬的风骚游记

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/2018-01/GDKOI2018日志&游记.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!