九省联考2018 乱写

传送门

按题解篇幅看就知道「秘密袭击」是「切树游戏」那样的神套路题了吧。（不过「切树游戏」毒瘤多了-_-||

$一双木棋$

有「$pos_i \leq pos_{i - 1}$」的限制，直接状压轮廓状态数就是 $\binom{n + m - 1}{m - 1}$，不到 $10^5$。搜索解决 min-max 博弈。

$Code$

$IIIDX$

我太菜了！直接贪心在 $d$ 有重复的时候是错的，比如 $n = 4$, $k = 2.0$, $1$ $1$ $1$ $2$ 和 $1$ $1$ $2$ $1$。

正解挺灵活的。建树，把 $d$ 从大到小排序。对每个权值维护一个 $c_i$ 表示别的节点至多能在 $i$ 左边拿走几个。我们知道把 $i$ 填到 $x$ 点就要在 $i$ 左边预留出 $size[x]$ 个空位放到 $x$ 的子树里，但是不能确定是哪些个空位因为会影响后面的判定。这时要把 $[i, n]$ 的 $c$ 减去 $size[x]$。

$c$ 实际上是用来限制同层的，所以往下走到儿子时，要把父亲给它预留的位置释放掉。

$Code$

$秘密袭击$

求树的每个连通块第 $K$ 大权值之和。类似整数概率公式一样的拆分权值：

其中 $cnt(S, i)$ 表示连通块 $S$ 中权值 $\geq i$ 的点数。

问题转化为：枚举权值 $v$，统计 $\geq v$ 的权值出现次数 $\geq K$ 的连通块个数。

这似乎可以 dp？！$f_{i, j, k}$ 表示以 $i$ 为最浅点，权值 $\geq j$ 的出现次数为 $k$ 的连通块数。有：$f_{i, j, k} = \prod\limits_{v \in Son(i)} f_{v, j, k’}(\sum k’ = k - (val_i \geq j))$。答案就是 $\sum\limits_{k = K}^n \sum\limits_{i = 1}^n \sum\limits_{j = 1}^W f_{i, j, k}$。令 $g_{i, j, k} = \sum\limits_{x \in subtree(i)} f_{x, j, k}$，我们求的实际上是 $\sum\limits_{k = K}^n \sum\limits_{i = 1}^W g_{1, i, k}$

（据说 $O(n^2K)$ 能过，但来都来了是吧）

上面那个背包长得一脸生成函数，那就如它所愿：令 $F_{i, j} = \sum\limits_{k = 0}^n f_{i, j, k} z^k$，$G_{i, j} = \sum\limits_{x \in subtree(i)} F_{x, j}$。有 $F_{i, j} = (val_i \geq j ? z : 1) \prod (F_{son_i, j} + 1)$, $G_{i, j} = F_{i, j} + \sum G_{son_i, j}$

带 $n + 1$ 个点值 $z$ 进去，让 $F$ 和 $G$ 是点值状态，转移就是对应位相乘，最后再拉格朗日插值还原系数得到 $g$。

对应位相乘？那就用整体 dp 的思想在每个点上维护一棵线段树，线段树每个节点上有个形式幂级数。考虑我们要干什么，区间乘 $z$，全局 $+1$，对应位置相乘，维护全局答案。

  • 初始化，$(F, G) = (1, 0)$
  • 如果 $val_i \geq j$ 那么 $(F, G) \rightarrow (F * z, G)$
  • 合并，$(F, G) \rightarrow (F(1 + F_v), G + G_v)$
  • $(F, G) \rightarrow (F, G + F)$

非常繁琐，我们用矩阵来转移。但是矩阵常数大跑不过暴力，考虑函数复合维护 tag（这一步过于神奇）：观察到 $F$ 只会变成 $aF + b$, $G$ 只会变成 $G + cF + d$，于是每个节点维护一个四元组 $(a, b, c, d)$ 表示 $(aF + b, cF + d + G)$。合并 tag 就是 $(a, b, c, d)$ 和 $(A, B, C, D)$ 相乘，得到 $(Aa, Ab + B, Ca + c, Cb + D + d)$。单位元是 $(1, 0, 0, 0)$。

hint：要写垃圾回收和 unsigned int。

复杂度 $O(n^2logW)$。

感想：整体 dp 好神啊！整体 dp 套生成函数好神啊！

$Code$

$劈配$

回忆起被「皮配」支配的恐惧 /jk 还好这道比较阳间，一道复杂度分析题

第一问写一个“扩展”的二分图最大匹配就好了，具体来说每个后期被更改匹配导师的人新匹配的导师必须是同一志愿的，$O(n^3C)$

第二问有显然的二分性，你可以二分 + 从前往后加人，但是这样是 $O(n^3Clogn)$。我们可以保留前缀不变的匹配状态，就是 $O(n^2Clogn)$ 的样子。

但是有完全更简单的做法：在做第一问要替换人的时候尽量替换靠后的，顺便记录下来就可以了。

$Code$

$林克卡特树$

题意：让你选 $K + 1$ 条路径使得权值和最大。

带权二分，$f[i, 0/1/2]$ 表示点 $i$ 的度数为 $j$ 时 $i$ 子树中的最优解（要记录路径数，写个 struct 就好了），分类讨论。

$Code$

$制胡窜$

大分类讨论题吗。。。有心情再写吧 /cy 被「秘密袭击」搞自闭了

upd: 我来口胡了

显然不能每个串都被那两刀切到。考虑容斥，求每个串至少被切到一次的方案数。有下面几种情况：

  1. 第一刀啥都没切到，第二刀切完
  2. 第二刀啥都没切到，第一刀切完
  3. 第一刀切到但没切完，补第二刀切完
  4. 第一刀切完，第二刀随便切

$1$、$2$、$3$ 不能一刀切完时答案是 $0$，否则算一下。

$4$ 麻烦一点，第二刀切的位置是一个区间，可以二分出左右端点。答案是个取 $\min$ 形式的，二分出开始取后面的时候。柿子存在平方形式，所以线段树维护区间 $0$、$1$、$2$ 次方和。