Petrozavodsk Camp, Summer 2021 MIPT Contest

排名	当场过题数	至今过题数	总题数
32/76	3	3	11

A

upsolved by 2sozx

题意

有两个 $n\times m$ 的矩阵，每个位置为 $v,>,.$ 三种其中一个，每次可以向其中一个矩阵的左上角放一个 $token$ ，然后顺着标志移动，$v$ 向下移动， $>$ 向右移动，当移动到 $.$ 或者超出矩阵范围则停止。每次移动过后，路径上的标记会反转，即 $v$ 变成 $>$ ，$>$ 变成 $v$ ，问最少操作多少次能让两个矩阵完全一样。

$q$ 次询问，每次会指定一个矩形的一个格子，将其标记反转，每次操作后要输出最少的操作次数，如果不存在输出 $-1$ 。$n,m\le 100,q\le {10}^5$

题解

首先想要简化题意，即对矩阵进行一种赋值方式，对于每个位置 $c$ 定义 $T_c,A_c,B_c$ 分别代表在这个位置的 $token,>,v$ 的值，定义一个矩阵的权值即为 $P=\sum _c(H_c{A}_c+K_c{B}_c)$ ，其中 $H,K$ 表示这个位置此时是否是 $>$ 与 $v$ ，我们可以将所有 $B$ 设为0，且显然对于我们权值的定义没有任何影响，因此我们只需要定义 $T_c$ 与 $A_c$ 。

考虑一个 $token$ 的移动，我们要使得每一步移动后整个矩阵的权值保持不变，因此可以根据这个想法得出一个表达式：

$$\{\begin{array}{l}{T}_{x,y}+A_{x,y}=T_{x,y+1}\\ T_{x,y}=A_{x,y}+T_{x+1,y}\end{array}$$

整理一下可以得到： $$\{\begin{array}{l}{T}_{x,y}={\displaystyle \frac{T_{x,y+1}+T_{x+1,y}}{2}}\\ A_{x,y}={\displaystyle \frac{T_{x,y+1}-T_{x,y+1}}{2}}\end{array}$$

因此如果我们知道了所有终态的 $T$ ，则可以在 $O(nm)$ 的复杂度内获得所有格子的 $T_c,A_c$ ，并且我们可以在 $mod1$ 的意义下进行这次操作，注意这里的 $mod1$ 可以理解为值始终保持在 $[0,1)$ 范围内，并且我们每次都是除以2，因此我们可以用二进制表示每个数。

下面证明一个引理：若 $P_1=P_2$ 则两个矩阵完全相同。

考虑一个位置 $A_c$ 以及在同一行右侧与其最近的终态点 $c^{{}^{\prime }}$ ，距离为 $d$ ，权值为 $T_{c^{{}^{\prime }}}$，则权值对于 $A_c$ 的贡献为 ${\displaystyle \frac{1}{2^d}}{T}_{c^{{}^{\prime }}}$ ，并且显然对于其余的点，由这个权值 $T_{c^{{}^{\prime }}}$ 产生的贡献一定不会等于 ${\displaystyle \frac{1}{2^d}}{T}_{c^{{}^{\prime }}}$ ，即 $d$ 不可能相同，因此 $P_1=P_2$ 时两个矩阵完全相同。

PS:这里的证明感觉没有很严谨，我感觉可能和后方证明结合，应该是大概率相同。

我们还会发现一个很显然的定理，就是答案一定是一直向其中一个矩形放入 $token$ ，正确性显然，并且放入 $K$ 个 $token$ 后矩阵的权值为 $P+K\times T_{0,0}$ 。因此我们可以根据两个矩阵的权值 $P_1,P_2$ 来计算得出所需的 $token$ 个数，即 ${\displaystyle \frac{P_1-P_2}{T_{0,0}}}$ 与${\displaystyle \frac{P_2-P_1}{T_{0,0}}}$。显然这样会出现负数，考虑 $T_{0,0}$ 的分母最大为 $2^p$ ，显然 $token$ 个数是在 $mod{2}^p$ 意义下的，因此可以除去负数的影响。

设 $\mathrm{\Delta }=P_1-P_2$ ，另一个同理。发现 ${\displaystyle \frac{\mathrm{\Delta }}{T_{0,0}}}$ 不好算，可以将 $T_{0,0}$ 对 $2^p$ 取类似逆元的东西，设为 $Inv$ ，发现对于矩阵所有数均乘以 $Inv$ 并不改变我们之前对于权值的定义，且乘后 $T_{0,0}={\displaystyle \frac{1}{2^p}}$ ，因此使用的 $token$ 数 $K={\displaystyle \frac{\mathrm{\Delta }}{T_{0,0}}}=\mathrm{\Delta }\times 2^p$ 。

但是对于一个 $\mathrm{\Delta }$ ，我们不知道他是否是一个可行解，因此我们考虑随机 $r$ 次，在从终态 $dp$ 的过程中随机向当前位的 $T_c,A_c$ 增加 $\frac{1}{2}$ ，显然这样的随机一定是有一种可行的终态的。对于所有的随机结果 $T_{i,0,0}$ 的分母最大值取 $max$ ，得到一个 $per$ ，如果存在一个随机状态的分母最大值不是 $per$ ，让其继续随机即可。如果这时 $\mathrm{\Delta }$ 全部相同，那么有 $1-\frac{1}{2^r}$ 的概率是正确的，因此可以直接计算。（分母 $2^{per}$ 的出现概率为 $\frac{1}{2}$ ）

发现答案的数量级是 $2^{n+m}$ 左右，因此可以压位。

总复杂度为 $O(nmr\frac{n+m}{G}\log per+qr\frac{n+m}{G})$

B

upsolved by 2sozx

题意

给定 $k,n$ 设 $M=\underset{k}{\underbrace{99\dots 9}}$ ，求第 $n$ 个数 $x$ 使得 $x\times M$ 不包含 $9$ 。$（k\le 18,n\le {10}^{18}）$

题解

C

upsolved by

题意

题解

D

solved by JJLeo

题意

题解

E

upsolved by 2sozx

题意

$n$ 个点 $m$ 条边，每个点有三个参数 $c_i,s_i,t_i$ ，假设当前权值为 $x$，对于一条边 $(u,v)$ ，如果 $x\le t_v$ 则可以从 $u$ 走到 $v$ 并且 $x=max(x,c_v)$。每个点开始 $x=c_i$ ，求对于每个点开始的所有路径的 $max{s}_u$ 。$n,m\le 2\times {10}^5,c_i,t_i,s_i\le {10}^9$

题解

$c_i,t_i$ 可以先离散化。考虑将边进行分类，假设当前的值为 $x$。

• 若 $min(c_u,c_v)\le x\le max(t_u,t_v)$ ，显然可以在 $u,v$ 反复横跳，将这样的边作为双向边。
• 若 $c_u\le x\le min(t_u,c_v-1)$ ，则只可以从 $u$ 到 $v$ ，将此定义为单向边。

考虑不考虑 $x$ 时将所有边进行分类，然后对于 $x$ 进行分治即可，对于双向边用可撤销并查集合并即可，分治时先递归右侧即可，这样才可以让单向边的答案更新正确。复杂度即为 $O(n{\log }^{2}n)$。

F

upsolved by

题意

题解

G

solved by JJLeo 2sozx Bazoka13

题意

题解

H

solved by 2sozx

题意

????

题解

????

I

upsolved by 2sozx JJLeo

题意

题解

J

upsolved by 2sozx

题意

给出 $n$ 个分式，求两两相减后化成最简分数的分母的乘积。 $n\le {10}^5$

题解

纯 $nt$ 题，就考虑每个质数的贡献。

枚举质数 $p$ ，考虑两个数相减 ${\displaystyle \frac{a}{b\times p^i}}-{\displaystyle \frac{c}{d\times p^j}}$。

• 如果 $i\ne j$ ，这俩数对于答案的贡献就是 $p^{max(i,j)}$ 。
• 如果 $i=j$，对答案的贡献即为 $p^{i-\sum _{k=1}^i[a\times b^{-1}=c\times d^{-1}mod{p}^k]}$ 。

然后直接算就行了，复杂度是个 $O(20n{\log }^{2}n)$ ，完全跑不满。

K

upsolved by 2sozx

题意

一颗 $n$ 个节点的树， $m$ 个叶子，树上有一个小偷，每次可以选择一条链，如果小偷在链上则被抓到，否则小偷可以往他所在的节点相邻节点移动或者不动。在初始不知道小偷位置的情况下，选择 $\lfloor \frac{m}{2}\rfloor +1$ 次能抓到小偷。给出方案。$n\le {10}^5$

题解

有以下两个非常显然的结论：

• 每次选择一定是选择两个叶子最优。
• 树中点度为 $2$ 的点没有卵用，删了就行。
• 选取一定要覆盖所有的边并且覆盖的顺序要有一定的要求。

考虑按照 $dfs$ 给叶子进行编号。假定此时叶子数 $m$ 为偶数。显然有一种简单的染色方式，即对于 $i\in (0,1,\frac{m}{2}-1)$ ，与 $m-1-i$ 进行配对，显然能够覆盖到所有的叶子。

考虑转化一下上述选取方式，我们选取一个中心点 $x$ ，每次覆盖 $(x-i,x+i-1)$ 这两个叶子（模意义下），显然这种选取方式是上述选取方式的一个拓展。

考虑这种操作带来的问题。对于每条边会将整棵树分离成两颗子树。考虑其中一颗子树，如果此时子树大小为偶数，则对于这条边会存在一个 $x$ 使得这条边最终没有被选到。会发现每条边最多会让两个点产生问题。

由于我们把点度为 $2$ 的点全部都删掉了，因此可以证明树中剩余的边不超过 $2m-3$ 条，并且和叶子直接相连的边不会让任何点产生问题。因此最多有 $m-3$ 条边会让点出问题，根据抽屉原理，一定会有一个点 $x$ 进行的覆盖至多让一条边没有被覆盖到，以这个点为中心覆盖即可。在覆盖的过程中，如果要跨过了最终没有被覆盖的边，强行覆盖一下这条边即可。

叶子数为奇数的时候，发现与上述情况本质相同，在选取 $x$ 的时候，最后覆盖一下 $x+\frac{m}{2}$ 即可。

记录

0h：最后一场毛营，开局找签到，啥也没找到。看一堆人过了H，开始硬猜H结论。ZYF想D，想了个硬分块的 $O(n\sqrt{n}\log (n))$ 的，看🐍他们过了H表示懵逼，完全不会(x，MJX猜了个垃圾结论，CSK写了暴力拍，发现MJX的算法完全寄了。MJX想了个K的算法，发现这个算法不知道从哪个叶子开始取，寄了。

1h：CSK看G，MJX ZYF看了看I，想了个处理方法，但是得 $O(n^3)$ 才能求出来，完全不会了。ZYF想了想，D用回滚莫队就不需要那个 $\log (n)$ 了，直接开冲。

2h：MJX和CSK讨论G，CSK把G的选取结论扔MJX，MJX想了想这题可以化成个直线取 $max$ 的操作，套个模板就行了，ZYF过了D后喂给ZYF，ZYF直接开冲。MJX想H乱搞，乱搞了个方法写上去，发现样例能过(x

3h：ZYF过了G，MJX开始对拍H，发现拍不出来啥问题，不管了直接交了，过了（迷惑）。之后继续想I。

4h：不会，啥也不会。

5h：jgg讲了个I，发现和我们做法一模一样，但是由于我们求的是所有的和，不用把每个位置都求出来，因此可以少个 $O(n)$ 的复杂度。🐂🍺。

总结

Dirt