2020-2021:teams:farmer_john:2sozx:codeforces_round_641_div._1
A
- 题意：给定一个长度为 $n(n{\le}10^5)$ 序列 $s(s_i{\le}2{\times}10^5)$ ，令 $t=\{lcm(s_i,s_j)|i<j\}$ ，求 $gcd(t)$
- 题解：对于一个质数 $p$，设 $s_i$ 中最大含有 $p^{a_i}$ ，那么 $p$ 对于答案的贡献为 $p^{a_j}$ 其中 $a_j$ 为 $a_i$ 里面第二小的数。
B
- 题意：给定一个长度为 $n(n{\le}10^5)$ 序列 $a(a_i{\le}10^9)$ ，以及 $k(k{\le}10^9)$ ，每次操作取其中的一段 $l{\sim}r$ 并将这段区间内部所有元素变为这段区间内第 $\lfloor{\frac{(r-l+2)}{2}}\rfloor$ 小的数，问这个序列能否最终都变为 $k$
- 题解：序列中没有 $k$ 显然不能变为 $k$ ，如果不存在连续的三个数使得其中至少两个数 ${\ge}k$ 那么就不能变成 $k$ ，否则可以。证明如下：
- 如果不存在连续的三个数其中至少两个数 ${\ge}k$ ，那么无论取长度为多少的序列都只能将其中 ${\ge}k$ 的数变成 $<k$ 的数。
- 如果存在，找到其中的一个区间，如果这个区间包含 $k$ 那么可以优先把这个全部变成 $k$ ,依次向左右移动即可。如果不包含 $k$ 那么可以先把这个序列变成全部 ${\ge}k$ 的数，向左右移动，如果碰到了 $k$ 则这个包含 $k$ 的区间可将这个区间全部变成 $k$ ，向左右移动即可。
2020-2021/teams/farmer_john/2sozx/codeforces_round_641_div._1.1589355746.txt.gz · 最后更改: 2020/05/13 15:42 由 2sozx
