Day -0.5
在机房写模板赛,发现怎么字符串这么差劲,连夜看了KMP,manacher,AC自动机期望不考容斥原理那些.考了绝对不会
然后感觉颓废了半个上午,剩下半个上午在看一些考前n问,有点紧张.
中午和@pap_han,@fantasticjimmy一起吃余割函数.然后坐地铁去CQBZ,和去年一样,CQBZ的厕所高度严格小于 1.2m 上厕所时特别没有安全感.
Day 0
进场了,很紧张,可能是因为我已经高二了,有些心理压力.
- 14:25 发压缩包密码了,密码很搞笑,好像有什么
DEC 31之类的东西. - 14:26 开始看T1,感觉有点困
早知道中午睡午觉了,早知道前一天晚上不干了,感觉这题有点东西啊,怎么合并还要+1的???
P.S. 有人第一次看错题了
-
14:34~14:40 怎么周围人都写完了,哦原来是我看错题了,重新思考发现,考虑最后的答案应该是取到一个 \(a_i\) 的值,如果卡在 \(a_i\) 和 \(a_{i+1}\) 中间可以选择把多的部分给到比它们小的数上可能会产生新的答案.所以我们可以考虑枚举最后的这个数是哪个 \(a_i\) 画出图来发现只需要统计比它小的前缀和,然后要补的部分数值对于每个 \(i\) 一定是单调的,于是我们可以二分,时间复杂度 \(\mathcal{O(n \log n)}\) 应该可以通过.
-
14:40~15:00 我写写写,写完了,嗯,大样例也过了
内心OS:应该没问题吧,由于一直在喝水,所以直接去上了一个WC -
15:10 上完了发现对于T1的 \(m=0\) 有点小问题,简单修改一下
-
15:13~16:00 开始看T2发现这个应该是和 \(n\) 有关的
floyd因为这样才能处理询问,不然就只能是每次询问跑一次dijkstra显然不可接受.考虑怎么才能归到和 \(n\) 有关的复杂度,看样例的时候发现同一条地铁线上的点互相到达的时间为0,这个就可以使用类似于缩点的方法解决,每个线路之间最短的换乘的时间就是对应线路上的站点的最短时间.又注意到每个点最多只被 \(d\) 个线路覆盖所以这样是很优秀的,询问只需要暴力枚举 \(x\) 和 \(y\) 所在的线路,找最短路再加上进入站台的和的最小值即可,总时间复杂度 \(\mathcal{O(qd^2 \log d+md^2+n^3)}\) 多了个 \(\log d\) 是因为我写的是map,一鼓作气写完居然直接过了所有样例,开心了直接去上了个撤硕. -
16:00~17:40 死磕T3发现怎么都不是我可做的题,考虑写暴力,定义一个 \(f_i\) 表示 \((u,i)(u < i)\) 的满足条件的对数,发现其实是倒着一直找就行了,先看那些可以一步到的,这种的一定不是答案,然后看一步到里面的最后两个 \(j\) 和 \(j+1\),向前找离这两个距离 \(\le m\) 分别作为 \(l\) 和 \(r\),这样 \([l,r]\) 内的数到 \(i\) 这个点就只能要么直接去 \(j\) 然后直接去 \(i\) 要么只能去 \(j+1\) 然后直接去 \(i\) 一定是两种,并且这个是一直往前递推的每个 \(j\) 都可以一直这么找直到 \(j\le 1\),又 \(x_i\) 单调上升,于是可以直接二分一下来找,但是这个代码巨tm难写,写了很久给我时间写完了.还不知道对不对,只验证了小样例...
-
17:40~18:20 狂写T4准备直接 \(n\times 2^n\) 枚举再判断联通块是不是 \(\le 2\) 个然后用
倍增LCA计算距离,但是没有时间了,只能先开始检查了.剩余 \(10\min\) 完全写不完. -
18:20~18:30 检查
freopen,long long,以及数组大小去年因为这些在CSP-S挂了 \(60\) 分,在NOIP挂了 \(10\) 分. -
18:30~18:45 签字确认,厚礼蟹对面那哥们怎么做出T3了,WTF
dp套dp没学怎么说,拜拜了, liukelin 小弟👋👋👋
Day 1
不是怎么大样例这么水啊,我不会挂分吧???如果挂了只能🤬🤬🤬然后再🥵🥵🥵了啊啊啊啊啊啊啊啊啊啊!!!!!
然后骨粉,感觉不是很高啊话说洛谷居然评价的是 \(\color{yellow}{黄}\color{green}{绿}\color{purple}{紫}\color{black}{黑}\) 啊有点colorful
最终股份:
\([0,100]+[0,100]+[0,40]+[0,0]=[0,240]\) 感觉多半很低了
然后写了这篇游记