2020-2021:teams:farmer_john:jjleo:codeforces_round_657_div._2
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:farmer_john:jjleo:codeforces_round_657_div._2 [2020/07/24 17:43] jjleo [F] |
2020-2021:teams:farmer_john:jjleo:codeforces_round_657_div._2 [2020/07/24 17:48] (当前版本) jjleo [F] |
||
|---|---|---|---|
| 行 31: | 行 31: | ||
| * 题意:$2n \times 2m$的黑白棋盘，$i+j$为偶数则$(i,j)$为白否则为黑；$q$次操作，每次禁用或解禁一个白格，问每次操作后能否放置$n \times m$个国王使得他们互不相邻，两个国王所在格子有边相同或角相同则认为是相邻的。$(1 \leq n, m, q \leq 200\,000)$ | * 题意:$2n \times 2m$的黑白棋盘，$i+j$为偶数则$(i,j)$为白否则为黑；$q$次操作，每次禁用或解禁一个白格，问每次操作后能否放置$n \times m$个国王使得他们互不相邻，两个国王所在格子有边相同或角相同则认为是相邻的。$(1 \leq n, m, q \leq 200\,000)$ | ||
| - | * 题解:考虑每四个格子为一个大矩阵，整个棋盘恰有$n \times m$个大矩阵，每个大矩阵里放且只能放一个国王。因此如果必须要求两两大矩阵的不冲突才能全部放满。一个大矩阵里面有$2$个白格，左上和右下，结论是如果有一个左上被禁的白格子完全位于另一个右下被禁的白格子的左上方，那么一定无解，否则一定有解。 | + | * 题解:考虑每四个格子为一个大矩阵，整个棋盘恰有$n \times m$个大矩阵，每个大矩阵里放且只能放一个国王。因此如果必须要求两两大矩阵的不冲突才能全部放满。一个大矩阵里面有$2$个白格，左上和右下，结论是如果有一个左上被禁的白格子完全位于另一个右下被禁的白格子的左上方，那么一定无解，因为假设其中一个放国王，那么他们路径上所有国王位置就被确定了，最后一定会冲突；否则一定有解。因此线段树维护$[1,x]$左上格子的最小行和$[x,m]$右下格子的最大行即可，修改则对每一列开一个set维护最大值和最小值即可。 |
2020-2021/teams/farmer_john/jjleo/codeforces_round_657_div._2.1595583804.txt.gz · 最后更改: 2020/07/24 17:43 由 jjleo
