题解：P10554 [ICPC2024 Xi'an I] Turn Off The Lights

Purslane · 2024-06-03 07:35:00 · 题解

Solution

一个神秘做法。显然的操作不受影响。

那么我们本质是：选取一些行或列翻转，使得最后开着的灯的数量 \le k。

若 k<n，必然有一列被只通过行或列翻转变为全关着。这一列是否翻转已经确定了（只有两种，枚举），那么每一行是否翻转也是确定的。对于其他列，暴力扫一遍翻转还是不翻转更优，使用 bitset 加速。

若 k=n，那么第一列恰好有一个灯是开着的，枚举这盏灯。

容易发现一共只有 O(n) 种可能的翻转方式，而每次翻转需要 O(\dfrac{n^2}{\omega}) 判断。

复杂度 O(\dfrac{n^3}{\omega})。

#include<bits/stdc++.h>
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=1000+10;
int n,k,a[MAXN][MAXN];
bitset<1001> ver[MAXN],hor[MAXN];
int flg1[MAXN],flg2[MAXN];
void output(void) {
    vector<pair<int,int>> ans;
    ffor(i,1,n) if(flg1[i]) ans.push_back({i,0});
    ffor(i,1,n) if(flg2[i]) ans.push_back({0,i});
    ffor(i,1,n) ffor(j,1,n) if(a[i][j]^flg1[i]^flg2[j]) ans.push_back({i,j});
    cout<<ans.size()<<'\n';
    for(auto pr:ans) cout<<pr.first<<' '<<pr.second<<'\n';
    return ;
}
int main() {
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>k;
    ffor(i,1,n) ffor(j,1,n) cin>>a[i][j];
    ffor(i,1,n) ffor(j,1,n) hor[i][j]=a[i][j],ver[j][i]=a[i][j];
    //把第 i 行清干净 
    ffor(i,1,n) {
        memset(flg1,0,sizeof(flg1)),memset(flg2,0,sizeof(flg2));
        flg1[i]=0;
        bitset<1001> bt;
        ffor(j,1,n) if(a[i][j]) bt[j]=flg2[j]=1;
        int cnt=0;
        ffor(I,1,n) if(i!=I) {
            int sum=(hor[I]^bt).count();
            if(sum<=n-sum) cnt+=sum;
            else cnt+=n-sum,flg1[I]=1;  
        }
        if(cnt<=k) return output(),0;
        flg1[i]=1;
        ffor(j,1,n) if(a[i][j]) bt[j]=flg2[j]=0; else bt[j]=flg2[j]=1;
        cnt=0;
        ffor(I,1,n) if(i!=I) {
            int sum=(hor[I]^bt).count();
            if(sum<=n-sum) cnt+=sum;
            else cnt+=n-sum,flg1[I]=1;  
        }
        if(cnt<=k) return output(),0;
    }
    ffor(j,1,n) {
        memset(flg1,0,sizeof(flg1)),memset(flg2,0,sizeof(flg2));
        flg1[1]=0;
        bitset<1001> bt;
        ffor(J,1,n) if((J==1)^a[1][J]) bt[J]=flg2[J]=1;
        int cnt=1;
        ffor(I,2,n) {
            int sum=(hor[I]^bt).count();
            if(sum<=n-sum) cnt+=sum;
            else cnt+=n-sum,flg1[I]=1;  
        }
        if(cnt<=k) return output(),0;
        flg1[1]=1;

        ffor(J,1,n) if((J==1)^a[1][J]) bt[J]=flg2[J]=0; else bt[J]=flg2[J]=1;
        cnt=1;
        ffor(I,2,n) {
            int sum=(hor[I]^bt).count();
            if(sum<=n-sum) cnt+=sum;
            else cnt+=n-sum,flg1[I]=1;  
        }
        if(cnt<=k) return output(),0;
    }
    cout<<-1;
    return 0;
}