【6.25】Codeforces Global Round 21

题意：给定一个长度为 $n$ 的数组 $a$ 、一个长度为 $k$ 的数组 $b$ 和一个数字 $m$，现在对数组 $a$ 进行以下操作：

• 选择数组 $a$ 中一个 $m$ 的倍数 a i a_i ai​ 替换成 $m$ 个 a i m \dfrac{a_i}{m} mai​​
• 选择数组 $a$ 中 $m$ 个相同的数字 a i , a i + 1 , … , a i + m − 1 a_i,a_{i+1},\dots,a_{i+m-1} ai​,ai+1​,…,ai+m−1​ 替换成 m ⋅ a i m\cdot a_i m⋅ai​

请问能否把数组 $a$ 变成数组 $b$。
数据范围： 1 ≤ n , k ≤ 5 × 1 0 4 1\le n,k\le 5\times 10^4 1≤n,k≤5×104， 2 ≤ m ≤ 1 0 9 2\le m\le 10^9 2≤m≤109， 1 ≤ a i , b i ≤ 1 0 9 1\le a_i,b_i\le 10^9 1≤ai​,bi​≤109， ∑ n + k ≤ 2 × 1 0 5 \sum n+k\le 2\times 10^5 ∑n+k≤2×105。

思路：相同相邻的数字分块，将两个序列尽量展开使得长度最长，然后比较一下即可。

AC代码：https://codeforces.com/contest/1696/submission/161759606

题意：给出一个 $1$ 到 $n$ 的排列 [ a 1 , a 2 , … , a n ] [a_1,a_2,\dots,a_n] [a1​,a2​,…,an​] 。对于 $1\le i<j\le n$ ，记 $\mathrm{mn}(i,j)$ 为 min ⁡ k = i j a k \min\limits_{k=i}^j a_k k=iminj​ak​ ，记 $\mathrm{mx}(i,j)$ 为 max ⁡ k = i j a k \max\limits_{k=i}^j a_k k=imaxj​ak​ 。

有一张 $n$ 个点的无向图，点的编号为 $1$ 到 $n$ 。对于每一对整数 $1\le i<j\le n$ ，如果同时满足 mn ⁡ ( i , j ) = a i \operatorname{mn}(i,j)=a_i mn(i,j)=ai​ 且 mx ⁡ ( i , j ) = a j \operatorname{mx}(i,j)=a_j mx(i,j)=aj​ ，或同时满足 mn ⁡ ( i , j ) = a j \operatorname{mn}(i,j)=a_j mn(i,j)=aj​ 和 mx ⁡ ( i , j ) = a i \operatorname{mx}(i,j)=a_i mx(i,j)=ai​ ，那么就在 $i$ 和 $j$ 之间连一条长度为 $1$ 的边。

询问这张图中从 $1$ 到 $n$ 的最短路的长度。可以证明 $1$ 和 $n$ 总是连通，所以最短路总是存在。 1 ≤ n ≤ 2.5 ⋅ 1 0 5 1\le n\le 2.5\cdot 10^5 1≤n≤2.5⋅105

思路：从一个点开始，如果向右是增大的，那它只能成为最小值，那么子区间内不能有比它小的，可以用单调栈预处理右边第一个比它小的作为区间的右边界。然后在这个区间里，找到一个右边界使得右边界上的数是区间内最大的。这里如果有多个数符合条件，容易知道跳到哪个都行，所以干脆跳到最大的。

如果向右是减小的，同理即可。

AC代码：https://codeforces.com/contest/1696/submission/161786928

题意：你有一张残缺的有 $n+1$ 行的网格纸，第 $i$ 行只有前 A i A_i Ai​ 格 ( A i ≥ A i + 1 ) (A_i\geq A_{i+1}) (Ai​≥Ai+1​) 。在一开始，在第一行的第一格写着一个数 $1$ ，其他格子上写的都是 $0$ 。

接下来，你可以进行若干次操作，每次操作可以将格子上任意位置 $(i,j)$ ，将上面的数减一，并将 $(i+1,j)$ 和 $(i,j+1)$ 上的数加一。特别的，如果即使在纸的边界上，你也可以进行这一操作，这会使得在格子外的加法无效。

现在，你需要求出使网格纸上的数全部变成 $0$ 的最少操作次数对 1 0 9 + 7 10^9+7 109+7 取模的结果。 A i , n ≤ 2 × 1 0 5 , A i ≥ A i − 1 A_i,n\leq 2\times 10^5,A_i \geq A_{i-1} Ai​,n≤2×105,Ai​≥Ai−1​

题解：Codeforces Global Round 21 D(分治) E(组合数学)

思路：其实就是求杨辉三角斜向的组合数之和，有公式。定义杨辉三角从 0 行 0 列开始编号，那么从第 $a$ 行首元素开始向斜下方至第 $b$ 列的元素之和为 C a + b + 1 b + 1 C_{a+b+1}^{b+1} Ca+b+1b+1​ 。推导

AC代码：https://codeforces.com/contest/1696/submission/163351101