2020年12月 OI学习记录

前言

11 月是水过来的，12 月活过 NOIP 之后要努力了。

第一周复习 NOIP，之后到寒假前全力冲刺弱的板块，起码达到提高组水平：

• 贪心
• 二分
• 数论
• 组合计数
• 分治
• dp

学习内容

• Trie
• 平衡树（Treap、Splay、FHQ-Treap）
• exCRT
• 拉格朗日插值
• 整除分块

做题记录

20/12/01

• P1052 过河

dp，需要对坐标轴上进行缩点，（特判 s=t）考虑如果一个石头无论如何可以被前面的石头不跳过，就直接缩，之后就是 f_i=\min_{j\in[s,t]}\lbrace f_{i-j}+[i为石子] \rbrace

• P3951 小凯的疑惑

打表找规律，答案为 ab-a-b，证明一下写

• SP666 VOCV – Con-Junctions

第一问直接照搬没有上司的舞会，第二问根据乘法原理和加法原理分类讨论即可

• P1099 树网的核

题面十分毒瘤的树形 dp，综合考察了直径的性质。https://imyangty.com/oi/1234

20/12/02

• P5664 Emiya 家今天的饭

计数 dp

• P5858 「SWTR-03」Golden Sword

线性 dp，设 f_{i,j} 为放入第 i 个元素后锅中有 j 个元素可达到的最大耐久值，显然有

f_{i,j}=\min_{k=\max(0,1-j)}^{\min(s,w+i-j)}\lbrace f_{i-1,j-1+k}+j\times a_i\rbrace

其中 k 为我们要拿掉的元素数量。这样做复杂度可视为 O(nws)，单调队列稍加优化可达到 O(nw)

20/12/03

• P5017 摆渡车

斜率优化，在奇奇怪怪的问题上调了很久

20/12/05 NOIP 爆炸

20/12/07

• P3174 [HAOI2009]毛毛虫

树形 dp

• UVA1401 Remember the Word

Trie 优化 dp

• UVA11732 “strcmp()” Anyone?

Trie 上计数 https://imyangty.com/oi/1241

20/12/12

学习平衡树

• P3369 【模板】普通平衡树

使用 Treap 和 Splay 通过

• P6136 【模板】普通平衡树（数据加强版）

使用 Treap 通过

20/12/13

• P6136 【模板】普通平衡树（数据加强版）

使用 Splay 通过

20/12/15

• P2286 [HNOI2004]宠物收养场

平衡树，练习 Splay

• P3391 【模板】文艺平衡树

使用 Splay 通过

• P1486 [NOI2004]郁闷的出纳员

平衡树裸题，运用了差量思想。考虑全局变量记录所有人工资的加减情况，然后插入时插入 k-\Delta 以消除影响。删除时可将所有会被删除的集中起来然后直接删掉。注意 kth() 函数的实现是求第 k 大

20/12/18

• P3165 [CQOI2014]排序机械臂

调了三天的题，Splay 维护区间信息

• 使用 FHQ-Treap 通过普通平衡树和文艺平衡树

20/12/19

• P2596 [ZJOI2006]书架

FHQ 的一个 trick：可以记录每个节点的父亲，这样可以快速查找某值在序列中的位置，同时不要忘了 pushup

• P4146 序列终结者

平衡树维护区间信息，标记比较多，注意维护即可

20/12/20

• P3224 [HNOI2012]永无乡

启发式合并 FHQ-Treap，使用并查集维护连通性

• P5338 [TJOI2019]甲苯先生的滚榜

平衡树板子，卡常

20/12/21

• POJ2689 Prime Distance

区间筛素数板子，注意特判

20/12/22

• P1463 [POI2002][HAOI2007]反素数

dfs

20/12/24

• UVA11526 H(n)

整除分块，O(\sqrt n)

• P2261 [CQOI2007]余数求和

整除分块 + 等差数列

20/12/25

• P2260 [清华集训2012]模积和

推式子 + 整除分块

• P3935 Calculating

推式子 + 整除分块

• P4781 【模板】拉格朗日插值

拉插

20/12/26

• P4280 [AHOI2008]逆序对

线性 dp + 树状数组，注意讨论 -1 可能产生的贡献

• P4777 【模板】扩展中国剩余定理（EXCRT）

exCRT

20/12/27

• P3868 [TJOI2009]猜数字

CRT，需要快速乘防溢出

20/12/31

• P4774 [NOI2018] 屠龙勇士

细节相当繁琐的 exCRT，第一道黑题祭