CSP2021
A 廊桥分配
考场上做出来了。比较简单，但是考场上脑抽了好久。
用一个 set 增量维护第 \(i\) 个飞机来后要全部填满的廊桥数，然后随便统计一下即可。
B 括号序列
我设计了一个比较复杂的状态，但是实际上感觉很清晰。\(f(i,j,0/1/2/3/4)\) 代表 \([i,j]\) 区间样式分别为 *...*，*...*A，A*...*，(...) 和 A 的一个字符串（*...* 代表一段 *，... 代表一段任意字符串但是满足内部括号匹配，A 是一个合法串）。
C 回文
实际上挺简单的。考虑你提取出第一个字符（两种情况，头或者尾）后序列分成两端，于是就可以把这两段用两个双端队列维护，每次贪心考虑取头还是取尾。
D 交通规划
待补。
BJOI2015 树的同构
树哈希板子题。随便设一个哈希：子节点有序的情况下的有根树的一个子树的哈希为（设 \(sz_u\) 为目前的一个前缀 \(sz_v\) 的和）
\[h(u)=B\times d(u)+\sum_v h(v)\times B^{sz_u} \]对于处理有序问题，考虑给子节点按照哈希值排序即可；对于根的问题，取重心即可（两个话就都求一下）。
https://hydro.ac/d/bzoj/record/617caee363b6465eb4e5811b
BJOI2015 糖果
答案为
\[\binom{m+k-1}{m}^{\underline{n}} \]那如何计算组合数膜合数呢？
\[\binom{m+k-1}{m} = \frac{1}{m!} \prod_{i=1}^{m} (m+k-i) \]处理一下 \(m!\) 的分解质因数。没了。
AtCoder DP 题选做
Z - Frog3
给定一个序列 \(h\)，从 \(i\) 跳到 \(j\) 的代价为 \(C+(h_j-h_i)^2\)。求 \(1\) 到 \(n\) 的最小代价。
\(f_i\) 表示到 \(i\) 的最小代价，则有
\[f_i=C+\min_{j<i} f_j+(h_i-h_j)^2\\ f_i=C+h_i^2+\min_{j<i} (f_j+h_j^2)-2h_ih_j\\ \]转移即用 \(2h_i\) 的线去切由 \((h_j,f_j+h_j^2)\) 组成的下凸壳。一开始并没有看到 h 已经排序，还写了一半 cdq，然而单调队列即可。
https://atcoder.jp/contests/dp/submissions/27010220
Y - Grid2
经典容斥题。
把障碍点和终点都设为关键点。把所有关键点按照拓扑序排序（此题就是按 \(x\) 排序）。设 \(f(i,j)\) 表示从第 \(i\) 个关键点到第 \(j\) 个关键点的不考虑阻碍的方案数，易知 \(f_{i,j}=\binom{x_j+y_j-x_i-x_i}{x_j-x_i}\)。考虑设 \(g_i\) 表示从初始节点到第 \(i\) 个关键点，除去这个关键点其他障碍全部没有经过的方案数，则有 \(g_i=\binom{x_i+y_i-2}{x_i-1}-\sum_{j<i} g_jf_{j,i}\)。
X - Tower
肯定要先贪心一下。可以推出按照 \(s+w\) 排序最优（考虑对于相邻两个放哪个更优）。
然后背包一下就可以啦。
A2OJ Ladder 题板刷
\(\color{blue}{蓝色}\) 自己攻克了的的简单题；\(\color{green}{绿色}\) 自己攻克了的稍复杂题；\(\color{pink}{粉色}\) 自己没攻克的简单题；\(\color{purple}{紫色}\) 自己没攻克的复杂题。
\(\color{pink}{\text{CF248D}}\)
给定一个一维地图，\(H\) 表示一户人家（遇到可以送糖果或者不送），\(S\) 表示一个糖果（遇到可以捡起或者不捡），\(.\) 表示空地，走过一格需要一单位时间。问从第一格左边开始，最少提前准备多少糖果才能在 \(t\) 时间内给每户人家都有一份糖果。
先上 binary search。
Observation：糖一定捡，并且一定送。
但是我一开始想的直接来回是错的。因为还有一种情况，拿到糖先回去送人然后再往后走。
这种情况可以这样理解：我先把糖欠着，然后一旦糖够了立马还回来。可以发现这样的决策在决定走 S 形（去+回+去）的方法上是最优的。
当然你也可以不还。但实际上，一旦你在第 \(i\) 户做出决定要全部赖账然后跑回来再还，那你就在之后不可能再做上述决定了。所以我们在按上述决策跑的同时，每一步都看一下，如果剩下的要跑过去然后跑回来要花多少时间。每次最远到达的那个点必然是固定的，所以求出来后直接做就好了。
https://codeforces.com/contest/248/submission/134194983
\(\color{blue}{CF237D}\)
这题属于是把做法写脸上了。给每条边分配一个集合，集合内就边的两个端点，然后用类似兄弟儿子的东西连边即可。
https://codeforces.com/contest/237/submission/134198693
\(\color{blue}{CF209C}\)
考虑处理每个连通块。忽略那些孤点无边连通块。如果连通块中存在奇点，则留两个奇点可以向外面连，其他奇点就随便和连通块内点自我消化。这样我们就得到了 \(k\) 个连通块，希望把这 \(k\) 个连通块连起来使得每个连通块度数都为 \(2\)。连一个环即可。
哦还有 1 一定要脸上就算 1 是孤立的。
https://codeforces.com/contest/209/submission/134201806
\(\color{pink}{CF144E}\)
只要配上那必然能够形成不相交路径。然后就是一个贪心的区间匹配问题了。
对于如何处理区间匹配，我们考虑对于每一个位置维护所有覆盖它的区间，以右端点为关键字塞入堆中，然后每次选择右端点最小的区间即可。