希望别挂分。
Day -2 ~ Day -1
睡得不怎么好,背部总是发热,像火烤一样。
Day 1
14:30 ~ 18:30
开场先把四道题都看了一遍,T1 简单题,T2 只会 50,看上去好难,T3
大模拟, T4 不知道是啥,先二分答案。没有一道 !吐了。看完题时 14:40。
然后花 分钟写了个 fread
快读,接下来 分钟写完
T1。一开始以为 T1 能操作很多次,发现无论输入如何答案都是 。改完就过样例了。
此时我发现 T1
只有两个样例!查看剩下题目的样例,发现没有一个题目的样例是给全了的。看来这场暗藏杀机。有模拟赛那味了。
还有十分钟到 ,见缝插针地想了 分钟 T4,发现菊花的部分只要求出 表示一个点最晚要在 时刻到达,然后把 从小到大排序即可完成二分答案的 Check
部分。想到这点后意识到 T4 是个贪心题,且有点像 exchange argument
的变种。此时已经 ,开始写
T2。
开始写 T2。先用 分钟写了
分暴力。然后对着暴力观察,容易发现只需对每个 求出 表示最大的 满足 可以消掉,就很容易求出以 结尾的合法串数 ( )。关键在于 怎么求。容易发现 ,且 与 之间的字符肯定能被划分成若干个
形成的区间。于是有朴素做法是先设 ,如果此时 就令 ,直到 。这就是一个向前跳跃的过程。所以可以开个数组 记录从 开始跳,跳到的最近的字符 在那个位置,然后直接令 。 怎么求 ? 可以由 拷贝过来,然后让 即可。
太难了啊这个 T2。当时想了 个求
的做法都假了,当时已经过了
分钟,额头已经微微出汗,大脑开始红温,去上了个厕所,意外发现厕所里窗边的凉风吹得非常舒服,状态很快就恢复正常了。
写完 T2 之后 。
测完样例,喝了瓶牛奶,大致规划了一下 T3
的思路,发现如何求地址已经被写在题面里了,这大概是出题人唯一良心的地方。 中开始码码码,到了 才码完。 调过了所有样例。 写了 行和不计其数的 string 和 map。STL
真是好用啊!
现在还有 个小时,我在写 T4
暴力和冲正解的选择中徘徊了一会儿,然后决定直接冲。发现我只需找到 的一个排列,使得
最大化,同时还要让这个排列满足树的限制,即父亲的出现位置必须在儿子前面。最后判这个最大化的
是否
即可。菊花的邻项交换正确性不难证明,把问题搬到树上,应该只需套用树上
exchange argument 的做法即可。观察全局 最小的那个点 。如果某个时刻 被选,下一步一定是先走到 。这是由邻项交换的正确性保证的。于是我们可以将
和
合并,表示它们一定是紧挨着的。合并出来的新点的 就是 。重复这样的合并过程,对于每个点,我们只需记录其大小和其对应的
,将其放到优先队列中去即可。合并过程可使用并查集维护。于是一次
Check 的复杂度就是 。其中的 是计算
的复杂度,因为我使用的是另一个二分来计算 。总时间复杂度就是双 。
写完,发现 T4 大样例要跑
,开始卡常。尝试很多种方法后,发现只有快读的优化最为显著,其次就是算分段函数的时候有一个小数除法可以提到外面去,加了这两个优化之后跑了约
,然后看到本地机子是 i3 8
代,想着评测机应该比这快,就没管它了。卡常的间隙还写了个 T2 的拍。
最后半个小时,我发现虽然我会
题的正解,但我只会
题的暴力。怀着这种心态,我到最后都没有想起来 T4 其实是可以对拍的。
下考之后发现这场确实出得比去年简单很多,题目质量也更加不好评价。后来听说
T4
的大样例不读入树的形态就能过,当时感觉有点悬,现在也看淡了,这种比赛挂
分也没啥。
当天晚上,很多自测网站其实已经开始营业,但我也没去关注,只看了小图灵发现
T1 和 T2 过了,就去睡觉了。晚上又没睡好。
我觉得这次发挥最主要的下饭之处就在于 T4
没有对拍,其他的都还好,前三个小时头脑也比较清醒,希望 NOIP
时也能保持清醒与理智。