题目：http://poj.org/problem?id=1392
题目还是让求一个长度为2^n的01……序列串，使得每取n位所表示的二进制数能够表示0~2^n-1,这之间的所有数，不过题目要求输出的不是这个序列，而是这个序列按照每n个数取的时候，所取到的第k个数是多少。我是采取打表的办法存储所有结果，然后要哪个就直接查表0MS，不过感觉内存消耗有点多
代码：
#include<cstdio> #include<cstring> int record[16][33000]; int arr[33000]; int total[16], num; bool used[33000][2]; void DFS(int x, int n) { for(int i = 0; i < 2; ++ i) { if( !used[x][i]) { used[x][i] = 1; int s = (( x<<1) + i) % total[n-1];//扩展搜索，对每一个状态S它的下一个状态左移后加0和加1这两种 DFS(s, n); arr[num++] = i; } } } void init() { total[0] = 1; for(int n = 1; n <= 15; ++ n) { int t = 0;num = 0; total[n] = total[n-1]*2; memset(used, 0, sizeof(used)); memset(arr, 0, sizeof(arr)); DFS(0, n);//dfs搜索， num += n-1; for(int k = 0; k < total[n]; ++ k) { t = 0; num --; for(int i = 0; i < n; ++ i) {//结果的二进制数转换成十进制数 t = (t<<1) + arr[num - i]; } record[n][k] = t;//记录 } } } int main() { freopen("poj1392.txt", "r", stdin); int n, k; init();//在程序开始时就初始化得到所有结果 while(scanf("%d%d", &n, &k) && !(n == 0 && k == 0)) { printf("%d\n", record[n][k]); } return 0; } |