期末练习赛 构造数列 数学+模拟（兰福德数列）「建议收藏」

题目描述 给你 2N 个整数，它们是 1，1，2，2，3，3，……，N-1，N-1，N，N（也就是1 到 N 之
间的每个数字都有一对）。现在请你构造一个数列，要求数列中值为 X 的两个数之间恰好有
X 个数字。
输入格式 一行，一个整数 N。
输出格式 如果能构造出满足条件的数列，则输出该数列，以空格做间隔，如果有多种可行方案，输
出字典序最大的那一种；
如果无解，则输出“No”。
输入样例 输入样例 1 输入样例 2 样例输入 3
3 4 7
输出样例 输出样例 1 输出样例 2 样例输出 3
3 1 2 1 3 2 4 1 3 1 2 4 3 2 7 4 1 5 1 6 4 3 7 5 2 3 6 2
数据范围 对于 20%的数据：可能无解
对于 100%的数据：1<=N<=76.
样例说明 样例 1 说明：
一对”3”之间恰好有3 个数字 3 1 2 1 3
一对”2”之间恰好有2 个数字 2 1 3 2

一对”1”之间恰好有1 个数字 1 2 1

本题看后，感觉没什么思路，不像贪心、动归等等算法，那么就只能搜索了，再看看数据范围：N<=76，会不会超啊？曾经不是给大家说，搜索不是一般小于30吗？这次有点大哦~

但是仔细想想，这次好像有很多可以剪枝的地方：

1、  每个数肯定只用用一次；

2、  一个位置确定了，肯定也就确定了另外一个位置，如果那个位置已经有数了，那么也得减掉；

3、  如果找到一组解了，立即停止；（此处有个细节不知道大家看到没有，题目中提到，有多组解的时候，输出字典序最大的那组，那么是不是多组解的时候我们应该将所有解全部求出，再比较下，再输出呢？这样就超时了！字典序大的怎么出来？让大的数在前面不就ok了？所以细节就是，我们填数字的时候，应该从大的数开始填起）

而且只有n%4>=2时才有解，证略，下次有空再证…

于是我选择打表…

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
int data[200],vis[200],num,f;
bool yz(int n)
{
	int i,z[200]={0};
	for(i=1;i<=n;i++)if(!vis[i])return 0;
	for(i=1;i<=2*n;i++)
	{
		if(!z[data[i]])
		{
			z[data[i]]=1;
			if(data[i]!=data[i+data[i]+1])return 0;
		}
	}
	return 1;
}
void dfs(int p)
{
	if(p>=2*num)
	{
		if(yz(num))f=1;
		return;
	}
	if(f)return;
	int i,j;
	while(data[p])p++;
	if(p>=2*num)
	{
		if(yz(num))f=1;
		return;
	}
	for(i=num-1;i>=1;i--)
	{
		if(!vis[i])
		{
			if(p+i+1>2*num)continue;
			if(data[p+i+1])continue;
			data[p]=data[p+i+1]=i;
			vis[i]=1;
			dfs(p+1);
			if(f)return;
			vis[i]=0;
			data[p]=data[p+i+1]=0;
		}
	}
	return;
}
int main()
{
	int n,i;
	freopen("打表.txt","w",stdout);
	for(num=1;num<=76;num++)
	{
		memset(data,0,sizeof(data));
		memset(vis,0,sizeof(vis));
		data[1]=data[2+num]=num;
		vis[num]=1;
		f=0;
		if((num-1)%4>=2)dfs(2);//这一句加了就不会超时了 
		if(f)
		{
			printf("\"");
			for(i=1;i<=2*num;i++)printf("%d ",data[i]);
			printf("\",");
			printf("\n");
		}
		else printf("\"No\",\n");
	}
}

这是我的表….

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
char s[76][500]={"No",
"No",
"3 1 2 1 3 2 ",
"4 1 3 1 2 4 3 2 ",
"No",
"No",
"7 4 1 5 1 6 4 3 7 5 2 3 6 2 ",
"8 6 4 2 7 5 2 4 6 8 3 5 7 1 3 1 ",
"No",
"No",
"11 9 7 5 10 2 6 8 2 5 7 9 11 6 4 10 8 3 1 4 1 3 ",
"12 10 11 6 4 5 9 7 8 4 6 5 10 12 11 7 9 8 3 1 2 1 3 2 ",
"No",
"No",
"15 13 14 10 8 6 4 2 11 12 2 4 6 8 10 13 15 14 9 7 11 3 12 5 1 3 1 7 9 5 ",
"16 14 15 11 9 7 13 4 2 12 10 2 4 7 9 11 14 16 15 8 13 10 12 5 6 1 3 1 8 5 3 6 ",
"No",
"No",
"19 17 18 14 12 16 9 7 5 15 2 11 13 2 5 7 9 12 14 17 19 18 16 11 10 15 13 8 3 4 6 1 3 1 4 10 8 6 ",
"20 18 19 15 13 17 10 8 16 5 2 14 11 2 12 5 8 10 13 15 18 20 19 17 11 16 14 12 9 7 3 4 6 1 3 1 4 7 9 6 ",
"No",
"No",
"23 21 22 18 16 20 13 19 10 8 6 2 17 15 2 12 14 6 8 10 13 16 18 21 23 22 20 19 12 15 17 14 11 9 7 4 1 3 1 5 4 3 7 9 11 5 ",
"24 22 23 19 17 21 14 20 11 9 7 18 4 1 16 1 15 4 7 9 11 14 17 19 22 24 23 21 20 13 18 16 15 12 10 5 3 6 8 2 3 5 2 13 6 10 12 8 ",
"No",
"No",
"27 25 26 22 20 24 17 23 14 12 21 9 7 19 4 2 18 16 2 4 7 9 12 14 17 20 22 25 27 26 24 23 21 19 16 18 15 13 11 8 6 3 10 5 1 3 1 6 8 5 11 13 15 10 ",
"28 26 27 23 21 25 18 24 15 13 22 10 8 20 5 1 19 1 16 17 5 8 10 13 15 18 21 23 26 28 27 25 24 22 20 16 19 17 14 12 9 7 2 11 3 2 4 6 3 7 9 4 12 14 6 11 ",
"No",
"No",
"31 29 30 26 24 28 21 27 18 16 25 13 11 23 8 22 3 1 20 1 3 19 17 8 11 13 16 18 21 24 26 29 31 30 28 27 25 23 22 20 17 19 15 12 14 9 6 4 2 7 10 2 4 6 5 9 12 7 15 14 5 10 ",
"32 30 31 27 25 29 22 28 19 17 26 14 12 24 9 23 6 4 21 1 20 1 4 6 9 12 14 17 19 22 25 27 30 32 31 29 28 26 24 23 21 20 18 16 13 11 8 15 7 2 3 10 2 5 3 8 7 11 13 5 16 18 10 15 ",
"No",
"No",
"35 33 34 30 28 32 25 31 22 20 29 17 15 27 12 26 9 7 24 4 2 23 21 2 4 7 9 12 15 17 20 22 25 28 30 33 35 34 32 31 29 27 26 24 21 23 19 16 18 13 14 10 5 1 6 1 3 11 5 8 3 6 10 13 16 14 19 18 8 11 ",
"36 34 35 31 29 33 26 32 23 21 30 18 16 28 13 27 10 8 25 5 3 1 24 1 3 5 8 10 13 16 18 21 23 26 29 31 34 36 35 33 32 30 28 27 25 22 20 24 17 19 14 12 9 7 4 15 6 2 11 4 2 7 9 6 12 14 17 20 22 19 11 15 ",
"No",
"No",
"39 37 38 34 32 36 29 35 26 24 33 21 19 31 16 30 13 11 28 8 27 5 3 1 25 1 3 5 8 11 13 16 19 21 24 26 29 32 34 37 39 38 36 35 33 31 30 28 27 23 25 22 18 15 20 14 9 7 17 2 6 10 2 4 12 7 9 6 4 15 14 18 10 23 22 20 17 12 ",
"40 38 39 35 33 37 30 36 27 25 34 22 20 32 17 31 14 12 29 9 28 6 4 2 26 24 2 4 6 9 12 14 17 20 22 25 27 30 33 35 38 40 39 37 36 34 32 31 29 28 24 26 23 21 19 16 13 15 10 18 5 3 1 7 1 3 5 11 8 10 13 7 16 15 19 21 23 8 18 11 ",
"No",
"No",
"43 41 42 38 36 40 33 39 30 28 37 25 23 35 20 34 17 15 32 12 31 9 7 29 4 1 27 1 26 4 7 9 12 15 17 20 23 25 28 30 33 36 38 41 43 42 40 39 37 35 34 32 31 29 27 26 24 22 19 16 21 13 14 6 3 5 18 11 3 2 6 5 2 10 8 13 16 14 19 11 22 24 21 8 10 18 ",
"44 42 43 39 37 41 34 40 31 29 38 26 24 36 21 35 18 16 33 13 32 10 8 30 5 3 1 28 1 3 5 8 10 13 16 18 21 24 26 29 31 34 37 39 42 44 43 41 40 38 36 35 33 32 30 27 28 23 25 22 19 17 15 12 9 20 6 4 2 7 14 2 4 6 9 11 12 7 15 17 19 23 22 27 25 14 20 11 ",
"No",
"No",
"47 45 46 42 40 44 37 43 34 32 41 29 27 39 24 38 21 19 36 16 35 13 11 33 8 6 31 3 1 30 1 3 6 8 11 13 16 19 21 24 27 29 32 34 37 40 42 45 47 46 44 43 41 39 38 36 35 33 31 28 30 25 26 22 20 18 23 15 12 10 7 2 4 5 2 17 14 4 7 5 10 12 9 15 18 20 22 25 28 26 23 14 9 17 ",
"48 46 47 43 41 45 38 44 35 33 42 30 28 40 25 39 22 20 37 17 36 14 12 34 9 7 32 4 2 31 29 2 4 7 9 12 14 17 20 22 25 28 30 33 35 38 41 43 46 48 47 45 44 42 40 39 37 36 34 32 29 31 27 24 26 23 19 16 18 15 10 6 3 21 5 1 3 1 6 13 5 10 11 8 16 15 19 18 24 23 27 26 8 13 11 21 ",
"No",
"No",
"51 49 50 46 44 48 41 47 38 36 45 33 31 43 28 42 25 23 40 20 39 17 15 37 12 10 35 7 34 3 1 32 1 3 30 7 10 12 15 17 20 23 25 28 31 33 36 38 41 44 46 49 51 50 48 47 45 43 42 40 39 37 35 34 32 30 29 27 24 22 26 19 21 16 13 5 6 2 8 4 2 5 18 6 4 14 11 8 13 9 16 19 22 24 21 27 29 26 11 9 14 18 ",
"52 50 51 47 45 49 42 48 39 37 46 34 32 44 29 43 26 24 41 21 40 18 16 38 13 11 36 8 35 5 3 1 33 1 3 5 8 11 13 16 18 21 24 26 29 32 34 37 39 42 45 47 50 52 51 49 48 46 44 43 41 40 38 36 35 31 33 30 27 25 28 22 20 17 15 12 23 9 6 4 2 7 19 2 4 6 14 9 12 7 15 17 10 20 22 25 27 31 30 28 23 14 19 10 ",
"No",
"No",
"55 53 54 50 48 52 45 51 42 40 49 37 35 47 32 46 29 27 44 24 43 21 19 41 16 14 39 11 38 8 6 36 3 1 34 1 3 6 8 11 14 16 19 21 24 27 29 32 35 37 40 42 45 48 50 53 55 54 52 51 49 47 46 44 43 41 39 38 36 34 33 31 28 26 30 23 25 20 18 15 13 9 4 5 7 2 22 4 2 5 17 9 7 12 13 15 10 18 20 23 26 28 25 31 33 30 12 10 17 22 ",
"56 54 55 51 49 53 46 52 43 41 50 38 36 48 33 47 30 28 45 25 44 22 20 42 17 15 40 12 39 9 7 37 4 1 35 1 34 4 7 9 12 15 17 20 22 25 28 30 33 36 38 41 43 46 49 51 54 56 55 53 52 50 48 47 45 44 42 40 39 37 35 34 32 29 31 26 27 23 21 19 16 14 11 8 5 24 6 10 2 18 5 2 8 6 11 13 14 16 10 19 21 23 26 29 27 32 31 3 18 13 24 3 ",
"No",
"No",
"59 57 58 54 52 56 49 55 46 44 53 41 39 51 36 50 33 31 48 28 47 25 23 45 20 18 43 15 42 12 10 40 7 5 3 1 38 1 3 5 7 10 12 15 18 20 23 25 28 31 33 36 39 41 44 46 49 52 54 57 59 58 56 55 53 51 50 48 47 45 43 42 40 37 35 38 32 34 29 27 24 22 30 19 21 14 8 11 4 6 26 2 9 4 2 8 6 16 17 11 14 13 9 19 22 24 21 27 29 32 35 37 34 30 16 13 17 26 ",
"60 58 59 55 53 57 50 56 47 45 54 42 40 52 37 51 34 32 49 29 48 26 24 46 21 19 44 16 43 13 11 41 8 6 39 3 1 38 1 3 6 8 11 13 16 19 21 24 26 29 32 34 37 40 42 45 47 50 53 55 58 60 59 57 56 54 52 51 49 48 46 44 43 41 39 36 38 35 31 28 33 27 23 20 30 25 18 14 12 9 4 5 7 2 22 4 2 5 17 9 7 12 14 15 20 18 23 10 28 27 31 25 36 35 33 30 17 22 10 15 ",
"No",
"No",
"63 61 62 58 56 60 53 59 50 48 57 45 43 55 40 54 37 35 52 32 51 29 27 49 24 22 47 19 46 16 14 44 11 9 42 6 41 3 1 39 1 3 6 9 11 14 16 19 22 24 27 29 32 35 37 40 43 45 48 50 53 56 58 61 63 62 60 59 57 55 54 52 51 49 47 46 44 42 41 39 38 36 34 31 28 30 33 26 23 21 18 15 13 10 4 5 8 12 25 4 7 5 20 17 10 8 13 15 7 18 12 21 23 28 26 31 30 34 36 38 33 17 2 20 25 2 ",
"64 62 63 59 57 61 54 60 51 49 58 46 44 56 41 55 38 36 53 33 52 30 28 50 25 23 48 20 47 17 15 45 12 10 43 7 42 4 1 40 1 39 4 7 10 12 15 17 20 23 25 28 30 33 36 38 41 44 46 49 51 54 57 59 62 64 63 61 60 58 56 55 53 52 50 48 47 45 43 42 40 39 37 35 32 29 34 26 27 22 31 21 18 16 11 6 3 9 5 8 3 24 6 14 5 19 11 9 8 13 16 18 22 21 26 29 27 32 14 35 37 34 31 13 2 19 24 2 ",
"No",
"No",
"67 65 66 62 60 64 57 63 54 52 61 49 47 59 44 58 41 39 56 36 55 33 31 53 28 26 51 23 50 20 18 48 15 13 46 10 45 7 5 3 1 43 1 3 5 7 10 13 15 18 20 23 26 28 31 33 36 39 41 44 47 49 52 54 57 60 62 65 67 66 64 63 61 59 58 56 55 53 51 50 48 46 45 42 40 43 37 35 38 32 30 27 25 34 22 24 19 12 9 11 6 4 2 29 8 2 4 6 9 21 12 11 17 8 14 16 19 22 25 27 24 30 32 35 37 40 42 38 34 14 17 21 16 29 ",
"68 66 67 63 61 65 58 64 55 53 62 50 48 60 45 59 42 40 57 37 56 34 32 54 29 27 52 24 51 21 19 49 16 14 47 11 46 8 6 44 3 1 43 1 3 6 8 11 14 16 19 21 24 27 29 32 34 37 40 42 45 48 50 53 55 58 61 63 66 68 67 65 64 62 60 59 57 56 54 52 51 49 47 46 44 41 43 38 39 35 33 31 36 28 26 23 20 22 17 13 9 10 5 30 4 12 7 25 5 4 9 18 10 13 7 15 17 20 12 23 22 26 28 31 33 35 38 41 39 36 18 15 2 25 30 2 ",
"No",
"No",
"71 69 70 66 64 68 61 67 58 56 65 53 51 63 48 62 45 43 60 40 59 37 35 57 32 30 55 27 54 24 22 52 19 17 50 14 49 11 9 47 6 46 3 1 44 1 3 6 9 11 14 17 19 22 24 27 30 32 35 37 40 43 45 48 51 53 56 58 61 64 66 69 71 70 68 67 65 63 62 60 59 57 55 54 52 50 49 47 46 44 42 39 41 38 34 31 33 28 36 25 23 26 18 16 13 10 5 7 4 12 8 29 5 4 21 7 10 20 13 8 16 18 12 15 23 25 28 31 26 34 33 39 38 42 41 36 21 2 20 15 2 29 ",
"72 70 71 67 65 69 62 68 59 57 66 54 52 64 49 63 46 44 61 41 60 38 36 58 33 31 56 28 55 25 23 53 20 18 51 15 50 12 10 48 7 47 3 1 45 1 3 43 7 10 12 15 18 20 23 25 28 31 33 36 38 41 44 46 49 52 54 57 59 62 65 67 70 72 71 69 68 66 64 63 61 60 58 56 55 53 51 50 48 47 45 43 42 40 37 35 39 32 34 29 27 24 22 19 17 14 11 16 8 30 5 9 6 13 26 21 5 8 11 6 14 9 17 19 16 22 24 13 27 29 32 35 37 34 40 42 39 21 4 2 30 26 2 4 ",
"No",
"No",
"75 73 74 70 68 72 65 71 62 60 69 57 55 67 52 66 49 47 64 44 63 41 39 61 36 34 59 31 58 28 26 56 23 21 54 18 53 15 13 51 10 50 7 5 3 1 48 1 3 5 7 10 13 15 18 21 23 26 28 31 34 36 39 41 44 47 49 52 55 57 60 62 65 68 70 73 75 74 72 71 69 67 66 64 63 61 59 58 56 54 53 51 50 46 43 48 45 38 42 37 33 30 40 35 25 29 24 20 17 14 12 9 6 11 2 32 16 2 27 6 8 9 22 12 14 11 17 19 20 8 25 24 30 16 33 29 38 37 43 35 46 42 45 40 4 22 27 19 32 4 ",
"76 74 75 71 69 73 66 72 63 61 70 58 56 68 53 67 50 48 65 45 64 42 40 62 37 35 60 32 59 29 27 57 24 22 55 19 54 16 14 52 11 51 8 6 49 3 1 47 1 3 6 8 11 14 16 19 22 24 27 29 32 35 37 40 42 45 48 50 53 56 58 61 63 66 69 71 74 76 75 73 72 70 68 67 65 64 62 60 59 57 55 54 52 51 49 47 46 44 41 39 43 36 38 33 31 28 26 23 21 25 15 13 9 10 5 7 34 30 2 12 5 2 9 7 10 13 15 18 20 17 21 23 12 26 28 25 31 33 36 39 41 38 44 46 43 4 18 17 30 20 4 34 "
};
int main()
{
	int n;
	freopen("seq.in","r",stdin);
	freopen("seq.out","w",stdout);
	cin>>n;
	cout<<s[n-1];
}

 其实，这里有一个直接根据兰福德数列构造的方法，

今天的文章期末练习赛 构造数列 数学+模拟（兰福德数列）「建议收藏」分享到此就结束了，感谢您的阅读。