NOIp 2019

用 3 个小时获得 10 分

Posted by Ghastlcon on November 17, 2019
CC 采用 $\text{CC BY-NC-SA 4.0}$ 许可,转载请注明:“转自 NOIp 2019

$\text{NOIp }2019$

你以为这是 $\text{CSP-S}$?这是 $\text{Counter Strike Polynomial}$!

你觉得有 $\text{NOIp 2019}$ 那就有了(

还是那样,想看 $\text{Solution}$ 的直接翻 $\text{Catalog}$ 。

$\text{Day }[-??,\, 0)$

照旧了,没啥可以描述的了。

总是莫名其妙 $\text{FST}$ 。

所谓打球

$\text{Day }0$

睡醒之后坐车,极度难受,感觉看不见了听不见了不知道自己在哪。

这住的地方真的神奇,真就就城中村啊。附近有个便利店可能还行。

便民巴士

出去瞎转了几圈居然转到了 $2015$ 普及时住的地方的路口,哭了。

真城中村

晚上瞎逼玩游戏,还是菜。

考前有好多人给我加油啊,好幸福啊,哭了。

麦老大为啥在奇怪的地方啊,这都十点半了我咋过去啊,算了明天再找他。

薯片真好吃(

$\text{Day }1$

睡醒之后头还是很晕,不太对。

早餐在某个神奇面包店解决,包里面全是奶油,想吐。

奇怪的海报

墙上为啥还贴着 $\text{dwjshift}$ 的走向巅峰啊,这是多久没换了。

走向巅峰

考场外面看到了 $\text{hz}$,正常吹了会水。为啥他会以为我是高一的啊。

广附的教练为啥会认识我,我记得我当时没给广附发邮件啊。

走了

密码是 $\texttt{Ren2Zhen0Si1Kao9?}$,把那个 $\texttt 0$ 看成了 $\texttt O$ 然后死活没法解压……试了几次之后还是不对,把解压出来的垃圾删掉的时候手滑把包给删了(

直接懵逼,找监考员重发了包(

点开注意事项发现没什么变动,不管。

看题,第 $k$ 个 $\text{Gray}$ 码是什么鬼啊,我记得结论是 $k\operatorname{xor}(k\operatorname{rsh}1)$ 来着。

树上括号序列是什么鬼啊,这不是直接维护后缀,然后拿个线段树走走就搞完了?线段树 $5\cdot 10^5$ 没问题吧?

给这个不同的子串的定义差评,还以为是本质不同的子串。

只用半小时就写完了。

这个字典序有点神奇啊,优先移动?但是有可能移回来啊?

哦那应该是边之间删除顺序的关系,这样子的话夹在 $a,\,b$ 间的边 $c$ 就要么在 $a$ 前要么在 $b$ 后,怎么感觉是个 $\text{2-SAT}$ ……

那我直接建出 $n^2$ 个点,每次暴力判断就是 $\mathrm O(n^3)$ 的?感觉还行啊?


十点了,草这玩意咋这么难写啊。

回去把前两题拍会吧。只用了 $15$ 分钟就拍上了,感觉还行。

再写会吧。边写边想。


草这怎么就十一点了,要不去写个链?

按照顺序排排,然后左右都讨论,可能还行?


草为啥写不出来啊,回去老实调 $\text{2-SAT}$ 吧。

等等怎么只剩 $10$ 分钟了,感觉要出事。

赶紧把 $\text{2-SAT}$ 全都删了,瞎逼搞了个 $\texttt{random\_shuffle}$ 贪心就跑了。


怎么全世界都 $210$ 啊,这个区分度也太良好了吧。

成功区分出了 $\text{myh}$ 和其他选手?

咋有人说直接贪心,然后这个非偏序关系能转化为某条边要紧接着某条边之后选,做完了?

中午跟着 $\text{aspe}$ 去了某家人满为患的 $\text K$,莫名其妙等了半天吃了个中药味的汉堡。

忽然发现我好像把外套放在考场了,感到不适。

回去的时候看到 $6174$ 在大堂带着女装,进房之后本来想给我穿的(

这么多人我为啥要搞这东西啊,把这东西甩给了 $\text{Monad}$(

为啥没带假发啊,差评如潮。

$\text{Ressed}$ 又不和我则啊,无聊到玩 $\texttt{generals.io}$ 了。


自然而然的晚上就跑去找麦老大啦。

跑出来之后在六中门口就找到了,瞎逼描述了下今天的题目就跑地铁了。

我寻思这有点远啊,是不是要半个小时啊。

站内遇到 $\text{zls}$,好像写了个并查集,果然是牛逼人。

草为啥我省选睡到 $37$ 这么众人皆知啊,麦老大直接说了睡过头 $\text{zls}$ 就知道是我(

地铁出来之后迎面就是个在大放电音的火锅店,给 $\text{xgc}$ 描述位置的时候直接用了“电音火锅”这个词……

然后就几个人走着走着碰到由胡爷爷带领的金中大队,感觉都不太认识……

问了一下胡爷爷写的咋样,咋又是 $210$ 啊。

广东真就只有队长把这破题写出来了啊。

然后 $20$ 来人到处闲逛都没找到能坐下的店面,最后瞎逼找了个类似大排档的地方就坐下了(

果然麦老大在的话气氛都比本校自己玩都嗨,真是神奇。

$\text M$:你这头像,你也看 $\text{JOJO}$?
$\text X$:是啊
$\text M$:太好了我不看,你一边去

麦老头你大呢?

$\text{xgc}$ 去雅礼的时候我不在,我去的时候他不在,感觉又不太行。

$\text M$:(对我)你会回去的路吧
$\text L$:显然会吧
$\text M$:那我知道你不会了
$\text L$:你咋又什么都知道了?你是不是还知道更多
$\text M$:那当然了
$\text M$:$\text{NOI}$ 你考完我就知道你多少分了

草为啥要描述我在学校干的破事啊,真不太行。

感觉没吃饱,然而就这样跑路了,回去再说吧。麦老大要去看电影,过了这次 $\text{NOIp}$ 下次再见真的不知道是啥时候了。


回来之后也没啥干的啊,围观狼人杀,又顺便打了会则。

你看这是不是有来有回

没活干的时候甚至点开了 $\text{Baba is you}$,然而还是根本不会。

薯片真好吃(

$\text{Day }2$

咋头还是很晕啊,感觉真的要完。

今天并没有跟着走,因此去了个神奇肠粉店,但好像没做熟……

考场开得比较早,因此并没有说太多话。

进去之后发现外套还完好放在原来的位置,好评如潮(

密码是 $\texttt{@zhuajin1SHIJIAN7}$,好像密码已经几年都不是随机串了。

怎么又是树啊,$\text{CCF}$ 这么喜欢树的吗?

那这个数数题显然直接考虑不合法的,点中出现过半的,然后暴力?超过半数有啥性质来着?

先写了个 $\mathrm O(n^3)$,想了会感觉直接改成 $\mathrm{+1}/\mathrm{-1}$ 就行了。改完之后很容易就拍上了。

数数题就是好数据全随机都不怕(


咋又是平方啊,又来斜率优化?我这是不是在打 $\text{NOI}$ 。

画了会发现不是很能搞,小于等于不知道咋限制,那就先搞个 $\mathrm O(n^2)$ 暴力记下上次决策吧。

就几行的事情很快搞完了,然后还是不会。我给你打个表?

草这个破东西为啥真的是单调的,单调下降然后在某个点处变成无解。那我只要找出从后往前首个有解的位置就行了?咋判断啊,我为啥只会 $\mathrm O(n)$ 。

能从前个位置推过来吗?不太行啊,块发生变动的复杂度没保证啊。

换题。


随便画了画感觉不太能做,现在写换根应该挺送命的,我觉得写不出来。

我居然会做链,太感动了,感谢良心出题人(

满二叉树咋搞啊,似乎只有删掉叶子才会引起双重心的情况?

瞎逼搞了个暴力又搞了上面几个情况,好像就 $75\%$ 了?

走了走了。


等等因为有解的位置下,把最后的块删掉并不影响前面的有解,那么首个有解的位置是不是判前面的块是否不大于自己就行了啊。那我可以先暴力枚举啊。

这个东西似乎并不单调,但是查询是单调的,那搞个单调队列就做完了?

高精度咋写啊,暴力搞个 $\texttt{vector}$?这能不能跑过啊。

瞎随了几组感觉跑得还挺快的,那就这样不管了。

考试结束前监考员强调把自己的随身物品带走,还特意说了“昨天有某位同学把外套留在这里了”(


感觉这个分数还不错?希望别 $\text{FST}$ 了就成。

咋 $\text{zjt}$ 说集训队群里没人 $\text{AK}$ 啊,这咋回事啊。

惨啊。

$\text{Memory}$

那既然都高二了,我也没有什么可以说的了。

这破题真太难了,也没指望能超越去年的分数。

想我去年这个时候认为未来充满希望,结果这年下来教育部搞了什么幺蛾子大家都知道了。

从 $\text{PKUWC}$ 空手而归开始,感觉事情就不太对了,虽然自己也没搞多好。

去年写了“大概是时代变了吧”,今年真的要肯定地说出时代变了。竞赛规模虽在缩水,但是不知为何涌入的人不减反增,也是很神奇。

不知道接下来这年里,教育部又会搞出什么呢。不知道等我明年退役后再回来看这篇东西,又是啥感受呢。

$\text{OI}$ 生涯,真的要结束了……

$\text{New Hope}$

$\text{Solution}$

$\text{P1}$

答案即为 $k\operatorname{xor}(k\operatorname{rsh}1)$ 。

也可以分位考虑。如果 $k$ 最高位是 $1$,那么必定是被反转过的。将这个 $1$ 去掉然后反转回来即可。可以递归实现,也可考虑反转映射的过程即为按位翻转,可直接取反。

因为无论如何都要输出,因此复杂度为 $\mathrm O(n)$ 。

$\text{P2}$

结点 $x$ 的答案可以从父亲处继承而来,因此我们只需要考虑以 $x$ 结尾的括号串有多少个是合法的。

将左括号标成 $1$,右括号标成 $-1$,计算前缀和 $s_i$,实际上想要知道有多少个 $s_j=s_i$ 且 $\min_{k=j}^{i\uparrow}s_k\geq s_i$ 。

线段树维护首个 $<s_i$ 的位置,然后求区间内有多少个 $s_i$ 直接二分查找即可。复杂度 $\mathrm O(n\log n)$ 。

$\text{P3}$

$\text{P4}$

因为出现过半的元素最多只有 $1$ 个,所以直接枚举出现次数过半的元素 $x$,然后令 $f(i,\,j,\,k)$ 为前 $i$ 行,选中了 $j$ 行,共选了 $k$ 个 $x$ 的贡献,直接转移即可 $\mathrm O(n^3m)$ 。

然后注意到出现次数过半是个挺好的性质,我们可以把 $j$ 和 $k$ 压起来,即记录变量 $t$,每选 $1$ 个 $x$ 令 $t$ 加 $1$,每选 $1$ 个除了 $x$ 以外的元素令 $t$ 减 $1$,最后 $t$ 为正数的时候即为出现次数过半。

复杂度 $\mathrm O(n^2m)$ 。

$\text{P5}$

首先有个显然的 $\mathrm O(n^2)$ 动态规划,$f(i,\,j)$ 表示考虑前 $i$ 个数,最后的决策点为 $j$ 时的最优解。

令 $s_i$ 为前缀和,即 $s_i=\sum_{j=1}^ia_j$,则

然后给 $f$ 打个表,会发现在 $f(i,\,j)$ 不为无解的情况下有 $f(i,\,j-1)\geq f(i,\,j)$ 。

因此我们实际上对于 $i$,想要找到最大的 $j$ 满足将 $(j,\,i]$ 分作一段的时候有解。

令 $g(i)$ 为上面描述的“最大的 $j$”,则

即 $2s_j-s_{g(j)}\leq s_i$ 。显然 $s_i$ 是单调上升的,因此单调队列优化即可。

对于最后 $3$ 个测试点,答案可能超出 $\texttt{long long}$ 的表示范围,需要用两个 $\texttt{long long}$ 储存最后的答案或者实现优秀的高精度。

$\text{P6}$