2020-2021:teams:manespace:codeforces_round_656_div3
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:manespace:codeforces_round_656_div3 [2020/07/24 11:42] iuiou |
2020-2021:teams:manespace:codeforces_round_656_div3 [2020/07/24 14:12] (当前版本) iuiou |
||
|---|---|---|---|
| 行 33: | 行 33: | ||
| 题解：给定两排数，每排都有$n$个数，每次操作可以交换一列的两个数，问能否存在一个最少的交换方案，使操作之后每一行都是$1$到$n$的一个排列。 | 题解：给定两排数，每排都有$n$个数，每次操作可以交换一列的两个数，问能否存在一个最少的交换方案，使操作之后每一行都是$1$到$n$的一个排列。 | ||
| - | 题解：这题有点难想，大致是一个二分图的问题。首先遍历两行数，如果一个数的出现次数超过了2次，那么肯定不成立。如果所有数出现次数都是两次，那么一定有一种方案满足。现定四个数组$r1[n],r2[n],b1[n],b2[n],b$数组用于存放列数，$r$数组用于存放行数，如果对于一个数$i$,$b_{1i}=b_{2i}$,则不考虑这个点，因为肯定不会动这个点的。如果$b_{1i}≠b_{2i}$,考虑r数组，如果$r_{1i}≠r_{2i}$,则在 | + | 题解：这题有点难想，大致是一个二分图的问题。首先遍历两行数，如果一个数的出现次数超过了2次，那么肯定不成立。如果所有数出现次数都是两次，那么一定有一种方案满足。现定四个数组$r1[n],r2[n],b1[n],b2[n],b$数组用于存放列数，$r$数组用于存放行数，如果对于一个数$i$,$b_{1i}=b_{2i}$,则不考虑这个点，因为肯定不会动这个点的。接下来对点染色，如果$b_{1i}≠b_{2i}$,考虑$r$数组，如果$r_{1i}≠r_{2i}$,则在$b_{1i}$和$b_{2i}$之间连一条权为0的边表示，两点染的色必须相同。反之，连一条权为$1$的边，表示两个点颜色相反，最后从每个点开始$dfs$经行染色即可,注意每次比对将开头的那个点染成$1$还是$0$，最后的结果会最优(即最少)。 |
2020-2021/teams/manespace/codeforces_round_656_div3.1595562178.txt.gz · 最后更改: 2020/07/24 11:42 由 iuiou
