whk 自闭，尤其是英语和化学。
会按自己的感觉，按照 NOIP2020 难度打分。
一.gym100212I(T2)
题意：给你一个二分图，你要保留一些边使得每个点度数 \(\geq 2\) ，要让保留的边最少。
\(n,m\le 300\) 。（两边的点数）
做法：直接建图，跑上下界最小流。但是更聪明的做法是倒着思考，当成先把所有边加上，再删边，就是普通的最大流了。
二. AGC029F(T3.5)
题意：给你 \(n-1\) 个集合，在每个集合里选两个数 \(u,v\) ，在一个图里连边 \((u,v)\) ，要使得最后成为一棵树。
\(n\le 10^5\) ，\(\sum |S|\le 2*10^5\)
做法：11月杂题的四。原来自己能独立想出来一个 AGC F！
三. ARC149D(T2.5)
题意：你一开始有一个数 \(x\) ，有 \(m\) 个操作， 第 \(i\) 次是这样的：如果 \(x>0\) 则 \(x:=x-a_i\) ，若 \(x<0\) 则 \(x:=x+a_i\) 。当 \(x=0\) 时停止操作。
给出 \(n\) 个 \(x\) 的初始值 \(x_i\)，如果 \(x\) 会变成 \(0\), 输出变成 \(0\) 是操作了多少次；否则输出 \(x\) 最后等于多少。
\(0<n,m,|x_i|,a_i\le 10^6\)
做法：这个操作有强烈的对称性。知道了 \(x\) 的答案就能知道 \(-x\) 的答案。
所以我们一直压缩状态，把这种传递关系建出一棵树。
四. CF757F(T3)
题意：无向图，边正权。有一点 \(s\) ，你要选择一个点 \(u(u!=s)\) ，使得删掉点 \(u\) 后有尽量多的点到 \(s\) 的最短距离改变。输出这个最多的点的个数。
\(n\le 2*10^5,m\le 3*10^5\)
做法：先跑一遍最短路，保留 \(dis[u]+w=dis[v]\) 的边。发现形成了一个 DAG 。
问题转化成在 DAG 删一个点，使得 \(s\) 不能到达的点最多。可以直接上 [模板]支配树。但是我不会（后面再学）。
很神的是，考虑入度为 \(1\) 且入它的点 \(v\) 不等于 \(s\) 的一个点 \(u\) 。显然我们不会选 \(u\) ，可以把 \(u\) 缩到 \(v\) 里。
缩完之后，删掉任何一个点，剩下的点都能被 \(s\) 到达。就输出缩得的最大点集即可。
(草有照着打别人题解的感觉)
五.AGC005F(T2)
题意：给定一棵无根树，定义 \(f(i)\) 为对于所有大小为 \(i\) 的点集，能够包含它的最小连通块大小之和。对于所有 \(1\le i\le n\)，求出 \(f(i)\)。
\(n\le 2*10^5\)，模数是 NTT 模数。
做法：考虑每一个点 \(u\)，有多少个点集构成的最小联通块包含它，容斥一下即可。
最后就能把答案整理成：\(f_i=\sum\limits_{j=0}^n \tbinom{j}{i}b_j\) 。差卷积。
六.AGC002F(T2)
题意： \(n\) 种颜色，每种颜色有 \(k\) 个球。你要把球排成一列，然后把每种颜色的第一个球染白。
问能得到的不同颜色序列个数。\(n,k\le 2000\)
做法：把 \(n\) 个白球和每种颜色的第二个球拿来当状态 dp 即可，因为由此可以顺势求出剩下的平凡球的填的方案。
七.ARC076F(T2.5)
题意： \(n\) 个人， \(m\) 把椅子。每个人都有自己的想法：想坐编号 \(\le l_i\) 或编号 \(\geq r_i\) 的。你可以添加一些"公共椅"，大家都喜欢做“公共椅”。
问最少要添几把，能使所有人都坐上椅子。
做法：考虑霍尔定理。经过一定推导，\(val(i,j)=i+(m-j+1)-\sum [l_k\le i\land j\le r_k]\) 。求出 \(val(i,j)\) 最小值即可。用线段树维护。
注意答案对 \(n-m\) 取 max。
八.AGC024F(T3.5)
题意（转化后）：给你一些 \(01\) 串（长度 \(\le N\)） 。你要对于每一个长度 \(\le N\) 的 \(01\) 串 \(T\) 求出：给出的串里有多少个满足存在一子序列等于 \(T\) 。
\(N\le 20\) 。
做法：ex子序列自动机（bushi）好神啊反正。
考虑 \(S\) 匹配 \(T\) 的过程，一定是贪心的，走法是唯一的。
我们把 \(T\) 和 \(S\) 还未参与匹配的后缀一起记下来，建成一个点岂不美哉。
然后就走出来了一条确定的路径，途径了一些确定的点。这里点数是 \(O(2^nn)\) 的，边数同阶。
这个就是自动机了，我们把它建出来跑拓扑排序 dp 就好了。
标签：10,le,一个点,题意,记录,sum,12,做题,做法 From： https://www.cnblogs.com/cwhfy/p/16961566.html