网站页面设计网页说明,软件工程项目案例,腾讯 微商 网站 建设,服务商平台正题 大意
一个数K#xff0c;求一个最长的01环形序列#xff08;头和尾相连#xff09;#xff0c;使得每个长度为k的连续子序列都不相同。#xff08;要输出这个串#xff0c;如果有多个答案输出字典序最小的#xff09; 解题思路
尝试将长度为k的01序列全排列一下我…正题 大意
一个数K求一个最长的01环形序列头和尾相连使得每个长度为k的连续子序列都不相同。要输出这个串如果有多个答案输出字典序最小的 解题思路
尝试将长度为k的01序列全排列一下我们会发现总共有2n2n2^n种排列那么其实这个序列长度很明显就是2n2n2^n。然后我们开始想一想如何输出队列。 首先每个序列只能也必须出现一次而每个序列后面都可以接上某些序列而最后又得回到最开始的序列。这么一看其实很像欧拉回路。所以我们可以用欧拉回路来求将每个排列作为一个点然后可以相接的连边。 连边方式 首先我们可以发现其实这个排列可以连接的下一个排列只有两种情况就是将k∼2k∼2k\sim 2的数取出来然后在末尾加入一个0/10/10/1。 之后暴力欧拉回路 代码
#includecstdio
#includealgorithm
#define K 2060
using namespace std;
int ans[K],n,k,m;
bool v[K];
bool euler(int x,int y)//求欧拉回路
{if (v[x]) return 0;ans[y]x1;//取二进制第一位v[x]true;//标记if (yn) return 1;if (euler((x1)m,y1)) return 1;//按字典序小的开始搜索if (euler(((x1)|1)m,y1)) return 1;//搜索v[x]false;//回溯
}
int main()
{scanf(%d,k);n1k;mn-1;printf(%d ,n);euler(n-2,1);//从n-2位保证输出的时候前面k个都是0for (int i1;in;i)printf(%d,ans[i]);
}
