[CF1391D] 505 - 状压dp

Description

给出一个 \(n \times m\) 的 \(01\) 矩阵，如果每个长宽都为偶数的正方形子矩阵内 \(1\) 的个数都为奇数，则这是一个“好的”矩阵。如果能把矩阵改成“好的”，问最少改多少个数。如果不能，输出 \(-1\)。

Solution

n,m 均大于等于 4 时，取任意一个 \(4 \times 4\) 子矩阵，即可证明问题无解

以下我们假设 \(n \le m\)

n=1 时，问题显然有解

n=2 时，只需要枚举开头是奇数还是偶数即可

n=3 时，设 \(f[i][j]\) 表示处理到第 i 列，状态为 j，此时修改的最小次数

#include <bits/stdc++.h>
using namespace std;

int vec2int(vector<int> x)
{
    int ans = 0;
    for (int i = 1; i <= 3; i++)
        if (x[i])
            ans += 1 << (i - 1);
    return ans;
}

vector<int> int2vec(int x)
{
    vector<int> ans(5);
    for (int i = 1; i <= 3; i++)
        if (x & (1 << (i - 1)))
            ans[i] = 1;
    return ans;
}

vector<int> vecvec[10];

signed main()
{
    ios::sync_with_stdio(false);

    for (int i = 0; i < 8; i++)
        vecvec[i] = int2vec(i);

    int n, m;
    cin >> n >> m;

    int swap_flag = 0;
    if (n > m)
        swap(n, m), swap_flag = 1;

    vector<vector<int>> a(n + 2, vector<int>(m + 2));
    if (swap_flag)
    {
        for (int i = 1; i <= m; i++)
        {
            string str;
            cin >> str;
            for (int j = 1; j <= n; j++)
                a[j][i] = str[j - 1] == '1';
        }
    }
    else
    {
        for (int i = 1; i <= n; i++)
        {
            string str;
            cin >> str;
            for (int j = 1; j <= m; j++)
                a[i][j] = str[j - 1] == '1';
        }
    }

    if (n >= 4)
    {
        cout << -1 << endl;
    }
    else if (n == 1)
    {
        cout << 0 << endl;
    }
    else if (n == 2)
    {
        vector<int> b(m + 2);
        for (int i = 1; i <= m; i++)
            b[i] = a[1][i] + a[2][i], b[i] &= 1;
        int sum = 0;
        for (int i = 1; i <= m; i++)
            sum += (i & 1) ^ b[i];
        cout << min(sum, m - sum) << endl;
    }
    else
    {
        vector<vector<int>> f(m + 2, vector<int>(10));
        for (int i = 1; i <= m; i++)
        {
            for (int j = 0; j < 8; j++)
            {
                int delta = 0;
                vector<int> &vj = vecvec[j];

                delta += vj[1] ^ a[1][i];
                delta += vj[2] ^ a[2][i];
                delta += vj[3] ^ a[3][i];

                f[i][j] = 1e9;
                for (int k = 0; k < 8; k++)
                {
                    vector<int> &vk = vecvec[k];
                    if ((vj[1] ^ vj[2] ^ vk[1] ^ vk[2]) == 0)
                        continue;
                    if ((vj[3] ^ vj[2] ^ vk[3] ^ vk[2]) == 0)
                        continue;

                    f[i][j] = min(f[i][j], f[i - 1][k] + delta);
                }
            }
        }

        int ans = 1e9;
        for (int i = 0; i < 8; i++)
            ans = min(ans, f[m][i]);
        cout << ans << endl;
    }
}