D题题解

前导知识: $11$. $2-SAT2-SAT$问题：https://www.cnblogs.com/captain1/p/9760503.html

这题我们利用 2-SAT推出满足条件

先假设变化完第一行有一个 $11$，这时候列最大值 $max(c_j)=2^{n-1}max(c\_j)=2^\{n-1\}$，所以此时要满足题目的条件$min(r_i)\ge max(c_j)min(r\_i)\ge max(c\_j)$就需要让行最小值 $min(r_i)>=2^{n-1}min(r\_i)>=2^\{n-1\}$也就是此时每列的第一行都是 $11$ 接着此时又得到 $max(c_j)=2^n-1max(c\_j)=2^n-1$, 所以需要让行最小值 $min(r_i)>=2^n-1min(r\_i)>=2^\{n\}-1$，所以此时矩阵为全一矩阵。 同理，假设第一行全为 $00$ 那么，变化完的矩阵就必须是全 $00$ 矩阵。

所以变化完的矩阵就只有01矩阵。那么我们只要知道变化成01矩阵需要多少步，经过实践可以知道，必须每一行的每个数字都相同，或者都不相同，才可能。 具体做法看代码。

首先先判断是否每一行都相等或者相反，不满足则为-1；

（ps:^ 是同为0，不同为一）

#include<iostream>
std::string a[2010];
int main() {
    int n, cnt = 0, x;
    std::cin >> n;
    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
    }
    for (int i = 2; i <= n; i++) {//这里是判断是否满足可变条件
        if (a[1] != a[i]) {
            cnt++; x = i;//统计不同行的个数，存储不同行在下面会用到
            for (int j = 0; j < n; j++) {
                if (a[1][j] == a[i][j]) {//一行中的每个是否相等,有相等的就不行
                    std::cout << "-1";
                    return 0;
                }
            }
        }
    }
    //接下来要变成1或者0的最小，只需要先判断第一行1和0哪个多
    int cnt1 = 0, cnt0 = 0,ans;
    if (2*cnt < n) {//如果是n/2有的过不了
        x = 1;
        ans = cnt;
    }
    else ans = n - cnt;//这里是不同行先变
    for (int i = 0; i < n; i++) {
        if (a[x][i] == '0') cnt0++;//统计这一行中0和1的数量
        else cnt1++;
    }
    
    ans += std::min(cnt0, cnt1);//再就是较少的列是我们需要变的
    std::cout << ans;
    return 0;
}