NOIP复习记录
upd 12.10 完结撒花
OI生涯快结束了,记录一下最后一赛季的复习过程
练习题参考模拟赛&题单 以紫题为主
尽量少写科技向/板子类的紫题,这对思维能力的提升微乎其微
记录
Week 1
9.18
- P5012 水の数列
并查集合并区间的Trick比较好想,但是看题的时候完全没想到枚举x -
P2048 [NOI2010] 超级钢琴
拆分答案贡献用ST表维护,同时巧妙利用堆来一次性存储多个起点相同的区间
Total:
9.19
-
P4168 [Violet] 蒲公英
比较简单的分块题,关键在于使用类似dp的思想降低预处理复杂度 - P4113 [HEOI2012] 采花
与 HH的项链 类似,询问按左端点排序,用树状数组存储前缀贡献;不同之处在于颜色对答案的贡献应该放在第二次出现的位置
Total:
9.20
-
P3224 [HNOI2012] 永无乡
简单的线段树合并板子题 也可以用平衡树启发式合并写 - P4921 [MtOI2018] 情侣?给我烧了!
- P4931 [MtOI2018] 情侣?给我烧了!(加强版)
神仙组合数学题。。。 感觉组合数学是一大弱点,要加强练习。
Total:
9.21
- 参加CSP-S1,难度比较正常,估分85;
upd:最终得分79,被薄纱了
Week 2
9.24
-
P1361 小M的作物
某场模拟赛的题,是没见过的最小割建模 总体思路比较简单,实现也不难
(然而巨大的边密度会制裁每一个想用EK过题的人和数组开小的我)
Total:
9.25
学习了 矩阵树定理 (不会证的神奇定理)
-
P7112 【模板】行列式求值
补一下之前没写的板子 -
SP104 HIGH - Highways
-
P6178 【模板】Matrix-Tree 定理
矩阵树定理板子,统计无向图生成树数量/边权积 -
P4111 [HEOI2015] 小 Z 的房间
转换建图之后求生成树数量 -
P3317 [SDOI2014] 重建
做个简单的数学转化(提取公因式)就是矩阵树定理板子了 -
P4336 [SHOI2016] 黑暗前的幻想乡
二进制枚举+容斥+矩阵树定理,好题
Total:
9.26
-
P3349 [ZJOI2016] 小星星
非常离谱的二进制枚举+容斥题,套路类似昨天的P4336
Total:
9.27
-
P3830 [SHOI2012] 随机树
第一问比较好分析省选白送50pts,第二问关于系数\frac{1}{i-1} 的证明有点离谱 -
P4001 [ICPC-Beijing 2006] 狼抓兔子
最小割/对偶图最短路板子,但是为什么最短路比网络流慢/ts -
P3806 【模板】点分治 1
学习一下淀粉质点分治,思路和实现都大量利用了树的重心的性质,但是尺取法还是不太好想/ll -
P4178 Tree
同样的点分治题,容斥太麻烦了,尺取过程中直接减去相同子树的点就行了
Total:
9.28
-
P6329 【模板】点分树 | 震波
恶心题 当你写了一坨bug发现它能运行.jpg -
P2221 [HAOI2012] 高速公路
没怎么用到期望的性质,基本上就是简单的线段树题。 -
P4564 [CTSC2018] 假面
恶心的期望题,第一种操作比较好处理,第二种操作的回退dp和分讨极其恶心。
Total:
Week 3
10.4
-
P5494 【模板】线段树分裂
线段树分裂板子,和平衡树分裂类似,一般适用于权值线段树。 -
P2824 [HEOI2016/TJOI2016] 排序
二分的写法相对比较简单,但是我选择线段树分裂/hanx 调吐了,区间维护需要用到类似ODT的结构。 -
P3239 [HNOI2015] 亚瑟王
主要利用了期望的线性性质分解答案的贡献,思路还是期望题一如既往的恶心。 -
P4562 [JXOI2018] 游戏
非常神奇的计数题,很多期望题使用计数的方法计算期望,而本题用期望值计数。
Total:
10.5
-
P1822 魔法指纹
奇奇怪怪的爆搜题,不知道为什么能评紫
Total:
Week 4
10.7
-
P3750 [六省联考 2017] 分手是祝愿
期望dp?思维题!期望的部分通过巧妙设置状态或者差分(本质相同)可以优化处理复杂度;最不好搞的还是猜结论 -
P8347 「Wdoi-6」另一侧的月
结论题/思维题;想到了就是想到了,没想到就是没想到(这个比较好想) -
P11169 「CMOI R1」Bismuth / Linear Sieve
简单推柿子+猜结论即可,难度不大 -
P2290 [HNOI2004] 树的计数
Prufer序列入门题,本质上来说也是道结论题 -
P2292 [HNOI2004] L 语言
ACAM上的简单dp,优化需要小寄巧,但是状压不如剪枝
Total:
10.8
-
P10220 [省选联考 2024] 迷宫守卫
完成了省选的遗愿思维题,关键在于贪心的思路和递归处理子问题。
Total:
10.9
-
P4314 CPU 监控
不简单的线段树题(我以为只是线段树板子.jpg) 分块貌似会好写一点 -
P4602 [CTSC2018] 混合果汁
难得有一道能几乎全部自己想出来的紫题 贪心+二分的暴力比较好想,主席树做法本质上是优化暴力,整体二分则是离线处理所有询问(也要用到线段树优化check复杂度)。 -
P4284 [SHOI2014] 概率充电器
dp状态比较难想到,但是有了dp状态设计之后换根dp就很简单了
100紫祭 /hanx
Total:
10.10
-
P10534 [Opoi 2024] 简谐振动
简单的找规律/数学题
Total:
10.11
学习了NOIP基本不考的LCT
-
P3690 【模板】动态树(LCT)
LCT板子 -
AT_exawizards2019_d Modulo Operations
不太好想的计数dp题/思维题
Total:
10.13
-
P11188 「KDOI-10」商店砍价
简单题,枚举剩下的数即可。
Total:
Week 5
10.14
-
AT_arc154_d [ARC154D] A + B > C ?
非常有意思的交互题,同时考察了数学和排序算法。 -
P2770 航空路线问题
建图方法算是老套路了,但是不会费用流直接糊最大流被制裁了/qd -
P3381 【模板】最小费用最大流
费用流板子,既然都用了费用流那就水一下咯/hanx
Total:
10.15
-
AT_abc295_e [ABC295E] Kth Number
期望题,用到了经典的概率-期望trick;本质上还是计数题。
Total:
10.16
-
P5658 [CSP-S2019] 括号树
括号串与栈的关系&树形dp,比较简单。但是某人口胡的做法是主席树 -
P7114 [NOIP2020] 字符串匹配
有意思的字符串哈希题,更难得的是直接口胡出了正确做法/hanx -
P7961 [NOIP2021] 数列
和上面那道蓝题比难了inf点,当然还是因为我计数dp太菜了/ll -
P6776 [NOI2020] 超现实树
从7kbyte佬那里看到的很有意思的 (Adhoc?) 题,整体偏CF风格,想到了就是想到了,没想到就是没想到。
Total:
10.17
-
P11183 [ROIR 2018 Day2] 大数据处理
一道比较难想到的题,整体思路和树形dp类似但是用集合合并转移状态。
Total:
10.20
-
P11217 【MX-S4-T1】「yyOI R2」youyou 的垃圾桶
简单的线段树题,略微卡常但是无伤大雅 -
P9870 [NOIP2023] 双序列拓展
完成了去年NOIP的遗愿Adhoc题,有充足时间的情况下思路并不难想,但是考场上就不一定了...
Total:
Week 6 (CSP-S2考试周)
积极备考CSP-S2
10.21 (Day -4)
上午模拟赛,题目有点水,但是T3的Adhoc有点离谱
-
P8496 [NOI2022] 众数
不难的DS题,由于绝对众数的性质很多所以做法较多。
Total:
10.22 (Day -3)
上午模拟赛,题目还是有点水,但是T3哈希没时间写了
-
P8866 [NOIP2022] 喵了个喵
为什么会有思路不好想代码还难写的Adhoc题目啊/youl -
P2617 Dynamic Rankings
树状数组套主席树板子题,(和下面这位相比)较为简单。 -
P3380 【模板】树套树
恶心题,基本操作还是树状数组套主席树,但是求前驱后继的特判太恶心了
Total:
10.23 (Day -2)
-
P7170 [COCI2020-2021#3] Sateliti
二维字符串哈希+二分的题,但是哈希方法不是很好写 -
P1975 [国家集训队] 排队
树套树板子题,思维难度比较低。 -
P5666 [CSP-S2019] 树的重心
非常恶心的树上计数题/tuu 无论是哪种做法都不好想还不好写。
Total:
10.24 (Day -1)
-
P9768 [ROIR 2021 Day 2] A+B
简单计数题,完全没有蓝题难度。 -
P3372 【模板】线段树 1
学标记永久化的时候发现自己线段树1的板子都没写/qd -
P4097 【模板】李超线段树 / [HEOI2013] Segment
不会单调队列维护凸包的我选择李超线段树/hanx -
P11014 「ALFR Round 4」D 罪人的终幕
数论转化有点不好想,转化完之后就是简单的李超树模板题了
Total:
10.25 (Day 0)
复习容斥。
-
P1450 [HAOI2008] 硬币购物
简单容斥题,二进制枚举所有可能的情况即可。 -
P4859 已经没有什么好害怕的了
dp+容斥/二项式反演,不太好想的计数题
Total:
10.26 (Day 1)
已经没有什么好害怕的了。
CSP-S 2024 RP++
游寄
实际得分
10.27
-
P11233 [CSP-S 2024] 染色
赛后用30min把T3正解改完了,然而终究是马后炮了。 -
P3157 [CQOI2011] 动态逆序对
同样是简单的树状数组套主席树板子题。
Total:
Week 7
10.28
-
P8314 [COCI2021-2022#4] Parkovi
模拟赛的简单二分+贪心题。 -
P8315 [COCI2021-2022#4] Šarenlist
模拟赛的简单容斥计数题。
Total:
10.29
-
P11234 [CSP-S 2024] 擂台游戏
带\log 写法的思路不太好想,优化到线性的过程需要认真分析复杂度;同时O(n) 写法的常数有亿点大,需要一系列的玄学卡常&剪枝。
Total:
10.30
-
P4643 [国家集训队] 阿狸和桃子的游戏
诈骗题,结论很好证但是不好猜。 -
AT_arc105_e [ARC105E] Keep Graph Disconnected
博弈论题/思维题/结论题(要素过多);博弈论题要多从奇偶性的角度考虑问题。
Total:
10.31
学习了长链剖分。
-
P5903 【模板】树上 K 级祖先
长链剖分的前置芝士板子。 -
P3565 [POI2014] HOT-Hotels
-
P5904 [POI2014] HOT-Hotels 加强版
长剖优化dp板子题,整体思路类似dsu但是用邪恶的指针把状态转移数优化到O(n) 。 -
AT_arc086_c [ARC086E] Smuggling Marbles
学长剖的目的之一,概率dp+长链剖分优化。 -
P1306 斐波那契公约数
结论题,配合简单的矩阵快速幂优化。
Total:
11.1
-
P10099 [ROIR 2023 Day 2] 美丽序列
离谱的dp题,map套vector被卡TLE只得被迫写9维dp /fn/fn/fn
Total:
11.2
-
P11244 吻秋
洛谷月赛的结论题,但是被我暴力DS艹过去了/kx 然后就被出题人制裁了/dk
Total:
11.3
-
AT_arc107_d [ARC107D] Number of Multisets
比较抽象的计数dp,关键点在于设计转移时要不重不漏。
Total:
Week 8
11.4
-
P4792 [BalticOI 2018] 火星人的 DNA
模拟赛的简单题,二分答案之后用(个人非常喜欢的)set和multiset维护即可。 -
P10100 [ROIR 2023 Day 2] 石头
模拟赛的特殊性质题,重点在于观察题目条件的性质并确定选取答案的可能范围。
Total:
11.5
简单水了下圆方树
-
P5236 【模板】静态仙人掌
普通圆方树板子,比较好写。 -
P10932 Freda的传呼机
与上面那题完全相同(水)
Total:
11.6
-
AT_agc008_f [AGC008F] Black Radius
@TLEWA推荐的题,计数+换根dp,关键点在于设计出不重不漏的计数方法,即让每种方案只在d 最小处被计数;次要的难点是需要分讨某个点不为关键点的情况。 -
P4630 [APIO2018] 铁人两项
比较水的广义圆方树板子;个人认为计数部分难度>圆方树。 -
P4320 道路相遇
比上面那道题还水的圆方树板子题,树上差分即可。 -
UVA1464 Traffic Real Time Query System
同样很水的圆方树板子。 -
P6773 [NOI2020] 命运
非常恶心的线段树合并优化dp。O(n^2) 的dp设计个人认为并不好想;线段树合并的思路比较类似长链剖分或者DSU,但是需要维护tag,细节比较多。
Total:
11.7
-
P10785 [NOI2024] 集合
不算太难的哈希题,分析题中“相似”的性质转化成判定集合同构即可。哈希实现需要注意模数细节。
Total:
11.8
-
P6756 [BalticOI2013] Brunhilda’s Birthday
数学题,主要是通过打表等手段观察出答案分段的性质。 -
P11262 [COTS 2018] 题日 Zapatak
做法较多的哈希题,官方题解做法利用了异或的性质二进制分讨。
Total:
Week 9
11.11
-
AT_arc100_c [ARC100E] Or Plus Max
Min-Max容斥/子集卷积板子题;子集卷积可以通过FMT/高维前缀和实现。
Total:
11.12
-
P3175 [HAOI2015] 按位或
Min-Max容斥+子集卷积+期望,同时利用了Min-Max容斥在期望意义下成立的特性。 -
P4707 重返现世
推导过程需要用到扩展Min-Max容斥,实际实现上通过dp来转移;dp状态的边界较难推导。
Total:
11.13
-
P5643 [PKUWC2018] 随机游走
Min-Max容斥+dp;难点在于想到待定系数处理dp方程。 -
AT_abc215_h [ABC215H] Cabbage Master
建二分图,利用霍尔定理转化题目条件,高维前缀和处理后容斥即可。
Total:
11.14
-
P1527 [国家集训队] 矩阵乘法 经典整体二分题,使用二维树状数组优化check复杂度。
-
P3527 [POI2011] MET-Meteors
同样是经典的整体二分题,树状数组优化check复杂度。
Total:
Week 10
11.18
-
P9195 [JOI Open 2016] JOIRIS
模拟赛的构造题,思路比较暴力但是不好想。
Total:
11.19
-
P3402 可持久化并查集
可持久化并查集板子题,本质上就是并查集按秩合并与可持久化线段树的组合。 -
P3293 [SCOI2016] 美味 异或操作可以拆分后按位贪心,考虑建0-1 Trie或权值线段树。由于题目有询问区间所以还需要可持久化。
Total:
11.20
-
P3920 [WC2014] 紫荆花之恋
动态重构点分树+平衡树,强制在线才是原罪。
Total:
11.22
-
AT_joi2020ho_c スタンプラリー 3 (Collecting Stamps 3)
模拟赛的区间dp题,状态有点麻烦,而且写炸了/ll
Total:
11.23
-
P11307 [COTS 2016] 建造费 Pristojba
很新奇的线段树套set优化prim最小生成树,写了篇题解。
Total:
11.24
-
P10241 [THUSC 2021] 白兰地厅的西瓜
线段树合并优化dp,但是思路不难想。 -
AT_dp_t Permutation
排列dp的板子题,复习一下练练手 -
P2467 [SDOI2010] 地精部落
还是排列dp板子题
Total:
Week 11 (NOIP考试周)
11.25 (Day -4)
-
P5590 赛车游戏
比较奇葩的差分约束题/qd -
P4407 [JSOI2009] 电子字典
trie上暴力dfs即可 -
P1295 [TJOI2011] 书架
线段树优化dp比较简单,关键是单调栈预处理最大值的影响范围。
Total:
11.26 (Day -3)
-
P5937 [CEOI1999] Parity Game
zaochen推荐的带权并查集题,带权并查集的部分很好想,但是转化到前缀和约束真不好想/ll -
P2235 [HNOI2002] Kathy函数
抽象的二进制翻转函数 抽象的高精度 抽象的数位dp -
P2144 [FJOI2007] 轮状病毒
一眼矩阵树定理,但是太慢了只能用py打表 还爆了numpy的精度/fn/fn/fn
Total:
11.27 (Day -2)
模拟赛,摆烂
11.28 (Day -1)
模拟赛,摆烂
出去坐地铁玩没注意时间,下午迟到了1h /qd
11.29 (Day 0)
没有模拟赛,摆烂
下午出发,晚上出去吃饭&摆烂 详情见NOIP游寄
打算写季风,但是摆了
11.30 (Day 1)
开考,详情见NOIP游寄
考后估分
回家 继续摆烂 准备whk
Week 12
12.6
NOIP出分,没挂分
完结撒花
下一篇可能就是省选的了(笑