标签：总结 10 21 22 中位 中下 板子 DP
题
| name |
diff. |
note |
date |
| ABC375F Road Blocked |
1546 |
floyd |
10-16 9 |
| P5684 [CSP-J2019 江西] 非回文串 |
中位绿 |
组合 |
10-16 10 |
| ABC203D Pond |
1578 |
中位数性质，二分 |
10-17 19 |
| P11162 「BalkanOI 2023 Day1」Car Race |
上位蓝 |
dsu on tree 好题，维护轻儿子子树内的车是否会炸的状态，合并到重链上 |
10-17 22 |
| P11157 【MX-X6-T3】さよならワンダーランド |
1366/中位绿 |
人类智慧，考虑用 \(k=i+j\) 去换元 |
10-18 14 |
| ABC232G Modulo Shortest Path |
2466 |
考试题，前缀优化建图 |
10-18 21 |
| AGC032E Modulo Pairing |
3258 |
考试题，人类智慧，调整法，左右两部分调整为不交最优 |
10-19 8 |
| AGC032D Rotation Sort |
2462 |
线段树优化 DP |
10-19 10 |
| P8590 『JROI-8』这是新历的朝阳，也是旧历的残阳 |
1431/中位绿 |
组合，前缀和，双指针 |
10-19 14 |
| ABC376E Max × Sum |
1063 |
贪心 |
10-21 15 |
| ABC376D Cycle |
743 |
BFS |
10-21 16 |
| ABC373G No Cross Matching |
2377 |
调整法，二分图匹配，将平面内两线段调整为无交总长会减小 |
10-21 20 |
| ARC061F 3人でカードゲーム |
2171 |
xyd讲课题，组合 |
10-22 9 |
| P4568 [JLOI2011] 飞行路线 |
上位绿 |
分层图最短路板 |
10-22 20 |
| P2939 [USACO09FEB] Revamping Trails G |
上位绿 |
分层图最短路板 |
10-22 20 |
| P4822 [BJWC2012] 冻结 |
下位蓝 |
分层图最短路板 |
10-22 21 |
| P1948 [USACO08JAN] Telephone Lines S |
中下位蓝 |
分层图最短路或二分+最短路 |
10-22 21 |
| P1989 无向图三元环计数 |
蓝 |
板子 |
10-22 22 |
| P9753 [CSP-S 2023] 消消乐 |
上位蓝 |
哈希+CDQ分治，以 mid 为界记录前后缀哈希值 |
10-23 21 |
| P8819 [CSP-S 2022] 星战 |
中位紫 |
度数哈希，出度全为 1 是可以到达一个环的充分条件 |
10-24 9 |
| P4630 [APIO2018] 铁人两项 |
中位紫 |
圆方树+DP |
10-24 22 |
| 各种板子 |
/ |
板子大赛 |
10-25 |
| P1723 高手过愚人节 |
中位蓝 |
manacher 板子，于是我用哈希过了 |
10-25 17 |
| P1377 [TJOI2011] 树的序 |
中位蓝 |
笛卡尔树板子。笛卡尔树，一种 \(O(n)\) 的离线建立平衡树的数据结构，Treap 属于一种笛卡尔树 |
10-25 20 |
| P3793 由乃救爷爷 |
上位蓝 |
笛卡尔树板子，但是没调出来。离线，由于期望（均摊）最大值出现位置是 \(\log n\) 的 |
10-25 21 |
| P11233 [CSP-S 2024] 染色（民间数据） |
中下位蓝 |
DP |
CSP-S2024 |
| P7981 [JRKSJ R3] system |
1631/中位蓝 |
基环树上倍增 |
10-28 16 |
| P7668 [JOI2018] Dango Maker |
中位蓝 |
考试题，DP，BFS不知道为什么假了，xyd数据不行 |
10-28 21 |
| ABC375G Road Blocked 2 |
2014 |
lca + dij + sgt，调麻了，建最短路树时没发现树不同构调了几天 |
10-29 8 |
| ABC377G Edit to Match |
1782 |
Trie 树上简单 DP |
10-30 8 |
| ABC377F Avoid Queen Attack |
2232 |
暴力 + 容斥 |
10-30 8 |
| P4551 最长异或路径 |
上位绿 |
Trie 树维护前缀异或和。Trie 以 \(O(n\log n)\) 空间和极小的常数，很容易被卡空间 |
10-30 10 |
| ABC371G Lexicographically Smallest Permutation |
2348 |
exCRT，出题人没树脂用 py 算高精。其实贪心就行 |
10-31 14 |
| ABC369G As far as possible |
2055 |
长剖板子 |
11-01 11 |
| ARC183C Not Argmax |
2018 |
DP，扩展状态法，组合 |
11-01 18 |
| P6018 [Ynoi2010] Fusion tree |
中位紫 |
01 Trie。trick：只维护儿子的信息，暴力修改父亲 |
11-01 21 |
| P6623 [省选联考 2020 A 卷] 树 |
中位紫 |
01 Trie 合并。注意树高。 |
11-02 14 |
学习笔记
字典树
MST
连通性相关
环计数
考试
test20241014
test20241017
test20241018
标签：总结,
10,
21,
22,
中位,
中下,
板子,
DP
From： https://www.cnblogs.com/DEV3937/p/18522176