前言

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,第一道黑题祭

最后修改日期:2020年12月31日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。