自动搬运

查看原文

来自洛谷，原作者为

	Purslane AFO

搬运于2025-08-24 22:59:08，当前版本为作者最后更新于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;
}