2020-2021:teams:hotpot:lotk:codeforces_round
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:hotpot:lotk:codeforces_round [2020/05/15 17:11] lotk |
2020-2021:teams:hotpot:lotk:codeforces_round [2020/05/15 17:35] (当前版本) lotk |
||
|---|---|---|---|
| 行 37: | 行 37: | ||
| ====题目大意==== | ====题目大意==== | ||
| - | 给定一个数列 $ a_n (n \le 100000 ，1 \le a_i \le 1e9) $ , 再给定一个数 k (1 \le k \le 1e9), 问能否通过把一个区间全部变成它的中位数的方式使序列全部变成 k. | + | 给定一个数列 $ a_n (n \le 100000 ，1 \le a_i \le 1e9) $ , 再给定一个数 $k (1 \le k \le 1e9) $, 问能否通过把一个区间全部变成它的中位数的方式使序列全部变成$ k $. |
| ====解题思路==== | ====解题思路==== | ||
| - | 首先，如果不存在 k ,那么答案肯定是否， 在存在 k 的情况下 ，如果 k 旁边有大于 k 的数，那么我们显然可以通过将这个数变成 k 和原本 k 的区间将别的数都变为 k. | + | 首先，如果不存在 $ k $,那么答案肯定是否， 在存在 $ k $ 的情况下 ，如果 $ k $ 旁边有大于 $ k $ 的数，那么我们显然可以通过将这个数变成 $ k $ 和原本 $ k $ 的区间将别的数都变为 $ k $, 进而我们发现，如果连续三个中存在两个 $\ge k$ ,那么可以通过区间操作将大于 $k$ 的数移到 $k$ 的旁边，若不存在，则不可能实现 (可以证明任意区间都会被变成小于 $k$ 的区间)。 |
| =====E.Orac and Game of Life===== | =====E.Orac and Game of Life===== | ||
| ====题目大意==== | ====题目大意==== | ||
| + | |||
| + | 给定一个 $ n \times m 的 01 矩阵 (1 \le n,m \le 1000)$, 每个时间一个周围存在不同类型点的点的类型会发生改变 $ (0 \rightarrow 1, 1 \rightarrow 0) $ 给定 $ t \le 100000 $ 个询问，每次问 $ i , j $ 位置上 $ p $ 时间的类型。 | ||
| ====解题思路==== | ====解题思路==== | ||
| + | |||
| + | 我们发现这个模型具有“传染”的性质，即上一时间变了的点周围没变的点，在下一时间会变且之后一直保持变的状态，因此我们只需要通过 $BFS$ 一次求出每个点开始变的时间并计算最后状态即可。 | ||
| + | |||
| + | <del> F不会 </del> | ||
2020-2021/teams/hotpot/lotk/codeforces_round.1589533881.txt.gz · 最后更改: 2020/05/15 17:11 由 lotk
