Daily Log

HAOI 2018 快到了,日子要紧张起来了呢。

记录一下每天的进展,考试的总结分析,以及算法复习的笔记。

3 / 14

上午打比赛,用的是之前雅礼的 NOIP 模拟赛,实际上是一套 AGC 的 CDE。

看 t1,看起来是比较经典的题目,尝试套用常规套路。得到了一个复杂度有点差的算法,但是感觉卡卡常可以过,并且没有更优越的算法可以实现,就写了一下。写完后本机测试 15s+,尝试卡了卡常优化到 2s - 3s,问了一下 std 只用跑 0.4s,感觉大概是算法错了,试了试删掉几个有优化空间的操作发现也只能跑到 0.7s,感觉继续卡常没啥前途,就先放弃 t1 打了 50pts 的暴力,看了看时间大概是 9:30。

看 t2,发现了几个比较显然的性质,能够处理比较小规模的情况,看起来有 10pts - 30pts 的样子,再往下撕烤没啥进展,期间想到了一个自以为正确的算法就很快被叉掉了,差不多到 10:40,目前手上暴力分没拿多少,感觉有点慌,去补了 t3,写了个删直径的贪心,不对,冷静分析了一下发现实际上是个树 DP,写完后怎么都过不了大样例,这题没法写暴力,眼查也无果,手完了几个小数据后终于发现问题,最后时刻改对了。

这时候时间已经到了,但是 t2 还没写,就强行加了二十分钟补了补 t2。

下午出分 50 + 0 + 100,t2 的暴力分没拿到,懒得查了可能是细节问题。

这场策略的主要问题是没有快速的把暴力分拿到,实际上这场的暴力分实现起来很简单,可以快速的拿到基础分,导致后面手忙脚乱。题目上的问题是 t1 没有考虑额外的组合意义,思维江化,t2 没有深入的撕烤,没有完全用到题目给的条件。

讲完题后把 BZOJ 的锅补了一下,一个二维偏序的傻逼强上了个 分治 + BIT。

上一场 CF 有个题是 FFT + 特征多项式 优化矩乘的,发现差不多忘完了,准备明天再过一遍,顺便把 FFT 与特征多项式结合的那一块也给开了。

晚上补一下前几天 CSA 的 G,然后颓一把饥荒(雾。

3 / 15

上午到机房后开始复习特征多项式 $k^2$ 处理矩乘的算法,加深了一遍印象,感觉考场上可以写出来了。

尝试开用 FFT 优化的那一块,Google 了一圈都没发现啥能看的资料,就咕咕咕了。然后看了一下 fhqTreap,就去吃饭了,中午颓了一会饥荒。

下午把 fhqTreap 实现了一下,写了一些那两个经典平衡树的板子题。然后写了一个 UVA 上一个可持久化 treap 的板子题,算是熟悉这个 ds 了。本来想补一下 BZOJ 上之前没写的 treap 题,看了几道感觉题目都有点无聊就没写。

报名了山西的七省联考,听说 HA 不少人去,算是个不错的锻炼机会吧。

晚上看了一下上一场 ZROI t1 t2 的题解,感觉 t1 考试的时候已经想到了接近正解的东西,但是就是没有接着往下想,被传统套路局限了。t2 的话大概还是智力问题吧…很简单的一个题,总共有四个维度限制求极值,利用离线省去一维,利用线段树解决两维,然后剩下一维只需要求三个维度下的最优值就能判定是否能取到最优解,考场上没有想到利用长度的限制来建线段树。

晚自习打饥荒~

3 / 22 | 雅礼集训 2018 Day 0

赶路,隔膜,写水题。

3 / 23 | 雅礼集训 2018 Day 1

上午考试,点开题后有点心态爆炸,这真的是..强省省选的难度吗???

前两题一个小时签到完成。第三题是个交互,发了一些比较显然的性质,先拿了 40,很容易得到了满分做法,但是感觉不太好写啊(考场上石乐志),感觉来雅礼集训的人整体水平不高,240 感觉稳了,就交了去水群刷即刻了。

下午出分震惊了啊,30个 AK 的,我可能有点傻逼啊..

然后几个人讲了几个自己选的题,都做过,就没听。

晚上回酒店写题隔膜。

3 / 24 | 雅礼集训 2018 Day 2

上午睡过了一会,没位置了就坐在最后面了,讲的题目都做过,算是复习了一遍。

下午讲微积分,感觉没啥用,没听,去 BZOJ 上写了几个水题。

晚上在 UOJ 上发现了一个叫 扩展埃拉托色尼筛法 的东西,点开一个例题发现好像还不会什么别的方法做,mark 一下明天学。

3 / 25 | 雅礼集训 2018 Day 3

晚上 MCT 没戴好,早上起来眼睛有点不舒服。到了后点开题,发现 t3 是个经典最小割。感觉 t1 可能是个巧妙的状压题,t2 没学过三角剖分所以这个题可能写不了。就开始直接肝 t3 标算,推了一会建图后发现有个小问题怎么都处理不了,往复各种撕烤怎么处理问题浪费了不少时间,到了十点多突然发现看错题了,没有看到一个比较重要的条件。加上那个条件后顺利得到了建图,通过了样例。

然后时间已经不多,没写拍,匆匆的补完了前两题的暴力。

下午出分,前两题的暴力分没丢,t3 只有 25pts,眼睛不太舒服所以听讲题不太方便。大概 t1 是个裸的 DP 套 DP,这一块不太熟练所以没写出来。t2 是个平面图分治的最短路,类似的题其实是写过的,但是考场上忙于写 t3没有认真思考。t3 是建图挂了,思考后发现我对这个模型好像并没有完全理解,讨论限制的时候忽视了一些情况。

总结一下还是一句话,避免情绪波动 + 积极对拍。

晚上开坑。

3 / 26 | 雅礼集训 2018 Day 4

考试,看 t1,感觉是个 sb hash 签到题;看 t2,好像是个计几,没有明显的思路;看 t3,区间 sort 这一类的题目只做过一个用类似整体二分处理的题,显然不太适用这个,但是 60 分的暴力还是好拿的。

先写 t1,写了一半后出题人发了通知说题意错了。改了题意后发现好像没那么 sb 了,撕烤了一下好像不太会用 hash 处理,上了个厕所冷静下回来突然意识到这好像是个 kmp,好像还是之前 usaco 的原题,就直接写了,写完后差点没看到数据范围有 6 个 0,赶紧优化了几个 xjb 处理的地方以及加了手写的输出输入,拍了拍感觉稳了。

然后补了 t3 t2 的暴力,感觉 t2 有突破的可能性就放弃 t3,尝试猜了几个结论都错了,中间还尝试用拉格朗日乘数处理,但是我三角形的面积直接用叉积表示了,导致推导异常麻烦,最后无果,然后坐到了结束。

下午出分,没挂题,rk12,排名能看了一点,长舒一口气。

讲题,t1 听说有 hash 做法,出题人似乎没讲,t2 确实是拉格朗日乘数,但是应该用三角函数来表示三角形的面积,没做出来算是这一块还不够熟练吧,t3 是个没见过的套路,对于所有有序的区间用一个平衡树维护一下,然后每次合并分裂即可,显然总合并分裂次数不会太多。

难题讲解的时候头疼,咕咕咕。

晚上写了个扩展埃拉托色尼筛,熟练了一些,争取明天出份总结,然后补了个 LCT 题,细节没想清楚 wa 了三次。

3 / 27 | 雅礼集训 2018 Day 5

考试,t1 刚看的时候脑子丢了,不会,t2 看起来不太能做,t3 好像是个树剖优化一下 DP 啊,考虑到前两题不太会就去写 t3 了,写写写调调调到十点搞定。重新看了一遍 t1,会了 30 分的容斥,写了一下,剩下的分感觉有点鬼畜不可做,先溜了,看 t2,冷静分析了几个性质撅腚打个 30 分的暴力走人,最后时间不够没打完。

出分后没挂题,大概 rk22 的样子,感觉还行。

晚上写了几个筛的题,感觉有点累,笔记先咕咕咕。

4 / 6 | 九省联考 Day 1

晚上没睡好,翻来覆去到三点多才睡着,早上氪了杯咖啡续命。因为有了 WC 的经验,所以决定这场最后至少留二十分钟冷静的时间,不再去拿分。免得出现手抖压线改题导致 CE 的问题。

不给 vim,所以只能拿 devc 魔改一下当编辑器用,因为 devc 支持预载代码模板所以格外显得好用?拿到题后开始看题,T1 博弈菊花一紧,简单过了一下题意没撕烤就去看后面的题了,T2 看起来是个挺可做的题,T3 好像挺鬼畜,先放放。

感觉 T2 可做,暴力好打,快速的打完暴力。冷静分析了一会脑补出一个做法,因为挺好写的所以就没考虑正确性先去实现了一下,放那里拍竟然没拍出什么问题?于是我半小时 A 掉了 T2 ?好像有点开心啊,先放在那里让他拍,开始做 T1,数据范围奇小,那是不是可以状压呢,很容易可以发现所有状态都是从左下到右上的只走两个方向的路径,也就是不同的状态数只有 $C_{20}^{10}$个,那直接爆搜 sg 就行啦。

准备开始写的时候看了眼拍,发现拍出了错误,那就先去修 T2 的 bug,画画图发现似乎不是代码写丑了而是正确性有问题。不慌,对着那组 hack 数据开始想怎么处理,尝试改进了最初的做法成功过了 hack 的数据,用了差不多半小时,然后继续放那里拍,不一会又拍出个错误,来来回回改了三四次算法,发现总有几种情况照顾不到,拖到了十点半还没有进展,感觉不能继续肝下去了,先去写 T1。

本来以为可能会难写一点,没想到一会就写完了,差不多到十一点的时候通过了所有样例。舒了一口气,T3 现在手上还没有分,简单看了一下题,很容易想到裸的暴力做法,看了看数据范围大概是 35 分,时间给到了 8s 所以可能还有更多的分?没那么多时间拿别的分了,快速的把这个题的暴力补上,差不多到十一点半,开始尝试在 T2 上挣扎一下。

把拍出来的一组 hack 数据画了一下图,想从那个方案中获取一些灵感,撕烤过程中突然发现那个好像每个点实际上是他的 DFS 序遍历的结果?写了一下放那里拍,没什么问题,因为这个时候数据生成的是一个部分分的数据,尝试自由生成发现果然出了问题,对着表看了一下大概是有 55 分的样子,值了,拿掉走人。

最后半小时,检查内存使用情况,检查下发样例输出是否正确,检查文件输入输出,检查 c++11 + O2 的编译运行情况,检查代码逻辑,提交。

下午出分,100 + 60 + 55,无挂题。

SX 省内排名 rk3,前面是 mjl 100 + 60 + 95 和 ljt 100 + 60 + 60。mjl 暴力优化了一下多过了 t3 的分,ljt 多写了 5 分的部分分。

正常输出吧算,丢人了。

4 / 7 | 九省联考 Day 2

心态平和了点,所以晚上睡眠还行(挠头。

拿到题后,T1 题面好长啊,先跳过了,T2 题意很简单,然后恶意出题人还在提示上说题目不难,那可能是个不可做题了,T3 似乎是经典的 sam 上线段树合并的题目,类似的题目写过一万个啊,打了暴力,然后开始码码码。

一个悲伤的故事就是我把 sam + 子串定位 + 线段树合并 这两三百行的模板无脑写完后,发现好像并不是很会处理一些特殊的情况,挣扎到了十点多就放弃了。去看 T1,大概经过了这样的心路历程:

题太长不想看 > 发现只有这个题能做 > 看完题发现暴力匈牙利复杂度很正确 > 发现匈牙利不能处理一个点对多个点的情况 > 改成 dinic 解决匹配 > 发现复杂度不对 > 发现判断是否存在增光路可以 O(1) > AC

愉快的解决完这道题,又挣扎了一会 T3,发现还是不太会处理,无奈暴力走人,T2 打了个随机选边走人,估计可以拿 10 分的样子。

因为前面挥霍时间太多,最后只剩十分钟走检查的程序,还好没出现什么问题。

下午出分,100 + 10 + 0,t3 写的暴力挂了,SX 省内 rk2,前面是 mjl 80 + 50 + 0,现场只有我的 T1 过了。

总分 SX 省内 rk2 的样子。

总体上来看这场考试我应该是认真对待了,虽然成绩还算能看,但是问题也很明显。就是刚拿到题时头脑不稳定导致对题目难度和解法的误判,使得前期时间浪费过多,还好这次题目整体来说没有过于恶心的地方,可以用较短的时间拿到标准分,否则可能会出现一些比较糟糕的情况。

4 / 16

今天模拟赛,没有发挥好,假如这场就是 HAOI 有进不了队的风险,所以简单总结一下。

首先是上午,时间分配上前半个小时读完题后大概就确定得分了,t1 是个提答,无脑做有不少分,t2 看错题,以为是个最小割可行边问题,t3 SBDP。大概快速拍完 t3 后就开始写 t2,t2 一通写模板也没用多少时间,而且在我错误的题意理解下可以通过所有样例,就没管别的,写完后就做了几个 t1 的点,然后中间看群里有人说 t2 的题意问题,讨论了一下发现我是个假做法(这时候还没发现看错题了),然后甚至想不出来别的做法,心态爆炸坐到了考试结束,也没再去拿 t1 的其他分。

接着是下午,看到 t1 发现是个之前做过的题,t2 没注意到一些条件想了个假做法,感觉是个傻逼题,很好写所以想去想 t1 了,想了一大概有半小时就想到了正解。然后决定先写 t2,刚建好文件就看到了那个限制条件,然后就傻逼了,思考了一会不太会,有四档暴力,每档还都要写不同的程序,所以决定先去写 t1,然后计几日常翻车,基本调到考试结束还是过不了拍,最后匆匆补了 t2 的暴力。

最后出分 50 + 45 + 100 + 60 + 20,没挂题,但是并不影响总体上策略非常失败。

因为上午只有三个半小时,而一道题过拍平均大概要消耗一个半小时,所以考场上最多只能做到 一个正解 + 一个高分暴力 / 正解 + 一个低分暴力。这就要求考场上不能消耗过多时间在无谓的撕烤和试错上,而且如果高分暴力或者正解挂掉就很可能意味着没法做好这场考试的区分度,所以读题很重要,拍很重要,不能压缩检查程序的时间。

大体制定一个上午的节奏,三个半小时的时间,半个小时看题,两个小时拿到基本分,半个小时争取更高的分数,半个小时走检查的程序。

下午就更不好办了,只有两个半小时,同样半个小时读题,因为只有两个题,而且整体来说题目可能难度偏高,所以争取一个正解 / 高分暴力 + 低分暴力就能拿到不错的效果,简单估计一下大概就是一个半小时的时间,最后半小时走检查程序。

求稳。