简述
我贪心太菜了，所以来总结几种模型，以防赛场 GG。
「杂题集」- 2019年10月1日
方程式
这个搜索好骚啊。
首先直接枚举 20 个数来搞初始根。假设我们拿到了\(s\)个根，那么我们还剩下\(n – s\)个，肯定是重根。所以我们考虑直接搜索剩下的\(n – s\)到底是哪个重根。这个复杂度就是\(\Theta(s^{n – s})\)。至于我们怎么验证解的正确性，就是这道题的精髓了：考虑把这组解写成零点式：
\[ \prod_{i = 1}^n (x – a_i) = 0 \]
我们做一个小的多项式乘法展开这个积式，然后与原式的系数进行对比即可。
「杂题集」- 2019年9月25日
[POI2008]BLO
一眼可以了解到是一道割点题。对于不是割点的情况，那么被计算的点对一定包含此点本身，又因为有序，所以贡献就是\(2(n – 1)\)。如果是割点的话，就比较麻烦，分下面几个来算：
- 此点延伸出去的点对。
- 连通块之间的点对。
- 本身就无法互通的点对。
第一个很好算，是\(2(n – 1)\)。第二个，在 Tarjan 枚举搜索子树的时候计算子树大小和全图补集的乘积（注意，这里会多计算一遍与点\(u\)的点对，所以我们第一个改成算\(n – 1\)）；第三个，算「当前整颗搜索树与图的补集大小」与「搜索树的大小」的乘积。
综合起来就是，对于点\(u\)：
\[ ans_u = \sum_{k \in son(u)} (n – size(k)) \times size(k) + (n – 1) + (n – 1 – \sum_{k \in son(u)} size(k)) \times (1 + \sum_{k \in son(u)} size(k)) \]
「杂题集」- 2019年9月21日
kal0rona 越来越 sb了。
「POI2007」BIU-Offices 题解
主要思路
正好在《组合数学》上看过一个结论：反图形成的连通块的点在原图一定处处连通。证明很简单：考虑点对\((u, v)\)，如果点对之间在反图中不连通显然是在原图联通的；如果在反图中连通，有一个不在当前点集的点使得他们连通。所以，我们只需要构建反图，根据「不与本点相连的点都在本连通块内」进行 BFS 即可。
「杂题集」- 2019年9月19日
方格取数
看一眼复杂度，\(O(nm)\)级别的，考虑两个循环的 DP。分析整个题面之后发现，我们穿过边界时，当且仅当另一个连通块的权值比当前的大，否则便不会为了穿过边界而损失当前金块。所以，我们做一个 DP 一样的东西：因为发现每个格子只能走一遍，那么在每一列你只能选择一直向上走和一直向下走，所以这个 DP 便没了后效性，然后再处理连通块之间的连接判断就做完了。