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_cA_c + K_cB_c)\) ，其中 \(H, K\) 表示这个位置此时是否是 \(>\) 与 \(v\) ，我们可以将所有 \(B\) 设为0，且显然对于我们权值的定义没有任何影响，因此我们只需要定义 \(T_c\) 与 \(A_c\) 。
考虑一个 \(token\) 的移动，我们要使得每一步移动后整个矩阵的权值保持不变，因此可以根据这个想法得出一个表达式：
整理一下可以得到： $$ \begin{cases} T_{x, y} = \dfrac{T_{x, y + 1} + T_{x + 1, y}}{2}\newline A_{x, y} = \dfrac{T_{x, y + 1} - T_{x, y + 1}}{2} \end{cases} $$
因此如果我们知道了所有终态的 \(T\) ，则可以在 \(O(nm)\) 的复杂度内获得所有格子的 \(T_c,A_c\) ，并且我们可以在 \(\bmod1\) 的意义下进行这次操作，注意这里的 \(\bmod1\) 可以理解为值始终保持在 \([0, 1)\) 范围内，并且我们每次都是除以2，因此我们可以用二进制表示每个数。
下面证明一个引理：若 \(P_1 = P_2\) 则两个矩阵完全相同。
考虑一个位置 \(A_c\) 以及在同一行右侧与其最近的终态点 \(c^{'}\) ，距离为 \(d\) ，权值为 \(T_{c^{'}}\)，则权值对于 \(A_c\) 的贡献为 \(\dfrac{1}{2^d}T_{c^{'}}\) ，并且显然对于其余的点，由这个权值 \(T_{c^{'}}\) 产生的贡献一定不会等于 \(\dfrac{1}{2^d}T_{c^{'}}\) ，即 \(d\) 不可能相同，因此 \(P_1 = P_2\) 时两个矩阵完全相同。
PS:这里的证明感觉没有很严谨，我感觉可能和后方证明结合，应该是大概率相同。
我们还会发现一个很显然的定理，就是答案一定是一直向其中一个矩形放入 \(token\) ，正确性显然，并且放入 \(K\) 个 \(token\) 后矩阵的权值为 \(P + K\times T_{0, 0}\) 。因此我们可以根据两个矩阵的权值 \(P_1, P_2\) 来计算得出所需的 \(token\) 个数，即 \(\dfrac{P_1 - P_2}{T_{0, 0}}\) 与\(\dfrac{P_2 - P_1}{T_{0, 0}}\)。显然这样会出现负数，考虑 \(T_{0, 0}\) 的分母最大为 \(2^p\) ，显然 \(token\) 个数是在 \(\bmod2^p\) 意义下的，因此可以除去负数的影响。
设 \(\Delta = P_1 - P_2\) ，另一个同理。发现 \(\dfrac{\Delta}{T_{0, 0}}\) 不好算，可以将 \(T_{0, 0}\) 对 \(2^p\) 取类似逆元的东西，设为 \(Inv\) ，发现对于矩阵所有数均乘以 \(Inv\) 并不改变我们之前对于权值的定义，且乘后 \(T_{0, 0} = \dfrac{1}{2^p}\) ，因此使用的 \(token\) 数 \(K = \dfrac{\Delta}{T_{0,0}} = \Delta\times2^p\) 。
但是对于一个 \(\Delta\) ，我们不知道他是否是一个可行解，因此我们考虑随机 \(r\) 次，在从终态 \(dp\) 的过程中随机向当前位的 \(T_c, A_c\) 增加 \(\frac{1}{2}\) ，显然这样的随机一定是有一种可行的终态的。对于所有的随机结果 \(T_{i, 0, 0}\) 的分母最大值取 \(\max\) ，得到一个 \(per\) ，如果存在一个随机状态的分母最大值不是 \(per\) ，让其继续随机即可。如果这时 \(\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 = \underbrace{99\ldots9}_k\) ，求第 \(n\) 个数 \(x\) 使得 \(x\times M\) 不包含 \(9\) 。\(（k\le18, 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^2n)\)。
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\) ，考虑两个数相减 \(\dfrac{a}{b\times p^i} - \dfrac{c}{d\times p^j}\)。
- 如果 \(i\not = j\) ，这俩数对于答案的贡献就是 \(p^{\max(i, j)}\) 。
- 如果 \(i = j\)，对答案的贡献即为 \(p^{i - \sum\limits_{k = 1}^{i}[a\times b^{-1} = c\times d^{-1} \bmod 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)\) 的复杂度。🐂🍺。