2020-2021:teams:farmer_john:2sozx:codeforces_round_641_div._1
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:farmer_john:2sozx:codeforces_round_641_div._1 [2020/05/13 15:27] 2sozx [B] |
2020-2021:teams:farmer_john:2sozx:codeforces_round_641_div._1 [2020/05/13 16:10] (当前版本) 2sozx |
||
|---|---|---|---|
| 行 4: | 行 4: | ||
| =====B===== | =====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$ | * 题意：给定一个长度为 $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$ ，否则可以。证明如下： |
| - | * 序列中没有 $k$ 显然不能变为 $k$ | + | * 如果不存在连续的三个数其中至少两个数 ${\ge}k$ ，那么无论取长度为多少的序列都只能将其中 ${\ge}k$ 的数变成 $<k$ 的数。 |
| - | * 如果不存在连续的三个数使得其中至少两个数 ${\ge}k$ 那么就不能变成 $k$ ，否则可以，证明很显然 | + | * 如果存在，找到其中的一个区间，如果这个区间包含 $k$ 那么可以优先把这个全部变成 $k$ ,依次向左右移动即可。如果不包含 $k$ 那么可以先把这个序列变成全部 ${\ge}k$ 的数，向左右移动，如果碰到了 $k$ 则这个包含 $k$ 的区间可将这个区间全部变成 $k$ ，向左右移动即可。 |
| + | =====C===== | ||
| + | * 题意：$n{\times}m$ 的矩阵 $(n,m{\le}10^3)$ 每个格子可以为黑色或者白色，对于格子 $i,j$ ，如果相邻的格子中有与这个格子颜色相同的格子，那么 $i,j$ 在 $1$ 秒后会变为相反的颜色，否则不会变，问 $p(p{\le}10^{18})$ 秒后格子 $i,j$ 的颜色。询问次数 $t{\le}10^5$ | ||
| + | * 题解：首先我们可以发现如果一个格子在初始状态下不会发生改变，但是其相邻的格子在初始状态下会发生改变，那么这个格子在下一个状态中一定会发生改变。这样我们就可以通过 $BFS$ 初始状态下会发生改变格子的边界来确定每个格子在什么时候会发生改变，之后就可以做到 $O(1)$ 的询问 | ||
2020-2021/teams/farmer_john/2sozx/codeforces_round_641_div._1.1589354836.txt.gz · 最后更改: 2020/05/13 15:27 由 2sozx
