2020-2021:teams:manespace:codeforces_round_663_div2
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:manespace:codeforces_round_663_div2 [2020/08/14 15:25] iuiou |
2020-2021:teams:manespace:codeforces_round_663_div2 [2020/08/14 15:32] (当前版本) iuiou |
||
|---|---|---|---|
| 行 16: | 行 16: | ||
| 题意：给出一个$n*m$的$01$矩阵，问如何做出最小的改变即(0变1，1变0)使这个矩阵中任意一个偶数为边长的方阵中1的数量为奇数。 | 题意：给出一个$n*m$的$01$矩阵，问如何做出最小的改变即(0变1，1变0)使这个矩阵中任意一个偶数为边长的方阵中1的数量为奇数。 | ||
| - | 题解：首先发现，对于一个4*4的矩阵，由4个2*2的方阵组成，若这4个2*2的方阵都满足条件，则这个4*4的矩阵中1的数量一定是偶数个。所以显然一旦$n$和$m$的边长都大于4则一定不会成立。 | + | 题解：首先发现，对于一个4*4的矩阵，由4个2*2的方阵组成，若这4个2*2的方阵都满足条件，则这个4*4的矩阵中1的数量一定是偶数个。所以显然一旦$n$和$m$的边长都大于4则一定不会成立。所以现在我们只需要考虑n和m都小于4的情况，可以使用$dp$来做，状压dp，考虑每个列的2*2矩阵的状态，修改前一个的矩阵会影响到下一个矩阵，而且对于一种不满足情况的矩阵修改一次就可以改变其状态，用01串来表示状态，枚举每个列，做转移即可。 |
2020-2021/teams/manespace/codeforces_round_663_div2.1597389937.txt.gz · 最后更改: 2020/08/14 15:25 由 iuiou
