2020-2021:teams:farmer_john:jjleo:codeforces_round_641_div._1
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:farmer_john:jjleo:codeforces_round_641_div._1 [2020/05/15 19:30] jjleo [A] |
2020-2021:teams:farmer_john:jjleo:codeforces_round_641_div._1 [2020/05/15 19:32] (当前版本) jjleo [C] |
||
|---|---|---|---|
| 行 5: | 行 5: | ||
| =====B===== | =====B===== | ||
| - | * 题意:给出一个长度为$n(n\le100,000)$的序列，每次可以将一个区间全部变成这个区间的中位数（偶数的时候取小的那个），问能否将区间所有数变为$k$。 | + | * 题意:给出一个长度为$n(n\le100\,000)$的序列，每次可以将一个区间全部变成这个区间的中位数（偶数的时候取小的那个），问能否将区间所有数变为$k$。 |
| * 题解:执着于找中位数的算法，时间全耗这题上了{{:2020-2021:teams:farmer_john:qq图片20200510224125.jpg?100|}}。首先序列中如果没有$k$肯定不行，否则若$n>1$则充要条件是存在长度为$3$的区间且有两个及以上的数$\ge k$，若$n=1$特判即可。 | * 题解:执着于找中位数的算法，时间全耗这题上了{{:2020-2021:teams:farmer_john:qq图片20200510224125.jpg?100|}}。首先序列中如果没有$k$肯定不行，否则若$n>1$则充要条件是存在长度为$3$的区间且有两个及以上的数$\ge k$，若$n=1$特判即可。 | ||
| 行 12: | 行 12: | ||
| * 题意:一个$n \times m$黑白方格阵，对于每一个方格，如果周围有相同颜色的方格，那么它下一秒会变为另一种颜色，否则颜色不变。初始时刻为$0$。$q$个询问，问每一个方格在某一秒$t$的颜色。$(1\le n,m\le 1000, 1\le q\le 100\,000, 1\le t\le 10^{18})$ | * 题意:一个$n \times m$黑白方格阵，对于每一个方格，如果周围有相同颜色的方格，那么它下一秒会变为另一种颜色，否则颜色不变。初始时刻为$0$。$q$个询问，问每一个方格在某一秒$t$的颜色。$(1\le n,m\le 1000, 1\le q\le 100\,000, 1\le t\le 10^{18})$ | ||
| - | * 题解: | + | * 题解:如果一个方格在某一秒第一次变化，那么它会在接下来的时间不断闪烁。而闪烁是走曼哈顿距离进行传递的，因此bfs找出每个方格开始闪烁的时间点即可$O(1)$回答询问。 |
2020-2021/teams/farmer_john/jjleo/codeforces_round_641_div._1.1589542248.txt.gz · 最后更改: 2020/05/15 19:30 由 jjleo
