6023: 传感器（DFS）
时间：2023-12-09 01:37:02
6023: 传感器
时间限制:1 Sec 内存限制:128 MB提交:50 解决:21
[ 提交][ 状态][ [讨论版][命题人： admin]
题目描述
SR最近买了一款新的电子桌游
这个玩具是一个M周围的传感器。每个传感器都有两种工作状态：开关，分别用1和0表示。显然，从不同的位置触发连续检查K传感器，可以得到长度为K的01串。SR知道这个M个01串应该是不一样的。
而且这款桌游的设计很安静，M最大可能值。SR已知K值，他希望你能找到M值，并给出字典序最小的传感器排列方案。
这个玩具是一个M周围的传感器。每个传感器都有两种工作状态：开关，分别用1和0表示。显然，从不同的位置触发连续检查K传感器，可以得到长度为K的01串。SR知道这个M个01串应该是不一样的。
而且这款桌游的设计很安静，M最大可能值。SR已知K值，他希望你能找到M值，并给出字典序最小的传感器排列方案。
输入
一行一整数K
输出
一个整数 M 与二进制串，由空间隔开。表示最大的可能性 M，以及字典序最小的排列方案、字符 0 表示关， 1 表示打开。你输出的第一个字符和最后一个字符相邻
样例输入
3
样例输出
8 00010111
提示
100%的数据 2<=K<=11
来源
2018江苏冬令营4
借鉴：
将0~2^k-1做点，每点二进制末尾加1或0，去掉最高位，得到下一点。dfs，类似欧拉回路
- #include
- using namespace std;
- int a[1<<13];
- bool vis[1<<13];
- bool dfs(int u,int step,int n)
- {
- if(vis[u])return 0;
- vis[u]=1;
- a[step]=u&1;
- if(step==n-1)return 1;
- if(dfs((u<<1)&(n-1),step+1,n))return 1;
- if(dfs((u<<1)&(n-1)|1,step+1,n))return 1;
- vis[u]=0;
- return 0;
- }
- int main()
- {
- int n,k;
- cin>>k;
- n=1<
- dfs(0,0,n);
- printf("%d ",n);
- for(int i=1;i
- for(int i=0;i
- printf("\n");
- }
