NOIP 2025 游寄

· · 生活·游记

前情提要

还是被 3pts 卡 7√ 了。

这居然是我第一次参加 noip。

Week -2

秋假被吞了。请输入文本。

不过好像能补。

依旧每天高质模拟赛。

Week -1

有人得了疾控啃亚热,导致其与隔壁宿舍所有人要被抽血。

还好隔一个楼层不算隔壁。

Week 0

并不需要早读,真正实现了全停。

Day -6

依旧开晚会,(我所记得的)大致内容如下:

总结:吃饭要用嘴吃,走路要用腿走。

Day -?

刷新了特殊宵夜。

所以某人的星期四什么时候请。

Day -1

中午回的学校,成功赶上大巴。

前往酒店。

到达酒店。飞速上楼。先放包,然后检查红外线,检查双面镜,检查隐秘性,然后装死。何意味。

五点下楼集合去别的地方赤饭。

豪赤。

为什么快吃完了才上米饭。

回酒店。

要进行神人晚自习,结束后还要收电脑收手机。

与亚历山大进行一番激烈的讨论后决定啥都不带下楼假装无电子产品,必要时交出提前准备的模型机。

结果是下楼发现无人值班,于是抓住 timing 上楼筹集。

豪抽。

过了一会快到该收手机的点了,为了安全起见还是下楼观察情形。

然后发现了一些危险实体。进行了一些巴巴博弈之后通过后门逃离。

于是就顺便吃了点宵夜。

豪赤。

回到酒店。似乎没多久就睡了。

Day 0

被酒店的电话与手机的闹钟一起叫醒。

收拾东西后下楼赤早餐。

豪赤。但是疑似碳水摄入偏多。

上车去考场。

进行了一个影的合。才发现 jf 去了好多。

终于进入考场。周围全是自己人何意味。

神秘键盘无法按动 ctrl 和 space。

开考发神秘密码。暗示了是一场 dream。

先进行题目一个全部的看,好像都不太可做的样子。

看 T1,题意很简洁,看着是个贪心或者 dp 之类。贪心好像有点搞头,但无法证明。想了若干分钟未果,遂想暴力。首先能确定的是,选的方案是分为两部分的。第一部分选的东西都是偶数个,相当于代价为 a_i+b_i,再用剩下的钱去选单独的,相当于代价为 a_i。于是可以分为两部分分别做背包。但是我居然花了 0.5h 打了一个我自己都不知道写了个啥的 01 和多重背包。

转向 T2。成功读错题被样例硬控 5mins,然后发现不可做,终重看 T1。

越来越发现不对劲,背包复杂度再怎么优化都不可能与 m 无关。于是再次考虑贪心正确性。发现第一部分相当于做价值确定相同的多重背包,那么选了贵的显然不如选便宜的。第二部分相当于做价值确定相同的 01 背包,贪心地考虑那也是价格从便宜到贵去选即可。好的似乎是正确的,那我岂不是对这个糖题犯了这么久的糖吗。

写写写,然后发现第一部分可以不用全部选完,可以留一点钱给第二部分。所以打了个前缀和,过掉所有大样例。这个时候已经过去了 2h。

上厕所清空思路。

由于 T2 完全不知道是个什么状物,所以直接看 T3。子树 \rm mex 是什么东西,好的同样不可做。既然是集合,那直接想一下状压。然后不知道犯了什么糖算出来复杂度 \mathcal O(n2^{n^2}) 以为不可做,所以没细想,等着回来打暴力。

上厕所。外面真冷。

然后看 T4。这不就是区间赋值版的超级钢琴吗??如果直接用超级钢琴的结论,每次的操作就要区间取一个当前答案的 \max,用己巳己可以处理。但是复杂度似乎不太正确,而且极其难写。等等,每次区间更新是一个定长,而且更新的东西好像有单调性,能不能用单调队列?不对,每个数入队不止一次,复杂度还是假的。

行,那直接处理 st 表然后每次询问每个数再暴力 O(n) 更新区间内的答案就行。过了比较小的样例,似乎能拿一个比较可观的分数。这个时候还剩大概 1h。

豪德,先把 T3 的 O(n^{n+1}) 弄了,然后 T2 的暴力也打掉。从难度梯度来看,T2 是目前最可做的。遂想,而无思路,蒜鸟蒜鸟。

最后把代码上虚拟机跑了一下,能编译,豪。那就等着吧。

预期得分:100+20+8+12=140pts

结束了。出考场就听到一堆巨犇讨论 T2 做法。

但好像分数都不太高?除了 sst。

后记

黄紫黑黑果然是 noi plus。

出分了,实际得分:95+20+8+35=158pts

T1 没判答案为 0 挂分。T4 能拿这么多分??

吃上星期四了。豪赤。

GD 1= 线 144pts。算是对没拿到 7√ 的一点补偿。

但是今年 1= 也太水了。