联赛真题 LIST

Posted on Edited on In

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

不过应该会咕得比较厉害

[CSP-S\ 2019]树的重心

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

n≤3×105n \le 3 \times 10^5

首先拿出一个原树重心做根，令一个非根的点 xx 子树大小为 sizxsiz_x，重儿子的 sizsiz 为 maxsonxmaxson_x。若要使 xx 是某一棵分裂出的树的重心，另一棵的大小为 SS，那么有：

maxsonx×2≤n−Smaxson_x \times 2 \le n - S

(n−S−sizx)×2≤n−S(n - S - siz_x) \times 2 \le n - S

化简得：

n−sizx×2≤S≤n−maxsonx×2n - siz_x \times 2 \le S \le n - maxson_x \times 2

并且显然这条删去的边不能在 xx 的子树中（若在子树内，不可能使重心移动至 xx）。

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

再考虑 rtrt 的贡献，令 u,vu,v 为 sizsiz 前二大的子树。如果删去的边在 uu 的子树，则 2×sizv≤n−S2 \times siz_v \le n - S，否则 2×sizu≤n−S2 \times siz_u \le n - S。这个也可以在 DFS\texttt{DFS} 的过程中维护。

[NOIP\ 2018]保卫王国

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

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

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

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

很显然

现在考虑如何进行修改。

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

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

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

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

那么从一个点 xx 的 dp\texttt{dp} 转移到其父亲 fa[x]fa[x]，有：

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

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

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

如果把乘法定义为:

ci,j=min⁡{ai,k+bk,j}c_{i,j} = \min\{a_{i,k}+b_{k,j}\}

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

(dp[fa[x]][0]dp[fa[x]][1])=(dp[x][0]dp[x][1])×(+∞f[x][1]f[x][0]f[x][1])\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]g[x][i] 为 xx 的 dp\texttt{dp} 值向上跳 2i2^i 步中途乘的矩阵的积。这样就可以在 log⁡\log 的时间内通过一个点的 dp\texttt{dp} 值得到整棵树的了。

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

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

复杂度 O(nlog⁡n+mlog⁡n)O(n\log n+m\log n)

[CSP-S\ 2019]树上的数

咕咕咕

[CSP-S\ 2020]贪吃蛇

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

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

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

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

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

设我在 pp，最近的必吃状态位置是 ss。

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

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

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

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

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

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