本 $\texttt{LIST}$ 用于记录联赛经典题。

不过应该会咕得比较厉害

[CSP-S 2019]树的重心

给一棵树,令 $p_i$ 为删去树上一条边后,$i$ 是分裂出两棵树中某一棵的重心的次数。求 $\sum_{i=1}^n i \times p_i$。

$n \le 3 \times 10^5$

首先拿出一个原树重心做根,令一个非根的点 $x$ 子树大小为 $siz_x$,重儿子的 $siz$ 为 $maxson_x$。若要使 $x$ 是某一棵分裂出的树的重心,另一棵的大小为 $S$,那么有:

$$maxson_x \times 2 \le n - S$$

$$(n - S - siz_x) \times 2 \le n - S$$

化简得:

$$n - siz_x \times 2 \le S \le n - maxson_x \times 2$$

并且显然这条删去的边不能在 $x$ 的子树中(若在子树内,不可能使重心移动至 $x$)。

所以可以 $\texttt{DFS}$,树状数组维护每个大小的 $siz$ 的出现次数,查询区间和。对于在 $x$ 内部的边产生的贡献,可以再开一个树状数组,跟着 $\texttt{DFS}$ 的过程加入值,然后记录遍历 $x$ 的子树前后的值,作差即可。

再考虑 $rt$ 的贡献,令 $u,v$ 为 $siz$ 前二大的子树。如果删去的边在 $u$ 的子树,则 $2 \times siz_v \le n - S$,否则 $2 \times siz_u \le n - S$。这个也可以在 $\texttt{DFS}$ 的过程中维护。


[NOIP 2018]保卫王国

给定一棵树,点带权,每次强制两个点选或不选,询问独立,求树的最小权覆盖集。
$ n \le 10^5,m \le 10^5$

首先考虑不带修改的做法,定义 $dp[x][0/1]$ 为 $x$ 这个点选或不选,$x$ 及其子树的最小权值。有:

$$dp[x][0] = \sum_{y \in son(x)} dp[y][0]$$

$$dp[x][1] = w[x] + \sum_{y \in son(x)} \min(dp[y][0],dp[y][1])$$

很显然

现在考虑如何进行修改。

发现如果修改点 $\texttt{a,b}$,那么除了 $\texttt{LCA(a,b)}$ 及其祖先之外,每个点最多只有一个后代被修改,因此修改的 $\texttt{dp}$ 值形如两条链。

考虑把转移写成矩阵的形式,设 $f[x][0/1]$ 为 $x$ 的父亲的 $\texttt{dp}$ 值减去 $x$ 的贡献后的值。有:

$$f[x][0] = dp[fa[x]][0] - dp[x][1]$$

$$f[x][1] = dp[fa[x]][1] - \min(dp[x][0],dp[x][1])$$

那么从一个点 $x$ 的 $\texttt{dp}$ 转移到其父亲 $fa[x]$,有:

$$dp[fa[x]][0] = f[x][0] + dp[x][1]$$

$$dp[fa[x]][1] = f[x][1] + \min(dp[x][0],dp[x][1])$$

实际上就是把上面两个方程移了下项。

如果把乘法定义为:

$$c_{i,j} = \min\{a_{i,k}+b_{k,j}\}$$

那么方程写成矩阵乘法的形式就是:

$$\begin{pmatrix} dp[fa[x]][0] & dp[fa[x]][1] \end{pmatrix} = \begin{pmatrix} dp[x][0] & dp[x][1] \end{pmatrix} \times \begin{pmatrix} +\infty & f[x][1] \\ f[x][0] & f[x][1] \end{pmatrix}$$

这个东西满足结合律,所以我们可以直接定义一个倍增矩阵数组:$g[x][i]$ 为 $x$ 的 $\texttt{dp}$ 值向上跳 $2^i$ 步中途乘的矩阵的积。这样就可以在 $\log$ 的时间内通过一个点的 $\texttt{dp}$ 值得到整棵树的了。

现在考虑修改,也就是把修改的点上不满足条件的(强制放或不放)那一项 $\texttt{dp}$ 改成 $+\infty$,然后再倍增向上跳即可。需要特殊注意两个点合并时的情况。

具体来说,若两点是祖先关系,那么可以跳到同一点后将两者中祖先的限制加入后代的 $\texttt{dp}$ 矩阵中,然后继续向上跳到根节点。否则,在 $\texttt{LCA}$ 处会出现一个节点的两个儿子同时被修改,特殊判断一下,修改转移矩阵即可,然后再继续跳到根节点。

复杂度 $O(n\log n+m\log n)$


[CSP-S 2019]树上的数

咕咕咕


[CSP-S 2020]贪吃蛇

考虑如果一条蛇选择结束,需要满足什么条件。

如果他吃掉最后一名之后,没有变成最后一名,那么他一定选择吃。称这样是必吃状态。

由于整个序列是递增的,如果他吃了最后一名而没有掉到最后一名,会使得序列的 $\min$ 增大,$\max$ 减小。那么新的第一名如果选择吃,那一定会落到原先第一名更后面。

那就让新的第一名去选择是否结束,反正我吃了不会比他先死。

如果他吃掉最后一名之后,变成了最后一名,那么找到距离他最近的必吃状态,我吃不吃只和与这个必吃状态的 距离 的 奇偶性 相关。

设我在 $p$,最近的必吃状态位置是 $s$。

首先显然的是 $s$ 处必定会吃,那考虑 $s$ 到 $p$ 之间的蛇,他们一定不是必吃状态,那一定有:这些蛇选择吃之后的新状态的体力值单调。

也就是说,如果 $s$ 吃,他一定吃的是 $s+1$。$s+1$ 知道自己会被吃,那么他就选择不吃最小的;$s+1$ 不吃,就会选择结束,那么 $s+2$ 就知道自己就算变成最后,也不会死,那么他一定选择吃......

也就是,如果 $p-s$ 是奇数,他就会结束游戏,否则一定会吃掉最小的,而接下来新的第一名就一定会直接结束游戏。

然后拿队列模拟一下,和 $\text{NOIP2016}$ 蚯蚓一样维护一个双端队列,每次从原队列和新队列取 $\max$ 和 $\min$ 更新即可。

只要遇上一个非必吃状态,就 $\mathcal{O(n)}$ 模拟找到下一个必吃状态,返回答案即可。

时间复杂度 $\mathcal{O}(n)$。

标签: dp, 数学, 贪心, 树状数组, 动态dp, 矩阵, 博弈论

已有 4 条评论

  1. 太强了!!

  2. chaos chaos

    太强了!!

  3. %%%@(吐舌)

  4. bigmurmur bigmurmur

    %%%@(吐舌)

添加新评论