九省联考 2018 切题记录

九省联考 2018 切题（被题虐）记录。

（为什么现在我写代码要写这么长。。。）

（自闭大赛）

（继续懒得抄题）

一双木棋

直接暴力，略。

IIIDX

LOJ / luogu

如果权值互不相同，那么可以直接按照 DFS 序贪心（60 pts）。但是对于有权值相同情况，有可能出现更优解（因为它在多出来的相同权值中还可以塞子树）。

容易想到逐位确定 + 二分。关键在如何 check。

最简单的实现是对于每个数 $x$，计算 $\ge x$ 的数的数量 减去 权值 $\ge x$ 的子树的 size 和。然后一个点最多能放的数就是它的前缀 $\min$。线段树 + 二分。

实现时注意在求一个结点的答案时，将其父亲结点子树的贡献去掉，只留父节点本身的贡献。

然后我在写的时候写复杂了，多维护了个东西，然后就调自闭了。code

秘密袭击

LOJ / luogu

猫锟又一道被乱搞艹爆的题。

容易想到 $O(n^3)$ 解法：求出以每个结点为第 $k$ 大的连通块个数，以这个点为根背包合并即可。可以优化到 $O(n(n - k)k)$（前 $k - 1$ 大的数不产生贡献，背包只枚到 $k$），然后就过了。。。

首先把每个点 DFS 一遍变成固定根 DFS：将贡献数组差分，然后对于每个 $i$，需要计算的就是有至少 $k$ 个权值大于 $i$ 的连通块数量。

将背包看成多项式 $F_{w, i}$，表示 $i$ 子树中经过 $i$ 点，且 $x ^ j$ 前系数表示权值 $\ge w$ 的点有 $j$ 个连通块数量，转移可以表示为 $F_{w, u} = \prod_{v \in \text{son(u)}} (F_{w, v} + 1) \cdot x ^ {[val_u \ge w]}$。总答案为 $\sum_{i} F_{w, i}$。

回忆猫锟的 WC 课件，发现有个叫【整体DP】的 trick 中有一页的内容和以上的内容很像~~，而且讲得很抽象，一脸不想让人看懂的模样~~。所以我们可以用线段树对所有 $w$ 维护 $F_{w, u}$ 和 $Ans_{w}$，支持区间乘 $x$ ，区间加 $1$， $Ans_{w}$ += $F_{w, u}$，以及线段树合并。

最后一个问题是这道题的模数不是 $998244353$，没法 NTT。但是我们可以任意选择 $n + 1$ 个点值，求出答案，并将不同的 $w$ 按照贡献合并，最后做一次 $O(n^2)$ 的拉格朗日插值变回系数表达。

另外，含有 lazy_tag 的线段树合并时为了避免 pushdown 时新增结点破坏复杂度，所以要在其中一个结点没有子节点的时候就直接合并。

我因为把所有的点值全部丢进线段树里，然后就变得巨难写~~，代码长度也遥遥领先~~。code

劈配

按题意建模，略。

林克卡特树

LOJ / luogu

首先 Link/Cut 操作可以认为是选 $k + 1$ 个点不相交的链，最大化总长度。

考虑一个暴力：$F_{i, j, 0/1/2}$ 表示在 $i$ 子树，进行了 $j$ 次切割，存在 $0/1/2$ 个连向儿子的边。然后暴力转移，转移的细节较为繁琐。

最后把第二位搞掉，猜想它可以凸优化（感觉比较直观，但不会证）。

DP 的转移调了比较久，用不相交的链的思想写转移，但是这样会多减掉一次 Link/Cut 的代价，需要加上。code

制胡窜

LOJ / luogu

一道 SAM 好码农题。

首先补集转化（但是要看清题面，总方案数只有 $\frac{(n - 1)(n - 2)}{2}$ 种），接着我们考虑只有一组询问时候的求法。

首先我们找到询问串的位置，接着进行这样的模型转换：将每一个合法位置的串 $S[l:r]$ 看做 $[l, r]$ 的线段。则每一个不合法的数对 $(i, j)$ 可以认为是在 $[i, i + 1]$ 和 $[j - 1, j]$ 的位置上各“切一刀”，每条线段至少被切一次。

统计这样的切法有多少次。

分成两种情况，一种情况是所有线段之间都有交。另一种情况则是交集为空。两种情况的求法类似，都是将左右端点看做关键点，枚举 $i$ 所在区间，求出 $j$ 所在区间大小，然后合并式子。

然后剩下的部分就是数据结构了，需要数据结构维护 $\text{right}$ 集以及推式子中需要的一些求和项，然后完成树上合并即可。

我的合并用 DSU on tree 实现的，实际效果和一个 $\log$ 的线段树合并差不多。code