NOIP2024 游记
第三次参加 NOIP 了,但是是第一次正式参加。
Day 0
考前一天我们三点半就放学了,然后打了两个小时排球,回去很累了,摆了一晚上。然后快要睡觉了,我又突然想起来打了个网络流的板子。最后差不多在 22:40 睡觉了,睡眠质量还不错。
Day 1
早上 6:30 就醒了,但是由于比较紧张,后面就没有睡着了,但是还是眯了一会儿。吃完早饭马上赶往考点,考点在七高,仍然是主场作战。在这里遇到了其他同学,我好像是最后一个到的?
现在大概是 8:10,我打开虚拟机,把板子敲上,然后就开始趴着睡觉,快到考试的时候,旁边的 @11111118m 问我怎么写重载运算符
,我小声告诉了,然后紧接着是 @X2H_tato 问我虚拟机在哪里
,然后他不是很听得清我说的话,于是就找了监考老师。
8:30,开题,我先通读了一下 T1,然后迅速花了 5min 思考了一下,没有什么头绪,于是就通读了一下四道题。T2 不知道是个啥,但是应该不会太难,T3 的题面太长了,懒得看,T4 是一道 DS,我觉得我有希望能做出来。
然后我就开始看 T1 了。想了一会儿就有个贪心做法,就是在前面能匹配就尽量多匹配,直觉上这一定是最优的,然后再分这一位 \(t1_i,t2_i\) 是什么值分类讨论。写了 20min 就写完了,一测大样例,发现挂了两个点。我又看了下代码,没找到啥错误,我就开始有一点慌,不会 T1 就做法假了吧。我又对着我的代码瞪了 10min,突然想到我两个需要分类的地方为了简便直接合在一起写了,但是写错了。于是我老老实实把所有要分类的情况都写完,没有图简便。并通过了大样例,我松了口气,此时是 9:20。
然后开始想 T2,仔细读完题我就发现这是个唐题,这不是直接 \(f_i=f_{i-1}\times (v^{2(a_i-a_{i-1})}-v^{a_i-a_{i-1}-1}(v-1))\) 就结束了吗,15min 写完代码,结果有个小细节没注意到,小调了一下。最终在 9:40 通过了大样例,剩余的时间还比较充裕,
接着,我花了点时间弄懂了 T3 的题意,看懂了样例,又用了点时间想了想,发现没有任何思路,甚至连 \(k=1\) 都不太会。于是我就果断地去思考 T4(还有个原因就是最近有好几次考试 T4 都比 T3 简单,所以我就潜意识的认为 NOIP 也会是如此)。
T4 是一个区间子区间求 \(\max\) 的问题,我首先想到了一个子集的 lca 等于 dfn 最小和最大的 lca,然后在这个出发点上面想了二三十分钟,却始终没找到突破口。于是我又换了个思路,我联想到了暑假时 lxl 给我们考试的一道题。大概思路就是处理出有哪些区间的 lca 是某个点 \(u\),所有的区间可以构成 \(\mathcal{O}(n\log n)\) 个矩形,可以用启发式合并来求解。询问的话根据错解不优发现只需要求满足 \(l'\le r,r'\ge l,r'-l'+1\ge k\) 的区间 \([l',r']\) 即可。那么一个矩形只有左上角的点有用,于是决策点就只有 \(\mathcal{O}(n\log n)\) 个了,为了卡常还可以去掉有偏序关系的区间。
现在的问题是对一个询问 \(l,r,k\) 求出 \(\max\limits_{l'\le r,r'\ge l,r'-l'+1\ge k}d_u\),这个就是个三维偏序问题,直接用 cdq 分治求解即可。但是,我考场上没有反应过来!我以为这是个单点修改,矩形求 \(\max\) 的问题,认为要写个树套树,并以为时间复杂度是 \(\mathcal{O}(nlog^3 n)\)。在大概 11:00 时想到了全部的思路,我开始有点激动,觉得自己做出了 T4 很厉害,但是想起了霉好的回忆,于是我就去上了个厕所冷静一下(其实在思考的时候我还上了好几个厕所)。然后我觉得很有希望能写出来,虽然不知道能过多少分。
然后我就一直写,写到了大概 11:40 左右过了小样例,但是大样例一直输出比答案要大。我就开始有点慌了,但是很快就冷静了下来,我发现我求矩形 \(\max\) 写的是 \([1,r],[l,n]\),会把一些不应该计入答案的算进去,实际上应该是 \([1,r-k+1],[l+k-1,n]\),这样子就过了。原本我都不打算通过最大的样例的,但是我一测发现只有 2.2s,于是就开始疯狂卡常。我甚至把 fwrite 也给加上了,最后再测,1.6s,非常好啊。这个时候已经是 12:30 了。
最后半小时开始冲 T3 暴力,写了15min 之后发现暴力非常难写,直接开始摆烂。然后看到了链,直接输出 \(1\)。菊花图,推了下式子就是 \((\frac{k*(k-1)} 2-k(n-1-k))(n-3)!\),可以获得 16 分(但是因为时间不多,我连 \(k=1\) 都没有细想了)。最后只剩 5min 了,我就检查了下代码,离开考场。
估分:100+100+16+(100-\(\epsilon\))=?,最好肯定是 316,最坏应该不会低于 300。
然后跟同学讨论,发现大家都考得不理想,高一的都只有少数的上了 200,因为被 T1 浪费了大量时间,导致 T2 都没有细想。高二的大众分在 270,我似乎算考的比较好的了,当然还是有考的比我好的大佬(@H_W_Y,@Union_of_Britain)。
然后下午和晚上都在摆烂。
Day 1.5
我从考完到当天睡觉前一直对外声称我的做法是 \(\mathcal{O}(n\log^3n)\) 的,直到晚上我才突然反应过来,决策点去掉无用的之后只有 \(\mathcal{O}(n)\) 个,并且矩形求 \(\max\) 的左端点一定是 \(1\),于是整个的复杂度就变成了 \(\mathcal{O}(n\log^2n)\) 了。
Day 2
洛谷有数据了,把 T1T2T4 代码都默写出来了,T1T2 通过了(吓我一跳,我听好多人说贪心是假的,以为 T1 就要挂分了)。T4 先写了个 cdq 分治的做法,直接无压力通过。然后又写了考场上树套树的做法,并怀着激动的心情测了一发,92 分((
T1 评测记录,T2 评测记录,T3 暴力懒得写了,T4 cdq 做法,T4 考场树套树做法。现在我只能祈祷 CCF 数据水点、机子快点了。
总结
这次考试的总体发挥还不错,T4 能实现出来已经很好了。但是仍有一些遗憾,比如 T4 没反应过来可以 cdq 分治,T3 \(k=1\) 的部分分都没有打之类的。可以看出我还是比较擅长偏 DS 的东西,但是 math 仍有一些不足,后面应该着重整一下数学方面的内容。
标签:max,T4,T3,然后,T1,mathcal,游记,NOIP2024 From: https://www.cnblogs.com/max0810/p/18579598