CSP 2020 复习杂题选做

## Codeforces Rounds [Codeforces Round #680 Div. 2](https://codeforces.ml/contest/1445) 做出 ABC，D 是结论，想不到。 ## DP 这部分重在思维。 - [P1412 经营与开发](https://www.luogu.com.cn/problem/P1412) DP 题，目前质量的维度无法表示，于是反过来，乘上系数即可。 - [P1284 三角形牧场](https://www.luogu.com.cn/problem/P1284) 看上去 DP，实际上模拟退火调调参就可以过。 - [P3205 [HNOI2010]合唱队](https://www.luogu.com.cn/problem/P3205) 区间 DP，想了半天 $\mathcal O(n^3)$ 枚举第一个数线性 DP，没发现这样就是枚举了所有区间... - [P6008 [USACO20JAN]Cave Paintings P](https://www.luogu.com.cn/problem/P6008) 关于联通块的 DP，想不到。[题解](https://www.luogu.com.cn/blog/vocalise/solution-p6008) - [P4158 [SCOI2009]粉刷匠](https://www.luogu.com.cn/problem/P4158) 序列 DP 再套一个背包。其中序列 DP 部分有劣 $\mathcal O(nm^2t)$ 做法可吸氧过，优做法 $\mathcal O(nmt)$，利用了贡献可分离的性质。 - [P2657 [SCOI2009] windy 数](https://www.luogu.com.cn/problem/P2657) 数位 DP 模板。感觉挺套咯。 ## DS 这部分重在所有会的都复习一遍。 - [P4592 [TJOI2018]异或](https://www.luogu.com.cn/problem/P4592) 树上和 DFS 序上可持久化 01trie 求异或 kth（最大值）模板。 - [P2894 [USACO08FEB]Hotel G](https://www.luogu.com.cn/problem/P2894) 线段树板子，但是不知道复杂度有没有保证。 - [SP2713 GSS4 - Can you answer these queries IV](https://www.luogu.com.cn/problem/SP2713) 线段树板子，复习用。 - [P3605 [USACO17JAN]Promotion Counting P](https://www.luogu.com.cn/problem/P3605) 正解树状数组，但是没想到，于是当 Splay 复习了。~~但是不 `Splay` 也能过~~ - [P1552 [APIO2012]派遣](https://www.luogu.com.cn/problem/P1552) 线段树合并裸题。但是可并堆是正解，被吊打。 - [P3521 [POI2011]ROT-Tree Rotations](https://www.luogu.com.cn/problem/P3521) 线段树合并，但是合并时要算逆序对。自己做出来，感动。[题解](https://www.luogu.com.cn/blog/vocalise/solution-p3521) - [P4390 [BOI2007]Mokia 摩基亚](https://www.luogu.com.cn/problem/P4390) 三维偏序板子，复习 CDQ 分治。 - [P3261 [JLOI2015]城池攻占](https://www.luogu.com.cn/problem/P3261) 左偏树。接近板子，和上面 P1552 相似。 ## 数论 这部分补充还不会的基础算法。 - [P3455 [POI2007]ZAP-Queries](https://www.luogu.com.cn/problem/P3455) 不知道多少倍经验题。莫反初步复习。 - [P2303 [SDOI2012] Longge 的问题](https://www.luogu.com.cn/problem/P2303) 没有高深知识。[题解](https://www.luogu.com.cn/blog/vocalise/solution-p2303) - [P1829 [国家集训队]Crash的数字表格 / JZPTAB](https://www.luogu.com.cn/problem/P1829) 莫反套路题。[题解](https://www.luogu.com.cn/blog/vocalise/solution-p1829) 但是完全自己做出来，挺感动。 - [P4777 【模板】扩展中国剩余定理（EXCRT）](https://www.luogu.com.cn/problem/P4777) 顺便复习了 exgcd。 - [P3312 [SDOI2014]数表](https://www.luogu.com.cn/problem/P3312) 得到分块 + 卷积的式子，但是卷积是有一定限制的。 因此离线从小到大询问，每次树状数组上插入算卷积。 感觉挺神仙的。而且筛 $\sigma$ 都不怎么会。[题解](https://www.luogu.com.cn/blog/vocalise/solution-p3312) ## 数数/期望 这部分重在思维。 - [P3223 [HNOI2012]排队](https://www.luogu.com.cn/problem/P3223) 非常基础的数数式子，但是高精... 屑 出题人 屑 - [P1350 车的放置](https://www.luogu.com.cn/problem/P1350) 基础计数题。 - [P1446 [HNOI2008]Cards](https://www.luogu.com.cn/problem/P1446) Burnside 引理，套一个简单的 DP。 ## 图论 这部分直接爬了。 ## 杂项 - [P1485 火枪打怪](https://www.luogu.com.cn/problem/P1485) 一年前的坑，其实是比较简单的维护二次函数和的方法。 但是还是卡了几下。