KbMu2

编辑于 2021-02-23 10:32

【题解】2021牛客寒假算法基础集训营5 精

美丽的路径

首先很显然，如果点 $s$ 无法到达点 $t$ ，那么答案一定是 $NO$ ；接着考虑二分最大的美丽值，假设二分出的最
大美丽值为 $x$ ，然后把 $n$ 个点中点权大于等于 $x$ 的标记为 $0$ ，剩下的都标记为 $1$ ，然后我们从 $s$ 点开始 $dfs$ ，如果从 $s$ 到 $t$ 点路径上存在两个相邻的点标记都为 $0$ 的话，那么显然答案一定大于等于 $x$ ；当然如果从 $s$ 到 $t$ 的路径上存在一条首尾点都为 $0$ ，然后 $0$ 和 $1$ 交替出现的路径的话；或者存在一条从 $s$ 到 $t$ 的路径上 $0$ 和 $1$ 交替出现，并且 $0$ 和 $1$ 的个数相等的时候，显然这两种路径上的答案一定也大于等于 $x$ ；其余情况显然答案一定会小于 $x$ ，因此我们可以通过二分得到最大的美丽值。

比武招亲（上）

显然，我们可以先枚举差值 $d$ ，这样可以有 $n-d$ 种方法填首尾两个数。

然后我们在差分之后的序列上考虑，显然是要填 $m-1$ 个数，和为 $d$ 。

所以方案数就是 $(n-d) \times C_{d+m-2}^{m-2}$ ，所以答案为 $\sum_{d=0}^{n-1}d\times(n-d)\times C_{d+m-2}^{m-2}$ ，组合数可以

通过预处理来得到。所以我们就可以在 $O(n)$ 的时间内算出答案。

比武招亲（下）

我们先考虑取值范围在 [1,m] 应该怎么做，显然答案为： $\sum_{i=1}^{m}i \times ({i^n-{(i-1)}^n})$

其中 $i\times({i^n-{(i-1)}^n})$ 是一个 n+1 次多项式。
那么若 m 很大，我们则可以通过拉格朗日插值来得到 $f(m)$ 。

拉格朗日插值： $f(x)=\sum_{i}f(x_i)\times \frac{\prod\limits_{i\not=j}(x-x_j)}{\prod\limits_{i\not=j}(x_i-x_j)}$
由于我们可以预处理 $f(1)…f(n)$ ，其下标连续，所以可以通过预处理前缀积和后缀积做到 $O(k)$ 插值。
那么现在我们是否可以得到这个 $m=n^{n^{n}}(无限个n)$ 呢？
答案是肯定的，因为在模 $p$ 意义下，有多项式 $f(x)=f(x+p)$ 。
所以我们仅需要 $n^{n^{n}}(无限个n)$ 在模 $p$ 意义下的取值即可。

根据扩展欧拉定理： $a^b\equiv a^{b\mod \phi(n)+phi(n)} \pmod n,(a,n)\not=1$ 且 $b\ge\phi(n)$
$\phi$ 在做 $O(log)$ 次之后就会变成 1，而这以后权值就不会再改变了。

所以我们只要做 $O(log)$ 次这样的操作即可。
这样我们就得到了m。

然后插值一下即可得到答案。

石子游戏

考虑给石子堆染色，我们染 $k$ 种颜色，第 $i$ 堆石子染第 $i$ % $(k+1)+1$ 种颜色，例如：第一堆石子染第一种颜色，第二堆石子染第二种颜色，...，第 $k$ 堆石子染第 $k$ 种颜色，第 $k+1$ 堆石子染第 $1$ 种颜色，...等等；令 $sum_i$ 表示第 $i$ 种颜色最开始所对应的石子堆的石子总数， $num_i$ 表示第 $i$ 种颜色所对应的石子堆数目 $(1\le i\le k)$ 。我们会发现每次操作让连续 $k$ 个石子堆石子数都加一，相当于 $k$ 种颜色中的每
种颜色所对应的石子堆总石子数加一，所以操作结束后每种颜色所对应的石子堆的总石子数的增加数目一定是相同的。假设最后能让 $n$ 堆石子数相同，并且每堆石子都变成了 $x$ ，那么一定存在等式 $x*num_i-sum_i=x*num_j-sum_j$ ，其中 $1\le i\le k，1\le j\le k$ 。如果存在颜色不满足这个等式，那么一定是无解的。

当 $n$ % $k!=0$ 的时候，我们可以计算出 $x=(sum_i-sum_j)/(num_i-num_j)$ ，如果 $x$ 算出来不是整数，那么一定无解。由于最后的石子数目确定了，剩下的直接从左到右贪心扫一遍去判断每堆石子是否能到达 $x$ 即可。

当 $n$ % $k=0$ 的时候，此时 $num_i=num_j$ ，那么我们可以二分 $x$ 来求最小操作数，对于每次二分出的 $x$ ，从左到右贪心扫一遍去判断每堆石子是否能到达 $x$ 。

树上博弈

首先这题表面上是一个对抗博弈问题，但是注意看数据范围后，其实这题应该是一个简单状压和拓扑 $DP$ 的问题，首先我们用长度为 $n$ 的二进制来表示游戏中树的不同的状态，如果一个二进制 $k$ 的第 $i$ 位为 $1$ ，表示这棵树的第 $i$ 个点已经被删除了。我们先用 $dfs$ 求出所有的合法状态，并且把这些合法的状态所对应的二进制进行标记。由于这个游戏中只有删除，所以任何两个合法状态之间只可能存在一条有向边，假设把每个合法状态看成点，如果一个合法状态 $A$ 能通过一次操作变成一个合法状态 $B$ ，那么点 $A$ 向点 $B$ 连一条有向边，边权就是这次操作删除的点的点权，最后这个图就是一个 $DAG$ ，我们就可以用拓扑 $DP$ 来求解最后的答案，当操作数为奇数的时候， $DP$ 是取 $max$ ；当操作数为偶数的时候， $DP$ 是取 $min$ 。

我的心是冰冰的

签到题，当 $n=1$ 的时候，输出 $1$ ；当 $n!=1$ 的时候，输出 $2$ 。

模仿游戏

这个题是一个贪心题，很显然每种类型的怪兽第一次出现的时候只能由泽鸽鸽打败，所以我们要让泽鸽鸽的时间尽可能早的去打每种类型第一次出现的怪兽，剩下的时间安排就是让叶妹妹和泽鸽鸽尽可能早的打当前时间剩余的怪兽。给每种类型的第一次出现的怪兽打上标记，并且记录每只怪兽后面下一只同种类型的怪兽出现时间是多少。按照第一维为被标记的怪兽排前面，没被标记的怪兽排后面，第二维为每只怪兽出现时间早的排前面，出现时间晚的排后面来对所有怪兽进行排序。用一个 $set$ 维护最近打败的每种类型的怪兽编号，然后枚举时间，如果当前这只怪兽是这种类型的怪兽的第一次出现并且它的出现时间在当前枚举的时间内，那么把怪兽编号加入到 $set$ 里面，直到不满足条件时，才停止加入。然后看 $set$ 里面的第一只怪兽的下一只同种类型的怪兽是否能加入，如果能，则先把第一只怪兽删除，再加入第一只怪兽的下一只同种类型的怪兽；否则则不改变。再将其余的情况进行讨论，进行 $set$ 的插入和删除怪兽编号，具体细节可以看代码，最终我们将会得到所有怪兽都被打败后的最早时间。

白色长方形

这个题考虑一下扫描线，把每个黑色矩形的上边界（左边界）和下边界（右边界）加入结构体数组，按照坐标顺序排序；先横着扫描一遍，再竖着扫描一遍，用 $set$ 或者线段树维护当前区间白色格子的连续区域，遇到上边界（左边界）的时候，需要分类讨论区间的拆分；同时遇到下边界（右边界）的时候，也需要分类讨论区间的合并。区间的拆分和合并细节有点多，分类讨论的时候尽量要把每种情况都考虑清楚。然后就是白色矩形区域算白色长方形个数，这个用数学知识很容易就算出来了，注意特判 $a$ 和 $b$ 想等的时候答案要除以 $2$ ，因为横竖扫描线求出的白色长方形都是一模一样的。

正十字

首先我们用 $f[i][j]$ 表示以第 $i$ 行第 $j$ 列的格子为中心的正十字的最大边长，显然 $0\le f[i][j]\le min(n,m)$ 。我们用暴力可以直接求出 $f[i][j]$ ，问题就变成了每次询问两个格子，求它们之间的所有路径里面的每条路径的最小值的最大值。这个问题我们可以用并查集来解决，一开始网格为空，每次将当前 $f[i][j]$ 最大的所有格子加入图中，用并查集来维护图的联通性，然后扫 $Q$ 个询问，看每个询问的两个格子是否联通，如果联通则得到了当前询问的答案（即当前 $f[i][j]$ 的最大值）；如果所有格子添加完后，有一个询问的两个格子都不联通，那么说明这个询问的答案就是 $-1$ ，复杂度为 $O(min(n,m)/2*Q)$ 。

桥

首先一棵树上有 $n-1$ 个桥，题目中的操作添加的两条边会构成两个环，而两个环上的边都不是桥。又因为环有交点，所以我们对两个环求并集。假设两个环的并集能让一条路径上的边变得都不是桥，这条路径的点数假设为 $k(k>1)$ ，那么我们通过计算会发现总共有 $(6*k-6)$ 种不同的操作会满足假设，其中当 $k=1$ 时，只有一种操作满足假设。那么现在的问题相当于变成了只添加一条边，如果添加完这条边后的图中桥的个数在区间 $[L,R]$ 内，那么答案加上 $6*k-6$ ，其中假设这条边所对应的路径的点数为 $k$ 。接着，我们把满足操作后图中桥的个数在区间 $[L,R]$ 内的不同的操作数 $=$ 满足操作后图中桥的个数在区间 $[1,R]$ 内的不同的操作数 $-$ 满足操作后图中桥的个数在区间 $[1,L-1]$ 内的不同的操作数。因此我们可以用点分治和排序来解决添加一条边后图中桥的个数在区间 $[1,x]$ 的不同的添加方案数，这样就完美解决问题了，注意特判 $n-1<L$ 的情况，直接输出 $0$ 即可。