蓝桥杯 - 算法训练黑白无常 C语言实现

2019-11-06 07:32:03

字体：大中小

来源：转载

供稿：网友

算法训练黑白无常

题目：（蓝桥杯测试数据有误）问题描述　　某寝室的同学们在学术完之后准备玩一个游戏：游戏是这样的，每个人头上都被贴了一张白色或者黑色的纸，现在每个人都会说一句话“我看到x张白色纸条和y张黑色的纸条”，又已知每个头上贴着白色纸的人说的是真话、每个头上贴着黑色纸的人说的是谎话，现在要求你判断哪些人头上贴着的是白色的纸条，如果无解输出“NoSolution.”；如果有多组解，则把每个答案中贴白条的人的编号按照大小排列后组成一个数（比如第一个人和第三个人头上贴着的是白纸条，那么这个数就是13；如果第6、7、8个人都贴的是白纸条，那么这个数就是678）输出最小的那个数（如果全部都是黑纸条也满足情况的话，那么输出0）输入格式　　第一行为一个整数n，接下来n行中的第i行有两个整数x和y，分别表示第i个人说“我看到x张白色纸条和y张黑色的纸条”。输出格式　　一行。如果无解输出“NoSolution.”。否则输出答案中数值（具体见问题描述）最小的那个，如果全部都是黑纸条也满足情况的话，那么输出0样例输入21 01 0样例输出0样例输入53 10 41 34 01 3样例输出35数据规模和约定　　n<=8分析：首先说一下，蓝桥杯的测试数据有误，又事一个坑。一开始得分是20，后来改进了到70分，小编本想不看答案做到100的，但有上次的经历后还是觉得看一下。发现答案下载不了，在网上差了一下发现第三组数据是错的。数据规模不大，直接深度暴力对于每个人有两种情况，黑和白，对于所有猜测进行判断。代码在此：

#include<stdio.h>#define SIZE 8int n;int data[SIZE][2];	//使用SIZE * 2存储数据 int v[SIZE];	//记录黑白  白1 和 黑0 int yes[SIZE];int ifz = 0;	//全局判断是否有0 （如果全部都是黑纸条也满足情况的话，那么输出0） void judge () {		int i;	int t = 0,f = 0;	int judge = 0;	//记录该猜测有几组数据对的上 	for(i = 0; i < n; i ++){	//当前猜测下的白的人数，黑的人数 		if(v[i] == 1){			t ++;		} else {			f ++;		}	}		int ifZero = 1;	//判断是否在全部为黑的时候也通过 （如果全部都是黑纸条也满足情况的话，那么输出0）	for(i = 0; i < n; i ++){	//当前预测下各组数是否满足要求 		if(v[i] == 1){	//当前预测下的i+1组数为白是否满足 			if(data[i][0] == t-1 && data[i][1] == f)				judge ++;			ifZero = 0;	//一旦有白就不可能有0 （如果全部都是黑纸条也满足情况的话，那么输出0）		} else {	//当前预测下的i+1组数为黑否满足			if(data[i][0] != t || data[i][1] != f-1)				judge ++;		}	}		if(judge == n){	//该猜测正确 		if(ifZero == 1){	//判断是否有0 （如果全部都是黑纸条也满足情况的话，那么输出0）			ifz = 1;		}		for(i = 0; i < n; i ++){	//记录可能的组数 			if(v[i] == 1)				yes[i] = 1;		}	}	}void fun (int k) {		if(k > n-1){	//k为0开始循环全部，每个人有两种可能，两个分支 (0 - 4 )		judge();		return ;	}		fun(k+1);	//k+1 为假 (0 - 4 )		v[k] = 1;	fun(k+1);	//k+1 为真 （0 - 4 ） 	v[k] = 0;}int main () { 		int i,j;		scanf("%d", &n);	for(i = 0; i < n; i ++){		scanf("%d%d", &data[i][0], &data[i][1]);	}		for(i = 0; i < n; i ++){	//初始化 		yes[i] = 0;	}	/*	n = 5;	//测试数据 	data[0][0] =  3; 	data[0][1] =  1; 	data[1][0] =  0; 	data[1][1] =  4; 	data[2][0] =  1; 	data[2][1] =  3; 	data[3][0] =  4; 	data[3][1] =  0; 	data[4][0] =  1; 	data[4][1] =  3; */	fun(0);		if(ifz == 1){	//有0（如果全部都是黑纸条也满足情况的话，那么输出0） 		PRintf("0");	} else {		int temp = 0;	//判断是否无解 		for(i = 0; i < n; i ++){	//将记录的数依次输出 			if(yes[i] == 1)				printf("%d",i+1);			temp = 1;		}				if(temp == 0){			printf("NoSolution");		}	} 		return 0;}

上一篇：sdut 1299 最长上升子序列

下一篇：Lua 环境在Linux上的安装