一些 ？
平面图欧拉定理：$|V|−|E|+|F|=2$。
codeforces-2144F
没做出来，题解做法是注意到答案只有 -1，1，2 三种，出现 () 答案就是 -1，剩下的一定能通过 ()()()() 和 (((()))) 两种覆盖，所以只要解决答案为 1。建 ACM dp 即可。
主要是没注意到可以被两种情况覆盖。主要可以从两方面入手：
-
条件很松，所以可以注意到含有
((和))交错构造即可，至于交错的就好想了。 -
如果直接建 ACM 会发现 dp 时需要记录当前满足条件的集合 S，感觉这个是很不优的，所以猜想不用记，只需要判断答案是否能为 1，否则只能为 2。
codeforces-2138D
乍一看感觉简单，对于每个块的每个位置统计方案，取决于最后的操作。分两类，第一类就是最后操作为赋值，只要保证之后不会修改即可，第二类不妨设是取 min，那就是说之前要对于 >=pos 的取 max 或赋值，感觉不会去重，放弃。
题解做法是统计一段位置前缀的方案，做个差分即可。感觉一下就做完了。
daimayuan-CSP-S 模拟赛 Day 16
A
考虑最后两个重心之间的边，要么是新加的，要么是原本的。新加的是好做的。原本的要对子树内或者子树外求 siz 等于某个数时的值，赛时直接拍在 dfn 上离线做，成功被卡空间。
cly 给的做法是把原树上的重心作为根，那么只会有别的子树和到根的路径上可能有答案。直接统计即可。
感觉赛时发现被卡空间时就应该再观察性质，思考如何更好地统计。
B
将中间没有区间端点的位置合并，观察到，某个区间的最小深度即为区间里位置的 log 上取整。考虑怎么统计数量，注意到，答案只和区间端点有关，为倒二层上所有中点的区间端点数。$O(n^3)$ 是好做的。
赛后，题解。$f(l,r)$ 表示区间 $[l,r]$ 的答案，枚举决策点 $k$ 由 $f(l,k),f(k+1,r)$ 即可转移。注意到决策点具有单调性，即 $f(l,r)$ 的决策点 $g(l,r)$ 在 $[g(l,r-1),g(l+1,r)]$ 内。即可 $O(n^2)$。
考虑证明，将刻画倒二层的状态，长度为 $1$ 或 $2$，答案为所有长度为 $2$ 的中点权值和。分深度相同和深度不同两种情况讨论即可。
观察单调性确实困难，但优化 dp 就只有单调性、优化状态、数据结构维护、观察连续性等几种，可以快速尝试。就算没有推理得出也可打表。
C
如果已知 $k$ 个点的划分方案，设 $a_i$ 表示划分后第 $i$ 个连通块的大小。相当于有 $n-k$ 可以任意连的点，$m$ 个之间不能互相连的连通块，用类似 prufer 的方法，每次如下构造：
- 如果连通块个数 >=2，且存在度数为 1 的连通块，删掉编号最小的，把连接的点插入 P 序列
- 否则删掉编号最小的度数为 1 的点，把连接的点插入 Q 序列
最后只剩下一个连通块和一个点。可以发现由 P 和 Q 可以唯一确定一棵满足条件的树。即序列和树构成双射。
序列的个数为 $(n-k)^{m-1}n^{n-k-1}$，每次删掉连通块以及最后连通块的连出去的点的方案是 $\prod a_i$，答案为 $\sum_m (\sum\prod a_i)m(n-k)^{m-1}n^{n-k-1}$。
考虑 $\sum\prod a_i$ 怎么求，设 $f_{i,j}$ 为 $i$ 个连通块，$j$ 个点的值。$O(k^3)$ 转移。
注意到最后要求的是 $n^{n-k-1}\sum_mf_{m,k}m(n-k)^{m-1}$，如果记 $f_k’=\sum_m f_{m,k}(n-k)^m$，发现 $f_k’$ 的转移是乘上某个系数的形式，可以 $O(k^2)$，但要求的是 $g_k’=\sum_m f_{m,k}m(n-k)^m$，转移是乘上系数加上 $f_k’$。
通过这题了解了很多有关生成树计数的方法，如 prufer 和矩阵树定理。同时，最后转移的优化也启示如果别的方面入不了手，不妨从答案形式入手。
D
赛时没有开。赛后补的。
数据范围提示状压。但是感觉根据点状压没有思路，考虑状压边。如果已知边集，即可知道联通状态。依次加入每条边，考虑非树边必须在一些边填了以后才能填。由于正着做为了保证不重，还得维护一维，总的是 $O(n^32^n)$。而反过来做不用，反着做即可。
两个关键点：
- 边状压
- 反着做优化状态
daimayuan-CSP-S 模拟赛 Day 17
A
考虑只要一段长为 3 的区间出现两次的数即为可以覆盖的数。从前往后贪心，每一位要么从后面的任意位覆盖，要么被前一位的值覆盖（从前往后覆盖只能通过前面一个颜色段），从前往后只会修改本身，从后往前直接暴力覆盖，因为之后不会再覆盖这些值，跳过即可。
B
从最终状态入手，令 $f(i,0/1)$ 表示前 $i$ 位，末位为 0/1 的方案数，$f(i,0)=f(i-1,0)+f(i-1,1)$，$f(i,1)=\sum_jf(j-1,0)[[j,i]可以为 1 段]$。判断就预处理即可。
C
01-trie 上贪心，优先选 0，后选 1。这样复杂度会退化。考虑到如果某一个子树都是能选的，即 $[l,r]$ 覆盖这段区间，答案是固定的。预处理即可，至多有 $O(\log n)$ 段这样的区间。
D
- 方案数的平方等价于同时做两遍的方案。（考虑路径和）
- 成行转移复杂度不够时可以考虑轮廓线 dp
AtCoder-arc122_e
核心观察是，从后往前填时，可以填的数不会变少。直接填即可。
判断一个数能不能填有点难想。
AtCoder-abc230_g
学到了，原来 $\sum_i d(i)\times d(p_i)$ 的上界是 $O(n\log^2n)$ 的。容斥后莫反，系数直接暴力枚举因数即可。
luogu-P14193
基环树，考虑 $O(n\log n)$ 求出环上一个点 $x$ 到所有不同种类蘑菇 $k$ 次需要走多少步以及结束位置。考虑指向 $x$ 的点，相当于一种蘑菇只要走 $k-1$ 步，往前跳即可。dfs 解决即可。
Atcoder-abc427_g
考虑长度为 $1$ 的 $P$，初始心情会分为两个区间，一段 $+A$，另一段 $-B$。
考虑归纳，每次在末尾加入一个点 $P_{i+1}$，前面长度为 $i$ 的 $P$ 会有 $i+1$ 个区间，第 $i$ 个区间为 $+iA-(n-i)B$。暴力地，求出每个区间中，最后等于 $P_{i+1}$ 的位置。不难发现最后会有 $i+2$ 个区间。
考虑维护这些区间。
CodeForces-2159D1
很奇妙的一道题。
首先观察到，只有后缀 min 才有用，其他删掉不改变答案。考虑最终答案区间的右端点如果没有在后缀 min 上，那么将右端点移到后面第一个后缀 min 是不劣的。此时右端点都在后缀 min 上，考虑左端点只对最小值有贡献，而由于右端点在后缀 min 上，最小值只可能也是后缀 min。
问题转化为一个上升的序列，划分，每段贡献为 $\lceil \frac{a_r}{a_l}\rceil$。对于这个问题，考虑每段贡献一定是 $\le 3$ 的，因为 $>3$ 时，每段可以递归地拆出 $2$，是等价的。
在一般的优化方法不起作用时，可以尝试根据题目性质，推出一些结论。