自动搬运

查看原文

来自洛谷，原作者为

	jinfanhao 最后在线时间: 2025/6/30 17:25

搬运于2025-08-24 22:58:07，当前版本为作者最后更新于2024-12-27 22:37:54，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这道题是道很好的二进制枚举练习题。
我们可以发现你一个手柄，无论操作只要重复了，就抵消掉了。
这样我们可以用一个二进制数 $i$ 来表示操作方案，如果这一位是 1，那么就是可以操作，否则就是不操作。

#include<bits/stdc++.h>
using namespace std;
char ch[5][5];
int op[5][5],f,minx=INT_MAX,ans;
signed main(){
	for(int i=1; i<=4; ++i){
		for(int j=1; j<=4; ++j){
			cin >> ch[i][j];
			if(ch[i][j]=='-')op[i][j]=1;
			if(ch[i][j]=='+')op[i][j]=0;
		}
	}
	for(int i=0; i<(1<<16); ++i){
		int sum=0;
		for(int j=1; j<=16; ++j){
			if(i&(1<<(j-1))){
				++sum;
				int x=(j-1)/4+1,y=j%4;
				if(!y)y=4;
				for(int k=1; k<=4; ++k){
					op[x][k]^=1;
					op[k][y]^=1;
				}
				op[x][y]^=1;
			}
		}
		bool ok=true;
		for(int j=1; j<=4; ++j){
			for(int k=1; k<=4; ++k){
				if(!op[j][k]){
					ok=false;
					break;
				}
			}
			if(!ok)break;
		}
		if(ok && sum<minx){
			minx=sum;
			ans=i;
		}
		for(int j=1; j<=16; ++j){
			if(i&(1<<(j-1))){
				++sum;
				int x=(j-1)/4+1,y=j%4;
				if(!y)y=4;
				for(int k=1; k<=4; ++k){
					op[x][k]^=1;
					op[k][y]^=1;
				}
				op[x][y]^=1;
			}
		}
	}
	printf("%d",minx);
	for(int i=1; i<=16; ++i){
		if(ans&(1<<(i-1))){
			int x=(i-1)/4+1,y=i%4;
			if(!y)y=4;
			printf("\n%d %d",x,y);
		}
	}
	return 0;
}