小X与神牛（dfs）

小X与神牛

时间限制: 1 Sec 内存限制: 128 MB

题目描述

小X在野外遇到了一种神奇的牛，并将其命名为“神牛”。
神牛都长着B只角，B只角从左到右在头顶上排成一排。每只角上都标着数字，不是0就是1。小X将每头神牛的B只角上的数字从左到右依次取出，组成一个只含0或1的B位二进制数。小X将这个二进制数转化为十进制，用这个十进制数来代表一头神牛，这个十进制就是这头神牛的编号。
神牛们之间的关系是很微妙的，如果两头神牛的第i只角上的数字不同，则称这两头神牛的第i只角是不一样的。如果两头神牛不同的角的数目大于等于D，则称这两头神牛是友好的。比如当B=8，D=2时，
01010100
00110100
xx
这两头神牛的第2和第3只角不同(x指向的位置)，不同的角的数目为2，所以这两头神牛是友好的。
现在小X向你求助：请找出N头神牛，使得任意两头神牛都是友好的，并将这N头神牛的编号按从小到大排序后依次输出。如果有多种符合条件的解，那么排在越前面的牛的编号越小越好。

输入

输入仅有一行包含3个用空格隔开的正整数，分别表示 N, B, D。

输出

输出仅有一行包含N个非负整数，相邻两个数之间用一个空格隔开，表示N头神牛的编号。如果有多解，你的程序要输出这样的解：越前面的牛的编号越小越好。

样例输入

复制样例数据

3 5 3

样例输出

0 7 25

提示

每头神牛都长着7只角，若两头神牛不同的角的数目大于等于3，则这两头神牛是友好的。现在要找出16头相互都友好的神牛。
答案是0000000, 0000111, 0011001, 0011110, 0101010, 0101101, 0110011, 0110100, 1001011, 1001100, 1010010, 1010101, 1100001, 1100110, 1111000, 1111111，转化为十进制就是0 7 25 30 42 45 51 52 75 76 82 85 97 102 120 127

对于30%的数据，1<=D<=B<=8，1<=N<=3
对于另外10%的数据，D=1
对于另外30%的数据，D=2
对于100%的数据，1<=D<=B<=8, 1<=N<=16
数据保证有解。

首先题目要求值越小越好，那么就从0开始。用字符串存储长度为B的二进制，然后从第一位到第b位枚举一遍，为了使不相同的值越多，那么不相同的位数从d位开始，所以dfs时每一位从0开始，然后再为1。。。

最后存储比较完事。

/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>

typedef long long LL;
using namespace std;

int n, b, d, ans[20], num;
string s[1005];

int pow(int x, int nu){
	int res = 1;
	for (int i = 0; i < nu; i++) res *= x;
	return res;
}

void dfs(int len, string str){
	if(len == b){
		int f = 0;
		for (int i = 0; i < num; i++){//与已有的答案进行比较，如果不同的值大于d存储
			int nu = 0;
			for (int j = 0; j < b; j++){
				if(s[i][j] != str[j]) nu++;
			}
			if(nu < d){f = 1; break;}
		}
		if(!f) s[num++] = str;
		return ;
	}
	for (int i = 0; i <= 1; i++) dfs(len + 1, str + (char)('0' + i));
}

int main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);

	scanf("%d %d %d", &n, &b, &d);
	for (int i = 1; i <= b; i++) s[0] += '0';
	num = 1;
	dfs(0, "");
	for (int i = 0; i < num; i++){//每个数转化成10进制
		int num = 0;
		for (int j = 0; j < b; j++){
			num += (s[i][j] - '0') * pow(2, b - j - 1);
		}
		ans[i] = num;
	}
	sort(ans, ans + num);//从小到大排序
	for (int i = 0; i < n; i++) printf("%d ", ans[i]);

	return 0;
}
/**/