2019省选复习周做题计划

随便找了点省选前需要复习的知识点相关的题目..

题目

LCT/树剖

共价大爷游长沙

小清新数据结构题

最小差值生成树

QTREE4

淀粉质

树上游戏

字符串

[APIO2014]回文串

[HEOI2016/TJOI2016]字符串

Trie

最大异或和

最长异或路径

整体二分/树套树

[ZJOI2013]K大数查询

cdq分治

[Violet]天使玩偶/SJY摆棋子

[NOI2007]货币兑换

莫比乌斯反演

[SDOI2014]数表

最小公倍数之和

Lucas的数论

组合数学、容斥原理、斯特林数

重返现世

[HEOI2016/TJOI2016]求和

[国家集训队] Crash 的文明世界

多项式、生成函数

食物

[CodeChef] COUNTARI

万径人踪灭

The Child and Binary Tree

城市规划

付公主的背包

玩游戏

记录

共价大爷游长沙:如果要获取一个点的子树信息,要么 access 父亲 Splay 自己然后看实+虚+自己,要么 access 自己然后看虚+自己。

最大异或和:一开始尝试用线段树合并做,复杂度是 $\mathcal O(n(\log(n+m)+\log w)+m\log(n+m)\log w)$,卡常卡不过去,尝试用 bitset 优化,后来发现除以 $32$ 被 $\log$ 掉了,加上带来的一些常数后根本没有优化.. 只不过后来发现可持久化 Trie 真的挺好写的,(只要会主席树不需要学也能 yy 出来的感觉)。

最后果然没做几道题..只不过比我想象中还要少一点..

写了点 OI Wiki,过程中也写了几道计划外的题。