80分求助
查看原帖
80分求助
107156
lqr2018楼主2021/10/23 09:38
#include<bits/stdc++.h>
#define maxn 21
#define maxm 1050625
using namespace std;
int n;
int cnt,ans;
int op[maxn], ch[maxn], g[maxm];
int read(){
	char ch = getchar();
	int s = 0, f = 1;
	while(ch < '0' || ch > '9'){
		if(ch == '-')
			f = -1;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9'){
		s = s*10 + (int)(ch - '0');
		ch = getchar();
	}
	return s*f;
}
void print(){
	cout<<"        12345"<<endl;
	for(int i = 1;i <= n;i++){
		cout<<"ch["<<i<<"] = ";
		int x = ch[i];
		while(x > 0){
			cout<<x%2;
			x/=2;
		}
		cout<<endl;
	}
	for(int i = 1;i <= n;i++){
		cout<<"op["<<i<<"] = ";
		int x = op[i];
		while(x > 0){
			cout<<x%2;
			x/=2;
		}
		cout<<endl;
	}
	for(int i = 1;i <= ((1 << n) - 1);i++){
		if(i < 10)
			cout<<" g["<<i<<"] = ";
		else 
			cout<<"g["<<i<<"] = ";
		int x = g[i];
		while(x > 0){
			cout<<x%2;
			x/=2;
		}
		cout<<endl;
	}
}
int main(){
	n = read();
	int s, t;
	for(int i = 1;i <= n;i++){
		s = read();
		for(int j = 1;j <= s;j++){
			t = read();
			if(t == i)
				continue; 
			op[i] |= 1 << (t-1);
		}
		ch[i] = op[i];
	}
	ans = 500;
	t = (1 << n) - 1;
	//print();
	for(int i = 1;i <= n;i++){
		ch[i] = ch[i] ^ (1 << (i-1));
		for(int j = 1;j <= n;j++){
			if( (op[i] & (1 << (j-1) ) ) == 0)
				continue;
			//if(i == j) 
			//	continue;
			ch[i] = ch[i] ^ op[j];
			//cout<<"================="<<endl;
			//cout<<"i = "<<i<<"  j = "<<j<<endl;
			//print();
		}
	}	
	for(int i = 0;i <= t;i++){
		for(int j = 1;j <= n;j++){
			if( (i & (1 << (j-1) ) ) != 0) 
				continue;
			g[i | ( 1 << (j-1))] = g[i] ^ ch[j];
			/*cout<<"================="<<endl;
			cout<<"i = "<<i<<" j = "<<j<<endl;
			print();*/
		}
	}
	//print();
	for(int i = 0;i <= t;i++){
		if(g[i] == t){
			cnt = 0;			for(int j = 1;j <= n;j++){
				if( (i & (1 << (j-1) ) ) != 0){
					cnt++;
				}
			}
			ans = min(ans, cnt);
		}
	}

	if(ans > n) 
		cout<<"‘Change an alarm clock,please!’";
	else 
		cout<<ans;
	return 0;
}
2021/10/23 09:38
加载中...