20210916 2j0s1yydnnoat 模拟赛官方题解

博主： tony102
发布时间：2021 年 09 月 16 日
3037 次浏览
3 条评论
4196字数
分类：题解

## Imformation

良心出题人： andysk $\times$ tony102 = 2j0s1yydnnoat

难度：NOIp

考察板块——联赛经典：树上问题、数论、组合数学、最短路、二分答案、动态规划

## 吐槽

h2 开黑+赛时找原题，还有人交了发现自己 WA 了之后改对了....

不过他们没人 ak，因为唯一一个过了防 ak 题的选手但是他 t1 爆零了这不怪两位良心出题人，他自己不看题。

## 飞羽疾电 (kujou) 题解

### Subtask1, 2

首先我们将一条路径用$(w, h)$表示，意为这条路径有$w$次水平移动，$h$次垂直移动。

考虑将所有从$S$至 $T$ 的可能形成最短路径的路（即找不到另一条路 $w, h$ 都不大于它）都找出来。计算每条路为最短路时的 $k$ 值，取最大的即可。

### Subtask3

注意到 $k$ 越大，最短路的长度肯定不减，所以 $k$ 值可以二分。每次二分一个 $k$，跑最短路(Dijkstra)检验即可。时间复杂度为$O( (n + m) \log n \cdot \log s)$。

## 玩游戏(game)

### Subtask1

枚举每个子序列，容易发现每个质数是独立的。枚举这个子序列中出现的所有质因数 $p$，将子序列中所有数的因子 $p$ 的次数从大到小排序，第 $i$ 个记为 $x_i$。

容易发现最终得到的数中 $p$ 的次数一定是这些数的中位数，记为 $x$，则 $p$ 的总贡献为 $\sum|x-x_i|$。时间复杂度为 $O(2^n \sqrt w)$，其中 $w$ 为值域。

### Subtask2

对于每个质数 $p$，将原数列中所有数的因子 $p$ 的次数 $x_i$ 从大到小排序（若 $p \nmid a_i$，则 $x_i=0$ ），设从左往右第 $i$ 个的排名为 $i$，考虑其贡献的次数。

在它左边选 $a\in[0,i-1]$ 个，右边选 $b\in[0,n-i]$ 个的贡献为

$$
\begin{cases}x_i & a < b \\ -x_i &a > b\\ 0 & a=b\end{cases}
$$

其中"选 $k$ 个"的意思是选出 $k$ 个 $x_j$，使它们作为某个质因子出现在选出的子序列中。容易发现这样恰好枚举到了所有情况。我们依次枚举 $i,a,b$，可以做到 $O(n^3)$。

### Subtask3

考虑$a<b$时，我们枚举$d=b-a$，则$d\in[1,n-i]$。贡献为

$$
\begin{aligned}
	&\sum\limits_{d=1}^{n-i}\sum\limits_{j=0}^{min(i-1,n-i-d)}\dbinom{i-1}{j}\dbinom{n-i}{j+d}\\
	=&\sum\limits_{d=1}^{n-i}\sum\limits_{j=0}^{min(i-1,n-i-d)}\dbinom{i-1}{j}\dbinom{n-i}{n-i-j-d}
\end{aligned}
$$

注意到

$$
\sum\limits_{b=0}^{min(m,a)}\dbinom{a}{b}\dbinom{n-a}{m-b}=\dbinom{n}{m}
$$

所以有

$$
\begin{aligned}
	&\sum\limits_{d=1}^{n-i}\sum\limits_{j=0}^{min(i-1,n-i-d)}\dbinom{i-1}{j}\dbinom{n-i}{n-i-j-d}\\
	=&\sum\limits_{d=1}^{n-i}\dbinom{n-1}{n-i-d}=\sum\limits_{d=0}^{n-i-1}\dbinom{n-1}{d}
\end{aligned}
$$

同理，当$a>b$时，贡献为$-\sum\limits_{d=0}^{i-2}\dbinom{n-1}{d}$。

设$s(x)=\sum\limits_{d=0}^{x}\dbinom{n-1}{d}$，则总贡献为$s(n-i-1)-s(i-2)$。

预处理组合数前缀和即可。时间复杂度为$O(n \log n)$。

## 仪式感(sor)

### Subtask1

$O(2^n)$ 枚举子集统计答案即可。

### Subtask2

记 $p_x=\sum\limits_{i=1}^{n}{[x|S_i]}$。

我们首先可以发现一个性质：对于当前的 $k$，若 $x\neq -1$，则 $y \neq -1$，且 $y=p_k$；若 $x=-1$，则 $y=-1$。

证明：$y\neq -1$时，$S$ 中所有为 $k$ 的倍数的数的 $\gcd$ 一定也为 $k$ 的倍数，设 $\gcd$ 为 $d$；但 $d$ 只能为 $k$，否则 $x=-1$，矛盾。

所以我们只用求出 $x$ 就好了。设 $dp_x$ 表示 $\gcd$ 为 $x$ 时最少取多少个数，则答案为 $dp_k$。转移如下：

$$
dp_{\gcd(x,S_i)}=\min(dp_{\gcd(x,S_i)},dp_x+1),x\in[2,S_i]
$$

其中 $x$ 只要枚举到 $S_i$ 是因为 $\gcd$ 有循环节。时间复杂度为 $O(n\sum{S_i})$。

### Subtask3

注意到上一个$dp$有很多无用状态，可以开一个 $map$ 存下有用状态再转移。不清楚能不能通过。

进一步优化，发现这个转移式子很像最短路，按最短路转移即可。复杂度大概是 $O(n^2 \log n)$

### Subtask4

设值域为 $w$。当 $k=1$ 时，注意到 $2\times 3\times 5\times 7\times 11\times 13\times 17\times 19=15796638>w$，所以答案的上界为$7$；那么$k>1$时，答案肯定也不超过 $7$。所以考虑从小到大枚举答案，检验是否可行。

设当前枚举的答案为 $t$，即最少选出 $t$ 个数能使它们的 $\gcd=k$。设 $f_x$ 表示选出 $t$ 个数使它们的 $\gcd=x$ 的方案数，那么

$$
f_x=\dbinom{p_x}{t}-\sum\limits_{j=2}^{\lfloor\frac{w}{x}\rfloor}f_{j\cdot x}
$$

解释：在所有 $x$ 的倍数中选 $t$ 个，它们的 $\gcd$ 也是 $x$ 的倍数。但我们要求恰好为 $x$，所以要减掉多算的。

如果最后 $f_k>0$，说明现在 $check$ 的 $t$ 可行，那么它就是答案。否则若 $\forall {t\in[1,7]}$，$f_k=0$，说明无解，$x=y=-1$。复杂度$O(w\log w)$。

## 摩拉克斯 (morax)

### 简化问题

先来考虑一个简单版本的问题：我们只有一个北国银行。答案是：

$$
\sum\limits_{(x,fa)\in E} w \cdot min(size_{x},S - size_{x})
$$

证明：

不妨设树根为$1$。在上面的表达式中，$size_{x}$ 表示的是在 $x$ 子树中居民的数量，$S$表示树中居民的总数量。

考虑如何计算所有居民接收到一枚钟离盾的总时间：对于每一条边，它的贡献为 $w$ $*$ **通过这条边的居民的数量**的总和，即对于每一条边  $(x, fa, w)$，我们有两种选择：一是选择子树内的所有居民通过该边（此时北国银行在子树外），故此部分贡献为  $w \cdot size_{x}$；二是选择 $x$ 的子树外的所有点上的居民通过该边进入 $x$ 的子树领取钟离盾（此时北国银行在子树内）。两种方式取 $min$ 即可。

### Subtask1

暴力枚举两个北国银行的位置。

### Subtask2

在链上的直接算即可。

### Subtask3

考虑最终北国银行放置的位置，会有一条没有居民过的边。那么可以枚举该边并将此边断开，使原树分成两个树，再通过上面的方法对两棵树的答案独立计算。时间复杂度为 $O(n^2)$。

### Subtask4

定义 $in_v$ 为 DFS 时进入$v$ 点的时间戳，$out_v$ 为 DFS 时离开 $v$ 点的时间戳。
假设只放置一个北国银行，我们就应该找到对于所有边 $e(v, to, w)$ ：$\sum\limits_{e\in E} w \cdot min(size_{to}, S - size_{to})$ 的总和。考虑 $size_{to}$ 和 $S - size_{to}$ 什么时候会算到贡献里：$w \cdot min(size_{to}, S - size_{to})$ 为 $w \cdot size_{to}$ 当且仅当 $size_{to} \leq \frac{S}{2}$， 为 $w \cdot (S - size_{to})$ 当且仅当 $size_{to} > \frac{S}{2}$。

回到 $O(n^2)$ 的解法。我们在 DFS 时在树中移去边 $(v, to, w)$ 。现在有两棵子树，大小分别为：$X = size_{to}, Y = size_{1} - size_{to}$。 考虑分别在 $X, Y$ 两棵树上解决问题。

第一部分先计算 $to$ 子树中的点的答案： $w \cdot min(size_{to}, X - size_{to})$ 的值的和。我们可以计算出 $w \cdot size_{to} (\forall size_{to} \leq \frac{X}{2}) + w \cdot X (\forall size_{to} > \frac{X}{2}) - w \cdot size_{to} (\forall size_{to} > \frac{X}{2})$。

剩余的部分就是要求出区间 $[l,r]$ 内所有数字 $\leq K$ 的和。可以把区间 $[in_{to}, out_{to}]$ 内的点的 $w$ 和 $w \cdot size_{to}$ 丢进两个树状数组，分别统计两类的答案即可。

$to$ 的子树以外的部分做法也很类似。注意要将这些操作在区间 $[1, in_{to} - 1]$ 和 $[out_{to} + 1, n]$ 和子树 $Y$ 上完成。除了从根节点开始的链到 $v$ （ 包括 $to$ 的子树中的节点）。在这条链上 $size_u$ 单调递减，所以用双指针并且记录前缀和。可以减去我们要为 $\leq \frac{Y}{2}$ 计算的部分。同样对 $size_{1} - size_{u}$ 做这样的步骤。最后加上我们需要的 $> \frac{Y}{2}$ 的部分，这部分在这条链上递增。

时间复杂度和空间复杂度均为 $O(n \log n)$ 。

最后修改：2021 年 09 月 16 日

如果觉得我的文章对你有用，请随意赞赏

3 条评论

flashhu
September 18th, 2021 at 09:51 pm

%%%%%%

回复
Eason_AC
September 16th, 2021 at 03:02 pm

最后一题题解里面的第二个 Subtask 2 应该是 Subtask 4 吧qwq

回复
1. tony102
  September 16th, 2021 at 07:03 pm
  
  @Eason_AC
  
  fixed
  
  回复

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

rlenitkthe
真好呢
暴力膜托
暴力膜托暴力膜托暴力膜托暴力膜托暴力膜托暴力膜托暴力膜托%%%
TosakaUCW
前排狂暴膜托！
菲兹克斯喵
竟然……又找到一个校友……而且初中和高中都是同一个学校……天哪...
暴力膜托
快给黄明珍开个方子吧，可怜孩子补太猛了

20210916 2j0s1yydnnoat 模拟赛官方题解

tony102 • 2021 年 09 月 16 日

## Imformation

良心出题人： andysk $\times$ tony102 = 2j0s1yydnnoat

难度：NOIp

考察板块——联赛经典：树上问题、数论、组合数学、最短路、二分答案、动态规划

## 吐槽

h2 开黑+赛时找原题，还有人交了发现自己 WA 了之后改对了....

不过他们没人 ak，因为唯一一个过了防 ak 题的选手但是他 t1 爆零了这不怪两位良心出题人，他自己不看题。

## 飞羽疾电 (kujou) 题解

### Subtask1, 2

首先我们将一条路径用$(w, h)$表示，意为这条路径有$w$次水平移动，$h$次垂直移动。

考虑将所有从$S$至 $T$ 的可能形成最短路径的路（即找不到另一条路 $w, h$ 都不大于它）都找出来。计算每条路为最短路时的 $k$ 值，取最大的即可。

### Subtask3

## 玩游戏(game)

### Subtask1

容易发现最终得到的数中 $p$ 的次数一定是这些数的中位数，记为 $x$，则 $p$ 的总贡献为 $\sum|x-x_i|$。时间复杂度为 $O(2^n \sqrt w)$，其中 $w$ 为值域。

### Subtask2

在它左边选 $a\in[0,i-1]$ 个，右边选 $b\in[0,n-i]$ 个的贡献为

$$
\begin{cases}x_i & a < b \\ -x_i &a > b\\ 0 & a=b\end{cases}
$$

### Subtask3

考虑$a<b$时，我们枚举$d=b-a$，则$d\in[1,n-i]$。贡献为

注意到

$$
\sum\limits_{b=0}^{min(m,a)}\dbinom{a}{b}\dbinom{n-a}{m-b}=\dbinom{n}{m}
$$

所以有

同理，当$a>b$时，贡献为$-\sum\limits_{d=0}^{i-2}\dbinom{n-1}{d}$。

设$s(x)=\sum\limits_{d=0}^{x}\dbinom{n-1}{d}$，则总贡献为$s(n-i-1)-s(i-2)$。

预处理组合数前缀和即可。时间复杂度为$O(n \log n)$。

## 仪式感(sor)

### Subtask1

$O(2^n)$ 枚举子集统计答案即可。

### Subtask2

记 $p_x=\sum\limits_{i=1}^{n}{[x|S_i]}$。

我们首先可以发现一个性质：对于当前的 $k$，若 $x\neq -1$，则 $y \neq -1$，且 $y=p_k$；若 $x=-1$，则 $y=-1$。

证明：$y\neq -1$时，$S$ 中所有为 $k$ 的倍数的数的 $\gcd$ 一定也为 $k$ 的倍数，设 $\gcd$ 为 $d$；但 $d$ 只能为 $k$，否则 $x=-1$，矛盾。

所以我们只用求出 $x$ 就好了。设 $dp_x$ 表示 $\gcd$ 为 $x$ 时最少取多少个数，则答案为 $dp_k$。转移如下：

$$
dp_{\gcd(x,S_i)}=\min(dp_{\gcd(x,S_i)},dp_x+1),x\in[2,S_i]
$$

其中 $x$ 只要枚举到 $S_i$ 是因为 $\gcd$ 有循环节。时间复杂度为 $O(n\sum{S_i})$。

### Subtask3

注意到上一个$dp$有很多无用状态，可以开一个 $map$ 存下有用状态再转移。不清楚能不能通过。

进一步优化，发现这个转移式子很像最短路，按最短路转移即可。复杂度大概是 $O(n^2 \log n)$

### Subtask4

设当前枚举的答案为 $t$，即最少选出 $t$ 个数能使它们的 $\gcd=k$。设 $f_x$ 表示选出 $t$ 个数使它们的 $\gcd=x$ 的方案数，那么

$$
f_x=\dbinom{p_x}{t}-\sum\limits_{j=2}^{\lfloor\frac{w}{x}\rfloor}f_{j\cdot x}
$$

解释：在所有 $x$ 的倍数中选 $t$ 个，它们的 $\gcd$ 也是 $x$ 的倍数。但我们要求恰好为 $x$，所以要减掉多算的。

如果最后 $f_k>0$，说明现在 $check$ 的 $t$ 可行，那么它就是答案。否则若 $\forall {t\in[1,7]}$，$f_k=0$，说明无解，$x=y=-1$。复杂度$O(w\log w)$。

## 摩拉克斯 (morax)

### 简化问题

先来考虑一个简单版本的问题：我们只有一个北国银行。答案是：

$$
\sum\limits_{(x,fa)\in E} w \cdot min(size_{x},S - size_{x})
$$

证明：

不妨设树根为$1$。在上面的表达式中，$size_{x}$ 表示的是在 $x$ 子树中居民的数量，$S$表示树中居民的总数量。

### Subtask1

暴力枚举两个北国银行的位置。

### Subtask2

在链上的直接算即可。

### Subtask3

### Subtask4

时间复杂度和空间复杂度均为 $O(n \log n)$ 。

20210916 2j0s1yydnnoat 模拟赛官方题解

3 条评论

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

名人传

VP: AtCoder Beginner Contest 222(ABC222)

写在 CSP-S2021 前

机房标准化岚语发音对照

VP: AtCoder Beginner Contest 221(ABC221)

CF1437 简要题意及题解

20211101 格点迷踪 (grid)

VP: AtCoder Beginner Contest 221(ABC221)

從四時陰陽之氣的變化，看五臟藏象與生理特點

Python 学习中的一些积累

20210916 2j0s1yydnnoat 模拟赛官方题解

3 条评论

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

20210916 2j0s1yydnnoat 模拟赛官方题解

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款