自动搬运

查看原文

来自洛谷，原作者为

	Mobius127 Countless stars are like dust

搬运于2025-08-24 21:44:19，当前版本为作者最后更新于2020-12-26 22:13:27，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

传送门

$link$

什么叫暴力出奇迹啊(狗头

看到$N \leqslant20$ 直接暴力$Food$ $Filled$，填完之后$O(nm)$检查是否可行即可。

主程序：

void dfs(int k){
	if(k>n){
		bool flag=true;
		int s=0;
		for(int i=1; i<=m; i++){
			s=0;
			for(int j=1; j<=n; j++){
				if(str[i][j]=='1'){
					s+=u[j];
				} 
			}
			if(s!=sum[i]) flag=false;
		}
		if(flag){
			ans++;
			for(int i=1; i<=n; i++) Ans[i]=u[i];
		} 
		return ;
	}
	dfs(k+1);u[k]=1;dfs(k+1);u[k]=0;
} 

交完仔细分析，欸这复杂度不对啊。

$O(2^n*nm)=O(2^{20}*20*100)> O(10^{9})$ 妥妥的超时。

bfs思考了一会儿后，找到了这个东西：

exit(0);

能直接结束整个程序的运行。

好东西啊！

可还是超时了。别打

思考剪枝，只要有1个不符合匹配，就可以直接$break$。

于是复杂度就大大降低了。

AC Code:

#include <stdio.h>
#include <algorithm>
#define N 1005
using namespace std;
int n, m, u[N], ans, Ans[N];
char str[N][N];int sum[N];
void dfs(int k){
	if(k>n){
		bool flag=true;
		int s=0;
		for(int i=1; i<=m; i++){
			s=0;
			for(int j=1; j<=n; j++){
				if(str[i][j]=='1'){
					s+=u[j];
				} 
			}
			if(s!=sum[i]){
				flag=false;
				break;
			} 
		}
		if(flag){
			ans++;
			if(ans>1){
				printf("NOT UNIQUE");
				exit(0);
			}
			for(int i=1; i<=n; i++) Ans[i]=u[i];
		} 
		return ;
	}
	dfs(k+1);u[k]=1;dfs(k+1);u[k]=0;
} 
int main(){
	scanf("%d%d", &n, &m);
	for(int i=1; i<=m; i++) scanf("%s%d", str[i]+1, &sum[i]);
	dfs(1);
	if(ans==0) printf("IMPOSSIBLE");
	else for(int i=1; i<=n; i++) printf("%d", Ans[i]);
	return o;
}