Day0

考试前一天看了几个模板,什么exLucas, 计算几何,带花树之类的…反正只会写暴力并没有什么卯月

本来还准备学习一下KM的,结果看书看到一半睡着了…

RP++

Day1

直接在解压试题环节gg,然后发现大家都打不开,改为纸质试题.等了大概半小时,看旁边的大佬已打完了FFT模板,要考FFT就怪了,于是一直在调vim和终端配色…

单旋 splay

迎面而来的工业气息…

然而看了题不像裸题,感觉旋转操作十分恶心…这时才发现并没有好好研究过splay.

手玩了大概三十分钟,发现将最大值和最小值旋转至根的操作并不会对splay造成很大的改变,只要分该节点的子树和其它节点两种情况更改其深度.那么我们就可以记录单旋splay中的深度,父亲和儿子信息.在插入时用set找到插入值的前驱和后继,并更新其深度和父亲信息;旋转时区间修改深度,并更新相关父子关系和根节点即可.发现要手写的数据结构只有一个树状数组STL大法好,不过由于操作很多需要分情况讨论还是写了3k.

写完又陆续发现了不少错误,调完大概在这题用了两个半小时了.由于暴力并不好写(暴力都要写splay,差评),所以没对拍就去打后面的暴力去了…

影魔 sf

迎面而来的工业气息 * 2…

匆匆打完了$O(n^3)$暴力,又想了大概二十分钟,有一个大概的思路:定义每个灵魂的贡献为其作为某些区间最大值时,那些区间对答案的贡献.ST预处理后,我们二分出每个灵魂$i$向左以及向右碰到的第一个大于它的位置,假设为$L, R$.考虑灵魂$i$的贡献,发现只有区间$[L, i + 1], [L , i + 2], … , [L, R - 1]$ 以及 $[L + 1, R], [L + 2, R]… , [i - 1, R]$ 会产生$p_2$的贡献,只有$[L, R]$会产生$p_1$的贡献.那么把区间看成二维平面的点,询问相当于查询一个正方形内的点权和,最后加上$[i, i + 1]$这类区间的贡献即可.

所以用两棵树状数组套线段树就可以了?火速打完发现拍上了…试下$n = 200000$果断RE,$n = 100000$果断RE, $n = 50000$果断超时…成功拿到暴力分.

礼物 gift

一开始看题的时候感觉这题暴力分很多…只需要将答案的式子拆一拆,然后记个前缀和,枚举移的位数就可以70了.

发现复杂度的瓶颈在计算$\sum_{i=1}^{n}x_iy_{i+j}$,其中$j$是移的位数,当时第一反应是FFT,想了一会并没有发现要把一个数组反过来做.于是就去看前面的题了…

后记

第一题最后没时间对拍比较虚,但是正确性似乎没有问题.

第二题各种方法都有,于是出现了莫队大佬,可持久化大佬等各路大佬.似乎正确性也没有问题,只是空间上会gg.

第三题就是FFT,为什么没有多想一想呢…

还好T1没挂,200还算好吧…不过200+的大佬好多啊…

Day2

今天试题密码没出错了,但是试题格式使得样例很不好复制(而且样例还很长,差评).

大佬 dalao

一个爆搜加一个简单dp就有40,然后就没什么思路了.

唯一想到的是应该贪心地让不用来增强信心的天数尽量多,这可以用一个简单的递推得到.这之后一个dfs就能方便地得到40分,除此之外就没什么意义了…

队长快跑 captain

计算几何?虽然前天看了但还是有点虚啊…

十分想不通这题竟然有比$O(n^3)$更优的复杂度,只好打个暴力了…

尴尬的是暴力都调了好久,发现判相交写错了,极限在下考前15min过了样例.计算几何还是没学好…

抛硬币 coin

容易发现答案就是$\sum_{i=1}^{a} {a \choose i} \sum_{j=0}^{min(i - 1, b)} {b \choose j}$,然而由于模数不友善,只会杨辉三角拿30.

不过考虑$a = b$的情况,此时是一个公平游戏,获胜方案数为总方案数减去平局方案数的一半.于是答案为

只要算一个组合数就可以了exLucas或者直接质因数分解都可以,50滚粗.

后记

打了三个暴力,不过好像暴力分就算高分了…

第一题竟然是爆搜题,前面的思路没有问题,然而我并没有写什么剪枝=_=.

第二题似乎是很难,而第三题有很多拿到70的(数学没学好).

320踩线?可以写本骗分导论了…

总结

终于进入正题了…

首先还是得打好暴力咯(蒟蒻当然只能打暴力),暴力写好了可以对拍正解,就算正解写挂了也不虚…

然后对于每一道题,就算看起来不好做或者已经能拿到可观的部分分还是要多想一想,比如Day1T3和Day2T1.就算看起来过不了也要进行一定的尝试,尽量优化算法,一些玄学题有可能会估错复杂度.

另外打代码的时候一定要理清思路,如果允许的话可以写完一部分就输出中间结果,这样可以省去很多的调试时间.就算过了看起来很强的样例或是拍上了也要小心,多构造特殊数据,最好进行一次静态查错.

在考场上最重要的还是要有好的心态,当做一次练习就好.

这次考试也发现在各种数学题上比较弱,平时在这方面的练习还要加强.这段时间在代码能力方面有一定提高(刷HNOI的后果),瓶颈往往在于思路上,刷题还要多重视思维.

接下来的话主要可以做一做近几年的NOI, ZJOI,然后可以多做一做计数题之类的数学题,难题和简单点的题都需要重视.

HNOI2017 完结撒花~~