P7315 [COCI 2018/2019 #3] Sajam 题解

性质的必然存在性.jpg

注意到题目给出了十分特殊的性质 $\boldsymbol{k\le n}$ ，因此考虑从这个地方入手。

注意到当 $k<n$ 时，根据抽屉原理可知必然存在一个全 $0$ 行，因此考虑枚举该行，然后对于该行内每个 $1$ ，翻转该位置对应的列。此时剩下的行要么翻转要么不翻转，且这些行均独立。因此设此时第 $i$ 行有 $d_i$ 个 $1$ ，那么最少需要执行 $\sum\limits_{j\neq i}\min(d_j,n-d_j)$ （ $i$ 表示枚举的是第 $i$ 行全 $0$ ），容易发现这个东西可以用 bitset 优化到 $O(\frac {n^3}{\omega})$ 。列的情况同理。

而 $k=n$ 时唯一的特殊情况是每一行每一列都有恰好一个 $1$ 。此时考虑枚举第一行 $1$ 的位置，然后可以确定剩余位置全部为 $0$ ，转化为第一种情况，同样可以用 bitset 优化到 $O(\frac{n^3}{\omega})$ 。因此本题得解，总时间复杂度为 $O(\frac{n^3}{\omega})$ 可以通过。

代码十分好写。

// #pragma GCC optimize(3, "Ofast", "inline", "unroll-loops")
#include <bits/stdc++.h>
#define int long long
using namespace std;
using ld = long double;
const int N = 1010;
int f[N];
char s[N][N];
bitset<N> bit[N];
signed main()
{
    cin.tie(0)->sync_with_stdio(false);
    cout << fixed << setprecision(15);
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            cin >> s[i][j], bit[i - 1].set(j - 1, s[i][j] == 'o');
    if (n == k)
    {
        for (int i = 1; i <= n; ++i)
        {
            // s[1][i] = 1
            // s[1][j] = 0 (i != j)
            bit[0].flip(i - 1);
            int sum = 1;
            for (int j = 2; j <= n; ++j)
            {
                int cnt = bitset(bit[0] ^ bit[j - 1]).count();
                sum += min(cnt, n - cnt);
            }
            if (sum <= k)
            {
                cout << "DA\n";
                return 0;
            }
            bit[0].flip(i - 1);
        }
        for (int i = 1; i <= n; ++i)
        {
            int sum = 0;
            for (int j = 1; j <= n; ++j)
                if (i != j)
                {
                    int cnt = bitset(bit[i - 1] ^ bit[j - 1]).count();
                    sum += min(cnt, n - cnt);
                }
            if (sum <= k)
            {
                cout << "DA\n";
                return 0;
            }
        }
        cout << "NE\n";
    }
    else
    {
        for (int i = 1; i <= n; ++i)
        {
            int sum = 0;
            for (int j = 1; j <= n; ++j)
                if (i != j)
                {
                    int cnt = bitset(bit[i - 1] ^ bit[j - 1]).count();
                    sum += min(cnt, n - cnt);
                }
            if (sum <= k)
            {
                cout << "DA\n";
                return 0;
            }
        }
        cout << "NE\n";
    }
    return 0;
}

隐藏／恢复文章

随机文章