Contents
前言
NOIOL 有点小爆炸
省选 ++rp
学习内容
- Link-Cut Tree
- 线性基
- 后缀数组
做题记录
21/04/01
- P3565 [POI2014]HOT-Hotels
- P5904 [POI2014]HOT-Hotels 加强版
长链剖分优化 dp
- P5384 [Cnoi2019]雪松果树
长链剖分
21/04/02
- P3899 [湖南集训]谈笑风生
长链剖分
- CF208E Blood Cousins
长链剖分
21/04/03
- CF246E Blood Cousins Return
dsu on tree
21/04/04
- P6625 [省选联考 2020 B 卷] 卡牌游戏
sb 贪心
- P4178 Tree
点分治，使用树状数组维护贡献
- P6626 [省选联考 2020 B 卷] 消息传递
点分治
- P3690 【模板】Link Cut Tree （动态树）
LCT
- P6136 【模板】普通平衡树（数据加强版）
新码风 Splay
21/04/06
- P3203 [HNOI2010]弹飞绵羊
LCT。建边，然后找根到该节点的路径长（一遍 access 和一遍 splay 即可）
- P1501 [国家集训队]Tree II
注意标记的下传即可
21/04/07
- P2870 [USACO07DEC]Best Cow Line G
SA。
21/04/08
- P2852 [USACO06DEC]Milk Patterns G
SA，求出现超过 k 次的子串的最大长度，即为寻找每 k – 1 个相邻的 ht[i] 的最小值的最大值。可以使用 multiset<int> 维护。
- P4149 [IOI2011]Race
点分治
- P3812 【模板】线性基
线性基
- HDU3949 XOR
线性基求异或 k 大
- BZOJ#3513. [MUTC2013]idiots
求随机选三个数边长可以组成三角形的概率。正难则反，算不能拼成三角形的方案数。考虑自身卷积，并去重，得到两个木棍能拼出的方案数，然后再做一下前缀和，得到两边之和小于等于该边的方案数，对于所有木棍长度求个和就得到了不能的方案数，直接算即可。
- BZOJ#2194. 快速傅立叶之二
推式子，C_k = \sum_{k\le i\lt n} a_ib_{i – k}，推完之后换元化为卷积形式然后 FFT。
21/04/09
- P2659 美丽的序列
单调栈
- [AGC005B] Minimum Sum
单调栈
- P4248 [AHOI2013]差异
SA 与单调栈
21/04/10 省选 Day 1
100 + [40, ?] + [0, 16] = [140, 156?]
炸干净了，T3 暴力爆炸了，希望 Day 2 能翻盘吧
留言