记失而复得的 CSP-S 2022

· · 个人记录

26号晚上被通知江苏取消CSP，担心一晚上。27号中午又被通知恢复了？感觉特派员多少沾点。不过结果是好的。

学校放月假，就在放学之后去老地方开了几把。运气究极差，就当是给CSP攒rp了！

回家之后又看了看去年NOIP的题，仔细想想光是暴搜级暴力打满就有144了。不过国一线貌似150。然而我除了暴搜什么都不会！看看今天能不能发挥神勇点了。

在太阳底下排队排了二十分钟，旁边的老师美名其曰给我们这些每天窝在电脑前的孩子补补钙。

进考场后试机，花15min敲了个线段树板子，一遍写对，是个好兆头！

然后下发题面。

T1转化后题意为，在图上找一个经过起点的权值最大的五元环。

开题后以为一眼秒了，拆成两半分别找就是 O(n^2) 了。然后写着写着发现不对劲。找到距离二的之后需要判前驱是不是重合，遂开堆维护，算了算空间有点危险。一看比赛时间过去1/4，还一分没得，就写了个四次方的暴力混个40pts润去开T2了。 期望得分40pts。

T2题意为：给两个序列，每次询问对两个序列分别给出一个区间，两人先后从各自区间中各选取一个数。先手的目标是使两数乘积尽可能大，后手的目标是是两数乘积尽可能小，若两人都做出最优决策，求两数乘积。

大概是这场的签到题吧。分先后手序列中有无正负分四类讨论，开六棵线段树维护。欸嘿，这里伏笔就来了，试机的时候打的线段树板子就用上了。大概写了半小时，一跑发现第二个样例寄了，然后对着调发现少讨论一种，改了之后还是寄。又是调调调发现又少讨论一种。改完之后大样例过了。期望得分100pts。

T3不知道是什么神仙题，题面好几百字，直接skip了。

T4，怎么又是树问题？？？一棵树一首诗一段情，再多的抱零也荒芜不了一整个OI。仔细端详一下发现部分分很多。k=1的情况就是求路径上权值和。树上差分解决。然后发现LCA不太会写，乐了。不过最后还是写出来了。k=2可以 O(n) 把链抽出来然后dp。k=3好像会有从链上拐出去的情况，有点想不动了，先吃一块巧克力。还是想不动，再吃一块，然后巧克力没了。还是没想出来。期望得分32pts。

离比赛结束还有半小时，回去写了发T2的暴力，一发拍上，感觉良好。

还有10min的时候，端详了一下T3，没看懂题面。然后就结束了。

期望得分：40+100+0+32=172

回来车上，发现tle把T1T2都切了，tql。听他说了T1做法之后茅塞顿开，前驱重复问题只要再维护一个次大值就能解决。我哭死。

回来之后在几个平台都测了一下：

洛谷自测：5+100+0+32=137

infOJ自测：40+100+0+24=164

计蒜客自测：35+100+0+？=？

总之是T1未知原因挂了，infOJ机子慢了点没跑过T4的2e5部分。现在寄希望于ccf数据造得弱点。也许能混个国一/蓝钩？能的话我在群里的id可以改了！不行的话还有NOIP。

算法水平没什么提高，不过码力应该比去年上升了些。去年这个时候我还干出了在czm杯冲2h线段树和暴力同分的壮举。

同学这边：

tle：100+90+0+0=190 蓝钩稳了，膜膜膜。

thh：0+60+0+16=76 打的不伦不类属于是。

lsx：50+40+0+0=90 有点强，T1单方面薄纱我了。

zzx：不是很清楚。

不过大概都能进NOIP，这是好事。NOIP加油捏！