GDOI2018

GDOI2018

这篇文章……或许并没有什么用处
只是一个半退役选手的满口胡言乱语罢了

GDOI2017 思考录 day-1

2018.4.27
借koi发的绿册子看去年的题目
只会前面两道题

d1t1

题意:字符串查找替换
kmp裸题,O(N^2*L)
忽然想起刚学的时候做字符串都是直接用stl的,特无耻

d1t2

感觉自己就是个大傻叉,看错题目了,狂问师兄
题意:给一棵树,求对于每个点,除了子树外其他点的mex(对于一个集合,在非负整数中没出现的最小值)
对于每种颜色,求出其lca(两两求就好),然后对于lca到root间的点,
它都是【没有在其他地方出现的值】,所以维护一下最小值就好了,O(N)

GDKOI2014 模拟赛(三个半小时) day0

早上用以前的原题做模拟赛,就我们竞赛室的几个人小测一下,据hz说又是很简单
然后第一题manacher水题
第二题网络流,但是数据有误
第三题暴力50分

GDOI2018 游记

初中oi生涯要结束了
哎前面说的看起来很简单,但gdkoi2018是真的懵逼啊……
话说今年可是我们主场呀
然后顺带一提,我们几个竞赛室的约定:有谁进了day3就请另外两个人吃饭

day1

T1

二分水题,nlogn

T2

打了个bfs拿暴力分,然后搞了搞m=2的暴力
中午听ozy大爷讲题:

  1. 先差分一波,然后现在目标就是把所有的数变成【m的倍数】
  2. 计算出当前数与上下两个【m的倍数】的距离a、b
  3. 然后就听不懂了
    讲课:
  4. 通过差分,让区间操作变成一个数+1,一个数-1,而且因为可加可减
  5. 那么这个时候,每个数字的顺序已经无关紧要了,可以先排个序
  6. 然后有一个显然的性质:一个数没有必要既增加又减少,所以必然是有固定决策的
  7. 记录决策的和,线性扫描一遍,枚举两个数中间作为中介点,当左右两侧的和相同(总有这样的位置,因为题目必然有解),则这个和就是最优解「这一步刚开始有点问题,原来是忘记最后一位的差分了,请教了rose」
    时间复杂度:nlogn
    UP:在知乎上找到了原题:51nod1357-密码锁

    T3

    暴力10分和链10分
    akc大爷:二维线段树
    rose大爷:四维KD-tree
    讲课:乱七八糟,但rose被卡了,跑了70分.
    在打球之前听akc大爷讲:
  8. 询问:「dfn1,dfn2」和「t+deprt-1,INF」
  9. 修改:「dfnx」和「t+depx-1」
  10. 维护双区间,但是如果直接两个树状数组需要n^2的空间,其实完全可以动态开点,改成线段树,
    然后这样的话,修改是一条链,空间复杂度nlogn,时间复杂度nlognlogn

T4

完全不会
讲课:还是不会
UP:在知乎上找到了原题:Uoj#12-B

总结

期望总分:100+30+20+0=150
实际得分:100+20+10+0=130
两道题都是case打wa了,不知原因,毕竟是暴力也不好复评

描述一下心路历程吧
开始半个小时看完题目,把t1切了,感觉难度不对劲,此时九点半
然后看第二题,没思路,但是部分分还是可以的,然后就写了bfs和m=2和3的情况
十点半点了,第三题感觉很难处理掉落的情况啊,没什么思路,感觉考虑深度,也推不上去啊
把小数据和链的分拿了,此时已经十一点半了
回头搞第二题,发现有m=3的大数据错了,然后打对拍,调策略,直到最后检查一下其他题目后继续搞……
比赛结束前忽然又拍出错误,发现我解决不了……(然后原来出题人也没有什么想法woc)

那么如今回顾一下,感觉前面三题真的不难,大概是一场noip+模拟赛难度,也似乎确实有人ak了
第二题其实就是个经典套路——差分,然后再贪贪心,但是因为没怎么用差分,所以没想过,而且这个贪心策略也不是那么好想的,似乎有非常多巨佬也被卡炸了……
第三题,其实打链的情况的时候也想过这个深度的关系,但是没想到「把dfs序静态化」,所以非常不可做,如今看来,其实只要把条件转化一下,然后推推关系式,发现是双区间而且互不影响,树状数组维护一波即可

那么完美的策略:
看题目:30min
T1:思考10min,实现10min
T2:思考40min,实现20min
T3:思考1h,实现40min
T4:挂机……因为我不会期望
剩余检查时间:30min

然而这场考试,重在求稳,任何一道题,如果翻车就会非常麻烦(虽然我并没有高分经验)
那么这场考试前面三题的最高预备知识是很简单的:树状数组
但是其灵活的命题,非常考验对套路的熟练使用

这场比赛,我考得相当差,
一部分原因是缺乏经验和自信,感觉难度会和koi一样,是那种ac一题就很好的那种
第二点是做题太少,整天做脑残noip题目,所以我决定接下来的一年,我的刷题量要增加500题!

总之,保持自信,相信自己,争取明天翻盘吧!目标:进day3

day2

T1

杠了三个小时……打了个60分的O(nm),虽然加了个素数优化10的常数,但本机跑了7秒……
而且我居然忘记了大样例输出文件的存在???也就是说我只知道时间,却忘记看正确答案输出了
打了个对拍,但是很sb地测1000,直接wa,然后只是去检查公式?
居然没有自己出个小的数据,或者拍小的数据
然后推了一个小时分块,没退出来,因为太久没用了,
其实就是n/(n/t),正确性其实很显然,因为整除是向下的,分母小,必然得到的最大t
总之不知道多少分,可能0,也可能60、70

总而言之,这道题不算特别难,算是莫反的一个裸题吧,
或许对于别人来说的签到题,我却耗费了大量时间,原因?
可能还是要怪中途去做noip这种玩意吧,
不知道教练口中那个进了省队刷noip的师兄是怎么想的,
或许是时代在变化吧

讲课:莫比乌斯反演
我是真的不自量力,看着题目限制没有下限,然后因为最近没用过莫比乌斯反演
所以想着yy一种替代做法,就是用总量-不互质的数对的贡献
然而当时过了非常小的样例就以为没问题了
其实稍微用个6这样的多个素因子的数字,就会发现算重复了

如今看来,其实不会也可以跳过的

T2

暴力5分
听说其实k=1不在乎顺序的时候可以组合数学乱搞,有点亏
讲课:不会

T3

暴力10分
讲课:好像是有单调性什么的,居然最高只用了链表??不是很懂

T4

题意:找出一个点所在的最小环
完全不会,然后因为感觉后面会比前面难,所以也没怎么看题目
讲课:好像floyd可以搞?

总结

感觉初中oi就这么结束了吧
凉凉的感觉
期望分数:0+5+10+0
实际分数:0+5+0+0
暴力分又炸了
怎么老是这样,不知不觉,加起来丢了30分,但是又不知道原因

现在感觉,这两天,还是第一天比较友好,但是错失良机了
然后在省选前,专题没有完整搞定,去做noip之类的,真的是自寻死路
第一天被简单题目拉了差距,第二天又拿不到分

结束了
后面,也没我什么事了
准备了这么久,并没有明显的收获吧

day3

上午听了网络流的讲座,还好吧
然后把d1t2切了
开始回到noip状态,打算快速做完以后开始搞数论
好像说我们可以延迟退役,等丰山的课程,又可以苟延残喘一会了

day4

上午颁奖仪式,最精彩的部分就是省队选手的颁奖了
那一刻,虽然说名单早就公布,依然全场安静,
所有的教练都站了起来,或许心中都带着某种骄傲之情?
有一天,我会站在那上面吗?

总结

我能感受到自己在变强,然而大家也在变强,可能唯一的优势就是我不怎么颓废?
还记得有天早上老妈跟我说:你的实力,其实很可能进不了省队
我:但除此之外我也不知道我能干什么了。不进省队也可以搞搞降分的吧
(然而其实心中依然对进省队抱有期望……)

附录

hz大佬的blog:
here

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

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