P7315 [COCI2018-2019#3] Sajam

Bronya18C · 2022-09-17 11:52:19 · 题解

由于本题原唯一题解是错误的贪心，现提供一种有正确性证明的方法。

给一个 n \times n 的 01 矩阵，每次使一行或一列状态反转，问能否用若干次操作后使得最终矩阵的 1 的个数 \le k。

本题关键条件为 k \le n，不运用此条件我们的贪心无从下手。

这里我们分成两类情况：

• k<n

  因为我们最多使用 k 次操作 3 将原矩阵 1 变为 0，所以经过操作 1 或 2 后的矩阵 1 的个数 g 满足 g \le k \lt n 。

  运用鸽巢原理可知 n 行里至少有一行全为 0。

  我们枚举全为 0 的行，然后我们发现对于当前情况，每一列的操作情况是固定的。

  由于操作为一整行或列反转，因此每一列或行操作次数要么是 0 要么是 1，否则可以等价于 0 或 1。

  现在我们固定了一行 i，规定它最终一定要是 0，则对于每一列 j，a_{i,j}=0 则这一列不操作，否则 a_{i,j}=1 一定要操作。

  然后我们对其他行进行列的操作（其实相当于异或上 a_i ），然后每一行最后可以进行贪心是否反转，因为列已经固定，且此行的操作不会对其他行有影响。

  即对于每个枚举的行 i 统计 ans_i=\sum\limits_{j\not=i} {\min \{\sum_{l=1}^{n}{a_{i,l} \oplus a_{j,l}} , n-\sum_{l=1}^{n}{a_{i,l} \oplus a_{j,l}}\}}（其中 \oplus 表示异或）。

  最后看是否存在一行 i，满足 ans_i \le k。

  暴力枚举 i,j,l 是 \mathcal O(n^3) 的。

  用 bitset 优化可做到 \mathcal O(\dfrac{n^3}{w}) 。

• k=n

  同理，我们首先判断是否能够存在至少有一行全为 0 的解，同 k<n 的情况。

  但 k=n 可能会存在最终每一行恰好都有一个 1 的解。

  我们枚举第一行的哪一位是 1，然后先将其异或上 1（相当于提前用一次操作 3），此时最终第一行就是全为 0 了。

  此时用了一次操作 3，相当于 k=n-1，将第 1 行行当作 k<n 情况中的全为 0 的那行 i 进行求解即可。

  枚举第一行的某一位复杂度为 \mathcal O(n)，再枚举剩下的每行每位复杂度为 \mathcal O(n^2)，再用 bitset 优化同样可以做到 \mathcal O(\dfrac{n^3}{w})。

总时间复杂度 \mathcal O(\dfrac{n^3}{w})。

int n,k;
bitset<1005>st[1005];
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){
        char s[1005];
        scanf("%s",s+1);
        for(int j=1;j<=n;j++)
            if(s[j]=='o')st[i][j]=1;
    }
    if(k==n){
        for(int i=1;i<=n;i++){
            st[1].flip(i);
            bool chk=false;
            for(int j=2;j<=n;j++){
                st[j]=st[1]^st[j];
                if(min(st[j].count(),n-st[j].count())>1){
                    chk=true;st[j]=st[1]^st[j];
                    break;
                }
                st[j]=st[1]^st[j];
            }
            if(!chk){
                puts("DA");
                return 0;
            }
            st[1].flip(i);
        }
    }
    for(int i=1;i<=n;i++){
        int sum=0;
        for(int j=1;j<=n;j++){
            if(i==j)continue;
            st[j]=st[j]^st[i];
            sum+=min(st[j].count(),n-st[j].count());
            st[j]=st[j]^st[i];
        }
        if(sum<=k){
            puts("DA");
            return 0;
        }
    }
    puts("NE");
    return 0;
}