考试LIST [2020.12]

2020.12.01

$\texttt{Location:NOIP2020}$

得分：$\texttt{240/400,Rank1}$。

[12.01]-错误

没啥大问题，就是菜......

[12.01]-部分正解

$\texttt{T1}$

仔细观察下面的柿子：

$$\dfrac{1}{2}\sum_{i=1}^n \text{dis}(i,p_i)$$

其中 $\text{dis}$ 是树上路径经过的边数。

首先后面的求和可以很简单地感性理解，大概就是每一个点都可以通过交换整个树上路径的每一条边一次来到达应该在的位置，顺序什么的不管 反正可以认为他有。但是需要琢磨一下前面为什么有一个 $\dfrac{1}{2}$。

可以想到，这个 $\dfrac{1}{2}$ 告诉我们，每一次对边进行操作，都应该需要对这条边所连接的两个点均产生一次的贡献，这样才能得到 $\dfrac{1}{2}$ 的操作方案。

那么考虑一条边 $(x,y)$，令其深度较浅的是 $x$。那么应该有：$p_x$ 在 $y$ 子树内，且 $p_y$ 不在 $y$ 子树内，那么交换这条边恰好可以使 $p_x$ 向 $y$ 子树内，$p_y$ 向子树外各走一步。

那么可以直接 $\text{dfn}$ 判断一条边是否合法，丢到堆里，每次取编号最小的，交换两个点上的 $p$，再暴力判断这两个点所连出的所有边是否变得合法，若合法则加入堆即可。

可以这样感性证明一下：

首先可以得到：共一个端点的两条边不可能同时在堆中出现。因为考虑这个端点想去哪里，显然不可能向两个方向去。那么这样的话，堆中的边可以看做独立，每交换一次不会对其他的边有任何的影响。又每交换一次一定会对两个点都产生一个贡献，所以是存在正确性的。

再考虑时间复杂度。首先观察到一条边最多被交换 $\mathcal{O}(n)$ 次。因为最劣情况是这条边所分割成的两棵子树中的点都想到另一棵子树中去。再考虑当我们将每一条边都交换一次，每一条边会被暴力判断多少次。这个很显然是 $\mathcal{O}(n)$ 级别，因为一条边只有两个端点。

所以时间复杂度是 $\mathcal{O}(n^2\log n)$ 的。

$\texttt{T2}$

对于方案数有限，求期望的问题，可以考虑求贡献和再除以方案数。而对于方案数有限，求贡献和的题，同样可以考虑求期望，再乘上方案数。

首先考虑一下一个子集的 $f$ 如何求出。如果我们把所有路径挂在端点的 $\text{lca}$ 上，那么当我们选择了一条路径，相当于将该路径两端点的 $\text{lca}$ 的子树删除。因为 $\text{lca}$ 已经被删除，子树内任何点再向外走的话一定会走到 $\text{lca}$，这样不合法。也就是说，一条路径合法，当且仅当该路径两个端点均未被删除。

那么就有一个贪心：每次贪心地选择 $\text{lca}$ 深度更深的，将其子树删除。

再考虑原问题。首先转化为求期望，最后乘以 $2^{n^2}$。考虑 $\text{dp}$。

记 $f(x,i)$ 为在以 $x$ 为根的子树中，保留包括 $x$ 的一个大小为 $i$ 的联通块的概率。当 $i=0$ 则代表 $x$ 已经被一条路径覆盖。需要注意的是，状态中还没有考虑该联通块中的任意路径。

每次考虑一棵新的子树，然后暴力树形背包即可。至于某一个 $f(x,0)$ 的求法，可以认为是 $1-p$，其中 $p$ 是仍然存在一个包括 $x$ 的联通块。那么：

$$p=\sum_{i=1} \dfrac{1}{2^{i^2}}f(x,i)$$

也就是之前没考虑联通块内的路径，现在考虑。若希望保留整个大小为 $i$ 的联通块，则该联通块中任意一条路径都不能出现，因为出现了就必须选。由于一共有 $i^2$ 条路径，且每一条不出现的概率是 $\dfrac{1}{2}$，所以系数是 $\dfrac{1}{2^{i^2}}$。

再由于期望的线性性，所以答案是 $\sum_x f(x,0)$。

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

$\texttt{T3}$

首先通过直接 $\text{Dijkstra}$ 可以获得 $\text{35pts}$ 的好成绩 不是。问题在于数字太大，我们无法处理 $k$ 太大的时候的数字比较。

但是，观察发现，当 $\times 2$ 次数越多，则两个数字的差距实际上会越来越大。同时，一条边只会向该阶段/下一阶段连边，不妨进行分层图最短路。

假设现在在一层中，从上一层继承的距离是 $d_x$，他可能很大，我们希望将其缩小，但是不改变最短路的更新顺序。

假设从上一层转移过来的所有 $d_x$ 都是从小到大排好序的。那么我们设一个常数 $\text{lim}$，表示相邻两个 $d$ 的差距不可以超过 $\text{lim}$，若超过，就将差距缩为 $\text{lim}$。

考虑一下这个 $\text{lim}$ 的取值。在该层内最多有 $m$ 条边，一条边的贡献就是 $+1$，那么一个点的原先的距离 $d$ 经过这一层之后最多会增大 $m$。因此当 $\text{lim}>m$ 的时候，无论在这一层如何走都不会对 $d$ 的相对顺序有所改变。同样的，当我们进入下一层，则所有的 $d$ 集体 $\times 2$，这更加会加大两个 $d$ 之间的差距。

那么这样我们存下来的 $d$ 就都是 $n\times \text{lim}$ 范围内的了，不需要高精度。同时我们需要记录一下到达某一个点时，实际上距离 $\bmod\ 998244353$ 的值是多少，只是不用这个数字进行比较。

再考虑消去堆的 $\log$。假设进入本层的时候 $d$ 从小到大排好序，那么维护一个队列。每次拿出一个点，对别的点进行更新的时候，将这些引发的更新加入另一个队列中，不难发现这个队列中的 $d$ 也是单调的了。与此同时，我们同样维护了 $d$ 的单调性。每次从两个队头中选出距离更小的进行更新即可。

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

$\texttt{T4}$

把赋值看做加法，也就是在 $(x,y)$ 的位置上加上 $z-f(x,y)$，其中 $f(x,y)$ 是该点若赋值正确能得到的值。

那么首先求出每一个关键点的第二类斯特林数应该是多少，然后我们就只需要求出一个被修改的点，对后面一个修改点/查询点的贡献的系数了。可以考虑组合意义，从 $(x_j,y_j)$ 转移到 $(x_i,y_i)$，考虑其系数。

可以看做现在已经将 $x_j$ 个小球分在 $y_j$ 个盒子中，现在还有 $x_i-x_j$ 个小球，可以分到 $y_i$ 个盒子中，但是必须保证第 $y_j+1$ 到第 $y_i$ 个盒子中都有球。发现后面的限制很难搞，所以考虑容斥来求，可以得到系数是：

$$\dfrac{1}{(y_i-y_j)!}\sum_{l=0}^{y_i-y_j} (-1)^l\binom{y_i-y_j}{l}(y_i-l)^{x_i-x_j}$$

后面是钦定有 $l$ 个之后的盒子不放小球，然后就可以容斥成恰好 $0$ 个后面的盒子不放小球的方案数。而前面的 $\dfrac{1}{(y_i-y_j)!}$ 是为了消除后面 $y_i-y_j$ 个盒子的顺序带来的方案数，因为实际上这些盒子是没有差别的。

当我们每次枚举一个关键点并枚举一个他能够贡献的关键点，接着再确定上述系数，其时间复杂度是 $\mathcal{O}(k^2m\log n)$，无法通过。

考虑消除后面这个 $\log$。不难发现所有 $(y_i-l)^{x_i-x_j}$ 可以写成 $\dfrac{(y_i-l)^{x_i}}{(y_i-l)^{x_j}}$ 的形式，同时 $y_i-l$ 在 $m$ 以内，$x_i$ 的取值只有 $k$ 个。所以我们可以直接预处理出 $1$ 到 $m$ 的 $x_i$ 次幂及其逆元，这里是 $\mathcal{O}(km\log n)$ 的，前面的复杂度就降低到 $\mathcal{O}(k^2m)$。

加上前面求每一个点的斯特林数，时间复杂度是 $\mathcal{O}(km\log n+k^2m)$。

2020.12.02

$\texttt{Location:NOIP2020}$

得分：$\texttt{145/400,Rank3}$。

[12.02]-错误

$\texttt{T2}$ 可以拿到很多的暴力分，甚至暴力写得好就可以拿到 $\text{90pts}$，我却一分没写......要有梦想才行。

$\texttt{T3}$ 也有一些部分分没有拿到，同时关于欧拉函数的对称性与高维前缀和的 $\text{trick}$ 不够熟悉。

[12.02]-部分正解

$\texttt{T1}$

先丢出卡特兰数递推公式，以免自己忘记：

$$C_n=\sum_{i=0}^{n-1} C_{i}\times C_{n-i-1}$$

其中 $C_{0}=1$。

但是以上和本题没有关系 考虑出栈顺序模型的转化。发现出栈顺序可以转化为一个树形结构，从根节点开始，每次选择进入一个儿子并删除该子树，删除完所有儿子之后弹出自己。需要注意的是，这里选择儿子的顺序同样会影响出栈序列中数字的相对顺序。

考虑对于一组限制 $(a,b)$ 表示 $a$ 要比 $b$ 先出栈，当且仅当 $a$ 在 $b$ 的子树中，或在 $a$ 与 $b$ 的树上结点的 $\text{lca}$ 的位置上，先选择遍历了包含 $a$ 的子树。

不妨考虑类似区间 $\text{dp}$ 的思路，令 $\text{dp}_{l,r}$ 表示区间 $[l,r]$ 出栈顺序的方案数。考虑枚举最后一个出栈的元素 $k$，那么其中编号为 $[l,k-1]$ 的都应该在 $[k+1,r]$ 的之前就出栈了，因为我们需要 $k$ 加入栈的时候在栈底，所以 $[l,k-1]$ 先被全弹掉了。

若一个限制 $(a,b)$ 在我们枚举到这个最后出栈元素 $k$ 的时候不合法了，那么当且仅当 $l\le a,b\le r$ 且 $a=k\text{ or }b<k,a>k$。那么若每次枚举到一个 $k$ 之后暴力 $\text{check}$ 每一个限制是否合法，那么可以做到 $\mathcal{O}(n^3m)$。

考虑优化，发现当 $k$ 是一个定值的时候，每一个限制实际上是 $\text{ban}$ 掉了分别以 $l,r$ 为两个维度的二维平面上的一个矩形。也就是当 $(l,r)$ 这个点在这个矩形中，则表示 $(l,r)$ 与 $k$ 这个状态不合法。那么现在就转化为每一个位置是否被矩形覆盖，直接二维前缀和预处理即可。

时间复杂度 $\mathcal{O}(n^3+nm)$。

$\texttt{T2}$

把每一种数字看做一个限制，令一个位置 $i$ 之后，第一个值同为 $a_i$ 的位置为 $\text{nxt}_i$，那么显然一个区间不能够同时包含 $i$ 与 $\text{nxt}_i$。

那么当我们枚举了一个左端点 $l$，那么对于任意合法的 $r$，应该满足：

$$r\le\min_{i=l}^r\{\text{nxt}_i\}$$

那么对于区间 $[L,R]$，其合法的区间数量为：

$$\sum_{l=L}^R \min(\min_{i=l}^R \text{nxt}_i,R+1)-l$$

也就是考虑先枚举一个左端点，然后看有多少右端点满足上述条件。

比较显然的是，$\min_{i=l}^R \text{nxt}_i$ 是单调不降的，所以考虑在线段树上维护一下后缀 $\min$ 之和。

至于线段树维护后缀 $\min$，与之前考过的 $\text{God Knows}$ 一题较为相似，可以参考粉兔的博客，我也可能会写一篇 但大概率会咕

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

$\texttt{T3}$

先看一下后面的柿子，令 $f(x)=\sum_{i=1}^x [i\bot x] x$。那么后面那个实际上就是 $f(ij)$。

考虑一下与一个数字互质的数有些什么性质，有：若 $i\bot x(i<x)$，那么 $(x-i)\bot x$，辗转相除即可。那么如果把这些与 $x$ 互质的数字排成一排，然后再写一排翻转一下排序顺序，对应位置相加，那么恰好和就是 $x$ 老高斯了。于是可以写成：

$$f(x)=\dfrac{x\times \varphi(x)}{2}+[x=1]$$

那么 $f(ij)=\dfrac{ij\varphi(ij)}{2}+[ij=1]$，还有一个柿子：

$$\varphi(ij)=\dfrac{\varphi(i)\varphi(j)\gcd(i,j)}{\varphi(\gcd(i,j))}$$

带入题目中的柿子，变成：

$$\dfrac{1}{2}(1+\sum_{i=1}^n\sum_{j=1}^m \dfrac{i\varphi(i)\times j\varphi(j)\times \gcd^{n+1}(i,j)}{\varphi(\gcd(i,j))})$$

$$\dfrac{1}{2}(1+\sum_{i=1}^n i\varphi(i)\sum_{j=1}^m j\varphi(j)\dfrac{\gcd^{n+1}(i,j)}{\varphi(\gcd(i,j))})$$

那么可以从 $\gcd$ 的角度考虑，求 $\gcd$ 相当于对两个数的质因数分解之后，每一个质数的指数求 $\min$，那么可以看做一个 “$\min$ 卷积”。可以做一遍高维前缀和，然后高维前缀差回来，这里类似 $\text{lover}$ 一题。

具体来说，我们将每一个质数当作一个维度，对于一个质数 $p$ 与每一个 $i$，将 $i\times p$ 处的值累加到 $i$ 的位置，对两个 $\sum_{i=1}^n i\varphi(i)$ 都做一遍，然后对应位置相乘。这样每一个位置得到的，就是 $\gcd$ 是该位置倍数的值的和。

然后和上面做类似的东西，再将这个高维前缀和的数字作差还原即可。

$\texttt{T4}$

$\text{zxyhymzg}$ 是我们的红太阳！本题解全是抄袭的他的

考虑先建立 $2^{\max(n,m)}\times 2^{\max(n,m)}$ 的矩形，然后把最后的给删掉。

首先考虑一下矩形满足什么条件的时候，会使答案最大。首先可以想到先构造二维前缀异或的数组，然后还原回来。那么对于一个矩形，在前缀异或数组上就变成了四个点的异或，又可以看做两行中的两个点对。

• 对于第 $0$ 行与第 $i(i\ne 0)$ 行的贡献，设第 $i$ 行有 $c_0$ 个 $0$，$c_1$ 个 $1$，那么贡献为 $c_0\times c_1$。
• 对于第 $i$ 行与第 $j$ 行的贡献，设 $00$，$01$，$10$，$11$ 的个数分别是 $a,b,c,d$，贡献是 $ab+ac+bd+cd=(a+d)(b+c)$。

两者同时取最大值，则 $a=b=c=d=2^{m-2}$。然后随便构造一下即可。

2020.12.03

$\texttt{Location:NOIP2020}$

得分：$\texttt{295/400,Rank1}$。

[12.03]-错误

$\texttt{T1}$ 为 什 么 花 了 这 么 久 ！

[12.03]-部分正解

$\texttt{T1}$

考虑直接搜出第一列所有可能的情况，然后折半状压。

发现跑得不是很快，但是数据范围很小，所以打表就可以了。

$\texttt{T2}$

好题！

首先数据范围有 $n-1\le m\le 2n-1$，先考虑一下 $m\le n$ 的 $\text{Subtask}$。

对于 $m=n-1$，我们显然会连出一棵树/一条链，由于一定有度数为 $1$ 的点，所以答案至多为 $1$，当然，如果连出两个联通块显然不优。

对于 $m=n$，若连出基环树，那么一定存在度数为 $1$ 的点，不会使得答案比 $m=n-1$ 大。而如果连成一个环，答案为 $2$，所以一定连成环。

对于 $m>n$ 的情形，首先一定考虑连出一个环，接着在环上连边。我们现在希望每一个点度数至少为 $3$，这样答案就不会小于 $3$ 了，而若图中存在一个度数为 $2$ 的点，那么一定会删掉他使答案为 $2$。

因此，再将环上的点连边使得每一个点度数都至少为 $3$，若边不够则答案仍然是 $2$。同时答案不可能为 $4$，可以这样考虑：当我们看做把环上的边全部删除，那么剩下 $n-1$ 条边只能做到给每一个点的度数都增加 $1$，而不能让每一个点度数都增加 $2$，所以答案至多为 $3$。

根据上述方法构造完之后，若还有剩余的边，就随便连即可。

$\texttt{T3}$

咕咕咕

$\texttt{T4}$

考虑一个区间作为答案的贡献。若一个区间被划分成两个，左右分别被称作左区间与右区间。那么对于一个区间，其作为一个左区间/右区间的贡献类似，所以只讨论作为左区间的情形，右区间实际上只有一个能否大小相等的差别。

考虑现在对于一个左端点 $l$，我们枚举断开的点为 $\text{mid}$，那么由于 $[l,\text{mid}]$ 需要被贡献，所以枚举的右端点需要使得右区间更大。

考虑枚举这个右端点，然后需要使得先断开最左边的边、最右边的边，然后断开 $\text{mid}$，才可以被贡献。算一下概率，可以做到 $\mathcal{O}(n^3)$。

但是，我们发现，只要是一个位置符合条件的 $r$，一定存在一个更右边的点比 $\text{mid}$ 先删除，也就是说 $r$ 这个限制是无用的，其概率之和为 $1$。那么就只需要枚举 $l$ 与 $\text{mid}$，做到 $\mathcal{O}(n^2)$。

写出柿子，发现他的系数只和区间长度相关。那么不妨枚举这个长度 $\text{len}$，然后一次性算出所有的长度为 $\text{len}$ 的区间和的和，乘上这个系数即可。求所有长度为定值的区间和的和，可以先做一遍前缀和，然后对前缀和数组再做一遍前缀和，推推柿子就可以化成这个“二维前缀和”差分的形式，加上线性求逆元，就可以做到 $\mathcal{O}(n)$。

$2020.12.20$ 日之后的总结数据丢失，随缘补。咕咕咕