思维+位运算+贪心，CF B - Sereja and Table

目录

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

二、解题报告

1、思路分析

2、复杂度

3、代码详解

---

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

B - Sereja and Table

---

二、解题报告

1、思路分析

    合法矩阵: 任意相邻行列相同和相反

    我们可以进行 k 次 操作

    若 k < n，则若存在合法矩阵，一定有一行不用动
    我们枚举行,O(n * n * m)
    
    若 k > n，我们直接考虑第一列每个位置变不变
    2^n * n * m，（这里由于k很小所以n很小）

2、复杂度

时间复杂度： O(n^2 m) 或 O(2^k * n * m)空间复杂度：O(nm)

3、代码详解

 ​

#include <bits/stdc++.h>
#define sc scanf
using i64 = long long;
using PII = std::pair<int, int>;
constexpr int inf = 1e9 + 7;

void solve() {
    int n, m, k;
    std::cin >> n >> m >> k;
    int res = inf;
    if (n > k) {
        std::vector<std::bitset<100>> g(n);
        for (int i = 0; i < n; ++ i)
            for (int j = 0, a; j < m; ++ j)
                std::cin >> a, g[i][j] = a;
        for (int i = 0; i < n; ++ i) {
            int s = 0;
            for (int j = 0; j < n; ++ j) {
                if (i == j) continue;
                s += std::min((g[i] ^ g[j]).count(), ((~g[i]) ^ g[j]).count() - (100 - m));
            }
            if (s <= k)
                res = std::min(res, s);
        }
        
    }
    else {
        std::vector<std::bitset<100>> g(m);
        for (int i = 0; i < n; ++ i)
            for (int j = 0, a; j < m; ++ j)
                std::cin >> a, g[j][i] = a;
        for (int i = 0, ed = 1 << n; i < ed; ++ i) {
            std::bitset<100> t = std::bitset<100>(i);
            int s = (t ^ g[0]).count();
            
            for (int j = 1; j < m; ++ j) {
                s += std::min((t ^ g[j]).count(), ((~t) ^ g[j]).count() - (100 - n));
            }
            if (s <= k)
                res = std::min(res, s);
        }
    }
    if (res < inf) std::cout << res;
    else std::cout << -1;
}

int main() {
#ifdef DEBUG
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    std::ios::sync_with_stdio(false), std::cin.tie(nullptr), std::cout.tie(nullptr);
    int _ = 1;
    // std::cin >> _;
    while (_ --)
        solve();
    return 0;
}

原文地址：https://blog.csdn.net/EQUINOX1/article/details/140571540

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！