2.7 KiB
AcWing 400 太鼓达人
一、题目描述
太鼓达人的鼓坏了，现在 vani 来修鼓。
鼓的主要元件是 M 个围成一圈的传感器。每个传感器都有开和关两种工作状态，分别用1和0表示。
显然，从不同的位置出发沿顺时针方向连续检查K个传感器可以得到M个长度为K的01串。
Vani知道这M个01串应该是互不相同的。
而且鼓的设计很精密，M会取到可能的最大值。
现在Vani已经了解到了K的值，他希望你求出M的值，并给出 字典序最小 的传感器排布方案。
输入格式
一个整数 K。
输出格式
一个整数和一个二进制串，由一个空格分隔，分别表示可能的最大的 M 以及 字典序最小的排布方案。
字符 0 表示关，1 表示开，你输出的串的第一个字和最后一个字是相邻的。
数据范围
2≤K≤11
输入样例：
3
输出样例：
8 00010111
二、解题思路
很显然，第一问的答案就是 2^n。
第二问，构造一个有 2^{n-1}个节点的图，对应 2^{n-1}个 n-1 位二进制数。从代表数 k 的节点(0<=k<2^{n-1})向代表数(k<<1)\&(1<<(n-1))的节点 和 代表数((k<<1)+1)\&(1<<(n-1))的节点分别连一条边。可以发现这样的图中，所有点的入度和出度都是 2，因此这是一个欧拉图。
因此我们从 0 号点开始 dfs 寻找一个欧拉回路，回溯的时候记录到栈中，最后倒序输出即可。
因为要求字典序最小，dfs 的时候要注意搜索顺序，先走 0 边，再走 1 边。这个算法寻找欧拉回路，每个点、每条边只访问一次，是 O(V+E)级别的。
时间复杂度 O(2^n)，预计得分 100 分。
和上一题一样，其实，000到001，其实00是不变的，可以抽象成点，而000，001都是只有一个，可以抽象成边，那么这题就可以做出来了，以0——2^（n-1)-1为编号建立一棵树，共2^（n-1)个节点，如果在某个节点后面添加一个0或者1,再去掉最高位，得到下一个节点，两节点之间连一条有向边。图中每条边就表示了一个数，共有2^n个数，各不相同！题目要求字典序最小，则从2^(n-1-1节点开始，并且每个节点先连加0的边，后连加1的边，这样的话，就能保证最终的字典序最小。还是欧拉回路，都是一个模型，算法也就那个一个。只是这里，为什么，我取模了，提交OJ反而会快10几Ms,这一点，我不明白的！