A
一个圆上有 \(2n\) 个点，你需要选出 \(n\) 个点对连一条线段，其中一些点对已经被选。
问所有点对方案中，联通块个数的和，联通的含义是线段相交，那么两条线段的端点都互相可达。
\(n\le 300\)。
线段相交，把圆放到序列上就是区间相交然而不包含。
我们拆贡献，计算每个区间 \([l,r]\) 的贡献，那么 \([l,r]\) 是极大的，其中的点不能往外连边。
我们可以计算这里的方案数，若 \([l,r]\) 未匹配的有 \(s\) 个。
只有 \(s\) 为偶数才有贡献，贡献是 \(g(s)=1\times 3\times ...\times (s-1)\).
然而有个问题，就是 \(l,r\) 可能不连通，我们要容斥掉这部分，设 \([l,r]\) 的贡献是 \(f_{l,r}\)，
则 \(f_{l,r}=g(l,r)-\sum_{k=l+1}^r f_{l,k}\times g(k+1,r)\).
B
有向图，找一条 \(1\) 出发，回到 \(1\) 的最小环。\(n\le 1e4,m\le 2e5\)。
只需要正反图跑两遍，记录每个点的 \(dis\)，和 \(fr\) 表示这条路的第一个路径。
枚举每个边 \((u,v,w)\)，若 \(fr_u\neq fr_v\)，那么贡献为 \(dis1_u+dis2_v+w\)。
C
有 \(n\le 2000\) 个椰子，给定权值 \(a_i\)，你如果对椰子操作 \(a_i\) 次就可以打开它。
真实的 \(a_i\) 被随机打乱。所以你不知道每个椰子对应哪个权值。
制定一种策略。求要获得 \(m\) 个椰子最坏情况下最少多少次操作。
将 \(a_i\) 从小到大排序，设 \(f_{i,j}\) 表示仅考虑前 \(i\) 个椰子，已经获得 \(j\) 个椰子的最小代价。
有两种转移，第一种是获得 \(i\) 这个椰子，那么 \(f_{i,j}=f_{i-1,j-1}+a_i\).
第二种是不获得椰子，但是由于之前获得椰子的时候可能导致这个椰子也被操作，考虑最坏的情况。
所以 \(f_{i,j}=\min(f_{k,j}+a_k\cdot(i-k))\).
直接套斜率优化即可。单调栈。