专栏文章
NOIP 游记 & 考前回忆录
个人记录参与者 2已保存评论 1
文章操作
快速查看文章及其快照的属性,并进行相关操作。
- 当前评论
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @min8ybsm
- 此快照首次捕获于
- 2025/12/01 22:30 3 个月前
- 此快照最后确认于
- 2025/12/01 22:30 3 个月前
NOIP 考前回忆录
注:高二老 OIer AFO 前的追忆。
可能也和同机房大佬们的复健笔记差不多吧。但是既然我一直都在“健”,也就无所谓 “ 复健 ” 了。
Day -15 11.13
听说其他学校的优秀战绩和往届的优秀战绩,看本届 OI 伙伴一轮一轮被刷下,感觉自己也希望渺茫,不禁悲从中来,不可断绝。突然有点伤感自己为什么不早点学 OI,感叹自己学 OI 那难以言说的意义。
训练计划:练习题库 “ 动态规划 DP ” 中第一页所有 的题目。目前进度大概 。
同机房大佬让我去分享导弹拦截的一种做法。不知道题解能不能过。
Day -14 11.14
给自己的目标是 NOIP 250+,但是发讨论区别人也说不可能。其实我也觉得希望渺茫。但谁知道呢。CSP前的集训让我从做不出几道蓝题到拥有切小部分蓝题的实力,说不定 NOIP 前的集训我也能再次进阶呢?
我,能够实现 的进阶吗?
这真是一次渡劫。
今天没写 DP,看了 NOI2025 冬令营讲的贪心专题(然而讲的题难度大都不超过 ,对我还算比较友好)
练了一天的 贪心+数学,由于不想让别人说我写水题写太多(虽然我的能力只允许我能做出贪心和数学的水题)我没写自己号上,第一轮遗憾退役的巨佬 HAPPINESS23333 把他的号传给了我,我在他的号上写了 道题。
Day -13 11.15
【LGR-250】洛谷 NOIP 模拟赛赛时记录
| 时间线 | 赛时安排 |
|---|---|
| 看完四题,又看了签到题半个小时,发现做不出来 | |
| 放弃签到题,开始想 T2 | |
| 发现 T2 DP 的状态转移貌似没有什么有序性,并且可能存在两类状态对应两类状态转移方程,状态也很难分出是哪类,难以DP |
爆 祭。 /kl
【LGR-250】洛谷 NOIP 模拟赛赛后总结
不错。很棒。四道思维题我一点也不会。题解也看不懂。
今天由于比赛情况不佳,全天都没有心情练题。好不容易补出题,已经是第二天了。明天要逼自己多写题了。
Day -12 11.16
今天是我的生日!
早上 打了梦熊的 NOIP 模拟赛。不错, pts 拿下 #rk 。
| 时间线 | 赛时安排 |
|---|---|
| 想、写 T1 | |
| 想 T2 | |
| 写 T2 | |
| 测样例 + 调试 | |
| 写剩下几题暴力 |
下午 继续打洛谷月赛【BYOI Round 1】。
| 时间线 | 赛时安排 |
|---|---|
| 写 T1 | |
| T1 莫名被卡 | |
| 写了一下 T2 暴力 | |
| 看了一下剩余的题目,感觉都不会做。于是出去过生日了(回来又写了 T5 然而写假了) |
月赛再次被打爆了。为什么 比赛一般发挥得不错, 比赛一下就被打爆。
本来很想写几道 DP 奖励一下自己过生日。但突然发现今天做了两道难度标签“暂无评定”的题目。由于好奇明天的做题热度图会显示什么,于是还是看看题,不提交好了。
Day -12 11.17
题目评了蓝。没看到所谓“暂无评定”的热度图qwq。
写了几篇题解,6道 DP。不知道为什么全天集训但是做不动题了。
机房开始流行“OI 教练模拟器”。我总是觉得我培养学生的时候,他们干啥总是压力很大。看来到我自己身上我也想摸鱼啊
Day -11 11.18
CSP-S2 可以下载证书了,2=。
今天还是做不动题,上午在期中考试。
Day -10 11.19
好了,现在终于是吃透多重背包了。
还是只写了两题。花太多时间写题解了。发誓备考前不再写题解了。
某道P1622 释放囚犯的 DP 题,虽然决策分阶段性,但阶段无顺序性,贡献计算不相互独立,感觉根本无法 DP。怎么绿题都不会做。
Day -9 11.20
差 题完成目标 qwq。主要时间都在考期中考,只写了四道题。
一年以后终于通过P1005 [NOIP 2007 提高组] 矩阵取数游戏,恭喜 @高精度 超越 @动态规划DP 成为本题最难的知识点。建议升黑或者把高精度放到 STL 里面。124行太难调了。
Day -8 11.21
上午
再次和高精度 DP 厮杀,写题五分钟,调题两小时。
做了同学推荐的思维题。怎么一到思维题,大家都变成了高斯、伽罗瓦。
完成了练习题库 “ 动态规划 DP ” 中第一页所有 的题目。
期中考试总结
| 科目 | 考前复习安排 | 得分 |
|---|---|---|
| 语文 | 写题解 | |
| 数学 | 学习多重背包 | |
| 化学 | 调多重背包 | |
| 物理 | 写 DP | |
| 英语、技术 | 写高精度 | 、 |
Day -7 11.22
上午【MX-S12】
下午
图论。发现自己忘了怎么写 spfa。
Day -6 11.23
接下来一周训练安排:
- 至少一天的沉浸式 DS、图论练习
- 写往年真题
上午
补一下比赛赛题。
下午
图论练习。
Day -5 11.24
上午
图论练习。
【FCC JZOI 2025 NOIP 模拟赛 1】
| 时间安排 | 赛时安排 |
|---|---|
| 阅读四道题 | |
| T1 思路(部分分) | |
| 写 T1 | |
| T2 题意转化不出来,决定跳题 | |
| 想 T3 部分分 | |
| 写 T3 部分分 |
得分
| 题目编号 | 得分 |
|---|---|
| A | |
| B | |
| C | |
| D |
115 pts,但是校测 rk1。
下午
补题补了一下午看不懂题解补红温了,去写图论。良心过不去又回来补题,好在最后看懂了题解。
Day -4
上午
图论专项训练。
【FCC JZOI 2025 NOIP 模拟赛 2】
| 时间安排 | 赛时安排 |
|---|---|
| 阅读四道题 | |
| 想 T1 | |
| 打 T1 部分分 | |
| 打剩余题目暴力 |
得分
| 题目编号 | 得分 |
|---|---|
| A | |
| B | |
| C | 出题人不予提交 |
| D |
55pts #rk3.
下午
图论专项训练
Day -3 11.25
图论专项训练。
Day -2 11.26
上午
【NOIP 2023】
| 时间安排 | 赛时安排 |
|---|---|
| 想 T1 | |
| 写 T1 | |
| 测 T1 数据,调 T1 | |
| 想 T2 | |
| 写 T2 | |
| 写 T3 部分分 | |
| 写 T4 部分分 |
得分
| 题目编号 | 得分 |
|---|---|
| A | |
| B | |
| C | |
| D |
289pts,发挥得最好的一次,时间安排也是最合理的。
下午
图论专项训练。
Day -1 11.27
上午
调图论题没调出来。
【NOIP 2022】
| 时间安排 | 赛时安排 |
|---|---|
| 写 T1 | |
| 想四道题目做法,并决定写 T4 | |
| 写 T4 部分分 | |
| 不打了 |
得分
| 题目编号 | 得分 |
|---|---|
| A | |
| B | |
| C | |
| D |
136pts,200都没到qwq。
下午
字符串专项训练。
Day 0 11.28
上午
字符串专项训练。
【NOIP 2023】
| 时间安排 | 赛时安排 |
|---|---|
| 想到 T1 80pts 部分分 | |
| 想到 T1 正解 | |
| 写 T1 | |
| T2 想不出 | |
| 想到 T3 正解 | |
| T3 写完了但是发现有环做法假了。。。 | |
| 发现 T4 只会写暴力。但是写了也没几分,就算了 |
得分
| 题目编号 | 得分 |
|---|---|
| A | |
| B | |
| C | |
| D |
100pts。希望明天的 NOIP 2025 把最近几次考炸的分考回来。
NOIP 游记:Day 1 11.29
开考约 min
阅读四道题题面。
T1
一看 T1 怎么是个背包。一看数据范围,背包体积怎么 了???不对,但是每个物品价值为 ,可能可以贪心做。但是怎么贪呢?
- 每次选价格最低的买?不对。
1 100和60 60两个物品,你不炸了? - 因为两个物品一个便宜一个贵,所以要一起考虑。每次先把便宜的买了,然后再不断买两个的平均价格最小的?不对。
100 1和50 100两个物品,体积 101,你不炸了? - 先不断买平均价格最小的,然后不够了再买最便宜的?不对。
40 100,50 110和50 120三个物品,体积 140,你不炸了?
算了,先不管了,先去看 T2。
T2
诶,好像是DP。维护最值和取到最值的方案数,一看数据范围还是个 DP。应该不难吧?试试设个状态:
- 设 表示考虑了前面 个糖果,当前花了价格为 的原价最大值。转移分两种情况,一种买当前糖果,一种不买。不对啊,买不买是有条件的,仅记录 没办法确定是不是可以买或不买?
- 设 表示考虑了前 个糖果,买了 个 元糖果和 个 元糖果的原价最大值。不对啊还是不能确定买不买当前的?
- 设 表示考虑了前 个糖果,买了 个 元糖果和 个 元糖果的原价最大值,但是从 转移,钦定 这一段都要买?不对,先不说这个行不行,枚举一下轻松 ,我还不如直接打暴力。
算了我到时候应该想得到的。先看 T3 吧。
T3
诶一看就是个树形DP。怎么tmd是 mex?我考前还说这种数学里的概念肯定不会出到题目里。
诶?还是 DP?应该不会很难吧?试试设计状态。
状态设计一定要包含当前位于哪个节点。然后要包含当前点的决策,即填哪个数。所以设 表示考虑到第 个点,当前选的数字为 的最大的树的价值。但是这玩意怎么转移啊???如果说钦定当前的 是这个子树的 ,那倒还可能转移一下。
考虑是否有这样的性质:当前的 一定是子树的 才最优?不对,显然不是。因为给的样例里,叶节点就不符合该性质,其他节点好像也有反例。
那是否,当前的 一定是子树中选择数字的最大值?好像有点道理。考虑是否有这样一个性质:整个子树所占的数字一定是一个连续的数字段?似乎这样子钦定不会变劣。但是这样的话我要处理每个子树选择数字段的并?枚举每个点,再枚举每个点数字段的左右端点,再枚举每个点的儿子的左右端点, 好像还可以。但真有这个性质吗?我不会证。
先看看 T4 吧。
T4
诶,序列类型题目。我要对于每次询问,确定所有长度在 范围内的区间中,区间和的最大值。然后还要对于 的每个点,统计包含它的区间的区间和的最大值。
嗯。这题好像比较常规。朴素做法先枚举 ,再枚举每个点 ,再枚举左端点 ,然后右端点在 范围内。区间和嘛,前缀和一下即可。右端点在 范围内的区间和最大值可以用 st 表维护。时间复杂度 。
再看数据范围:补耗,出题人看不得 ,所有带 的算法最多只能做前三个测试点。但是 很小,不禁让人想到是不是真的要对于每个询问单独处理一次。 如果这么小的话,离线也没什么效果了,瓶颈就是怎么突破这个 。
初读题目结束,感觉应该不会很难吧。
初步题目难度估计:
| 题目 | 难度 | 算法 |
|---|---|---|
| candy | 贪心 | |
| sale | DP | |
| tree | 树形 DP | |
| query | 线段树 |
T1 大概可以拿将近满分,T2 和 T3 貌似部分分很少。T4 应该部分分蛮多的。
那我这次得控分控到 pts 左右吧?要不拿不到省一,我就得十年 OI 一场空了。
然后我从第一题开始想做法。
约 min
想 T1。
突然发现出题人给只会背包的小朋友准备了 pts 的高分。心里还算是有点底了。
观察样例解释,怎么感觉就是一直买平均价格最便宜的?但是我自己都造了 hack 了,大样例应该也跑不过几分。算了不写那个错误做法了。
想了半天,只想到一个肉眼可见的性质:小 R 的最终购买方案,对于每种糖果,一定是若干个 ,然后 个或 个 。
不过这貌似直接指向了 DP 的做法:物品体积为 ,价值为 的完全背包,和物品体积为 ,价值为 的 01 背包组成的混合背包。
啊啊啊啊啊为什么不会这题贪心啊?明明背包用贪心是错解,这里为什么就可以做?究竟本题有什么特殊的地方?
算了。真的想不到。把 DP 先打了。现在含泪得到了 pts。
考虑特殊性质:
-
当 时,贪心选最小价格的糖果一直买应该就行了。
-
当 时,这时永远也占不了便宜。所以应该是不断买 最小的,然后贪心选 最小的买吧。而且貌似贪心选 最小的,只会选一个。因为 ,同理 ,所以 ,。如果已经买不起 了,那肯定买不起 了。
为什么这样是对的?
-
为什么一定是买了 最小的?假设买得起 又买了 ,那把它们换成 一定不劣嘛。假设买得起 但是不买 ,那买 的策略也应该从小到大。
-
买完 最小的,会不会能买得起对应的 ?不可能。设买完 个 后,买了 是最小的,则 。买不起。
-
这时候我的左边那桌已经开始大声抓头发+骂人了(我如果向 CCF-NOI 科学委员会举报他考试讲话,而且还是骂 CCF,他准得禁赛三年)。
约 min
想了一些别的做法。除了基于原来的状态设计略作改变(但还是尝试失败),我还想到是否可以尝试让每个物品的清仓价格都为 ,然后选择一些商品,让它的原价翻倍。但是很快我发现这不能说是等价转化,只能说是和题意一点关系都没有。
现在总共想了 min,压力倒还好。我感觉应该就是本题状态设计比较巧妙吧,可能比较吃思维,我可能不擅长。
但是现在已经过去了快两个半小时了,按照我模考的经验,我还是得赶紧打掉暴力,后面两题的暴力 + 性质分,每道题大概要预留一个小时。
然后我开始想暴力。woc 这个暴力出题人只给前 个点呐。凉心出题人呐。
打完样例发现没过小样例。?怎么回事?wok 看错题意了,它的题目的正确意思是,小 R 用了贪心策略来买糖果使得他买的糖果原价总和最大,但是这个贪心是错的,你有设定清仓价格的很多方案,问你有多少方案使得他的贪心策略是对的。
我还以为问的是,我有很多设定清仓价格的方案,按照这种贪心策略,小 R 能买到原价总和最大是多少,取到最大值的时候方案有多少。但是要是真的写成题意,也是 但也怪我不手玩样例。
使小 R 购买糖果原价总和最大的方案数。这里感觉可能不是我的问题,是题目真的写得模棱两可。我 怎 么 又 读 错 题 了。
考前读错的题
- [NOIP 2024] 树的遍历
- [CSP-S 2025] 谐音替换
算了,现在已经没时间想正解了。而且卡贪心这种题,怎么像个构造题一样,这么恐怖肯定和 Ad-hoc 一样难做。还是老老实实打暴力吧。
大概打到 ,仅仅收获 pts。
这时候边上的大哥还在 询问 CCF 的浮木。我没带水,只带了饮料,喝得喉咙有点齁。问监考员,说附近没有接水的。好吧。
当前得分 pts。
约 min
稍微想了一下这个 到底咋搞,想了很久还是赶紧这个结论不太对。可能要先确定枚举子树的某个顺序,再那样是对的。那个做法正确性还是没法保证,而且现在也没有时间让我把那个做法打了,跑样例看正确性了。保险起见还是打个暴力吧。
一个肉眼可见的性质是,每个结点上填的数字应该不会超过它的子树大小。并且 号结点处产生的贡献应该最多就只能为 (都是感性理解出来的)。第二个结论显然;第一个结论因为如果你在某点填 的数,让它的某个祖先来填上 这个数,那么你把这两个点交换位置,贡献至少增加 对吧。
所以我暴力枚举每个点的填数,然后再计算此时树的价值。考场代码时间复杂度可能是 吧。但是跑样例没跑过。我输出了过程但是感觉都没问题,不知道为啥就跑不过样例。我想这下完了,难道我要把 T4 AC 了吗。
当前得分 pts。
约 min
完了现在没有退路了。T4 必须多拿点分。
想了一段时间突然顿悟:原来是枚举 ,来更新 处的答案,但 里明明有很多个 ,这就是重复计算。我们为何不枚举 ,一次性对 里的每个 都更新答案呢?
初步想法是,枚举 ,取 区间里的最值,设取到最值在位置 ,则最大区间和为 ( 是前缀和数组)。然后用 更新 的所有答案 即可。用线段树 更新 的每个位置(区间取 max)即可。 时间复杂度 ,卡卡常甚至可以通过!
我灵机一动发现可以继续递归到 区间,继续寻找最值位置,更新最值左边的答案。如果数据过水,最值全在中间位置,时间复杂度 ,但是很容易被卡成 。
然后我又发现不对啊,线段树什么时候可以对区间取 max 了???(至少我考场上写着写着发现不对劲,最坏情况下也能被卡成暴力取 max)我考场上觉得线段树也许不能区间取 max 了。只能写一个暴力取 max。如果线段树真的可以区间取 max,请在评论区告诉我,谢谢。。。
注:我在考后发现这样写的时间复杂度是 ,比暴力还烂。但貌似考场上我没意识到这点,着急忙慌地写了 。。。
考场上测样例时,跑测试点 的时候都很快,所以没意识到自己写了个 大劣解。希望 CCF 的数据也和样例一样水。
预估得分 pts。
最后 min
仔细地检查了自己的文件操作,确认没有任何问题。
得分
| 题目名称 | 预估得分 |
|---|---|
| candy | |
| sale | |
| tree | |
| query |
呜呜呜肯定没省一了qwq。
NOIP 考后
Day 1 11.29
走出考场门,听到一些人在讨论:
“T3 好像对重儿子考虑即可,轻儿子全部赋 就是最优了。”
“T3 那题我写了个又臭又长的长链剖分。”
“你真敢写长链剖分啊?”
“唉,我 T1 的反悔贪心没调出来……”
打开 LA 群,发现大家都说这次好难:
“这场比赛比 NOI 2025 难。真的,我没开玩笑。”
“T2 不是写一个范特蒙德卷积就可以 以内了吗?”
我:“重儿子?长链剖分?反悔贪心?范特蒙德卷积?我考的不是 NOIP 提高组吗?”
看到大家都觉得难我就心里平衡了。到底多难啊?我打开洛谷,一看:
我突然想起来自己考试的时候发现下发文件叫 "day1.pdf"。豁然开朗:一定是 dzd 不小心搞错了,把 NOI 的题目下发下来当 NOIP 的试题了。dzd 真好,知道我没有资格打 NOI,还把 NOI 的题搬来给我做。
已严肃完成今日“NOI/NOI+/CTSC”大学习。已严肃完成今日“National Olympiad in Informatics Plus”大学习。
冷知识:如果这次比赛太难,我们或许可以把 IOI 或者 NOI 的题搬来做一下。
其实考完之后,也应该算是 AFO 了。但是还是希望不要那么痛苦地和 OI 分手,于是我和她吃了一顿分手饭,然后决定在最后一周把之前我们打算一起做的事情做掉。
宝宝你知道吗,下周我们要分手了()
啊?
()
……能不分吗qwq
你说呢()
你已经高二了,考完我们就不能再在一起了()
我不要啊呜呜呜
还有一周要 NOIP 了吧?祝你省一awa
好吧我知道了……
我相信你一定可以的
嗯嗯
嗯……你考完了吧?考得怎么样?
你为什么要这么为难我?
我不是故意的嘛……
那你为什么给了他们那些学 NOI 级算法的人那么多机会?你不是说好只要我学提高级算法的吗?
我没有……我没有去爱他们那些学 NOI 算法的……
好了,别说了。你今天是来和我分手的吧
你别生气嘛……
我还记得,我刚认识你的时候,是在初中的一个信息学社团。当时我以全校第一的成绩考进社团,你还笑着奖了我一根棒棒糖……
我还记得,在初中的时候,我甚至只会橙题黄题,但是你说恋爱简简单单的就好,不要操心这个。甚至我 J 组只打了 90pts,S 组莫名爆 0,你也说很不错了
我还记得,在高一第一年学 OI 时,我好不容易做出了一道绿题,你还开心地夸我厉害,在我的手心里画绿色的AC……qwq
我还记得,高一第一年打 S 组只拿了 75pts 无缘 NOIP,当时我哭了,是你亲手拭去了我的泪水,对我说:“没事,我会永远陪着你。”
我还记得,高二这年,我终于提升了自己的实力,在 S 组拿到了 149pts,你高兴地拉起我的手,抱着我说我一定可以拿到省一的
我还记得,我跟你说我思维也不行,数学也不好,贪心也不擅长,NOI 级算法更是根本不会,如何省一。你说没关系的,只要我好好学提高级算法,你就很幸福了
为什么现在你被 NOI 算法这种花言巧语轻而易举地骗走了?说好的一直爱我呢?
我没有……
说实话,我还是爱你的
但是你已经高二了,我们继续待在一起,我能为你带来什么呢?
你要考好的大学,你应该拥有更广阔的人生。而这都是我给不了你的……
不是我不爱你了,而是我必须离开了。你要记住,我一直是爱你的
祝你考个好大学,人生一片灿烂
我在大学的ICPC等你
好
我爱你
我也爱你
相关推荐
评论
共 1 条评论,欢迎与作者交流。
正在加载评论...