Description:
@card{
太鼓达人的鼓坏了,现在vani来修鼓。
鼓的主要元件是$m$个围成一圈的传感器。
每个传感器都有开和关两种工作状态,分别用$1$和$0$表示。
显然,从不同的位置出发沿顺时针方向连续检查$k$个传感器可以得到$m$个长度为$k$的$01$串。
Vani 知道这$m$个$01$串应该是互不相同的。
而且鼓的设计很精密, $m$会取到可能的最大值。
现在 Vani 已经了解到了$k$的值,他希望你求出$m$的值,并给出字典序最小的传感器排布方案。
$1 \leq k \leq 11$
}
Solution:
@card{
这个题直接做显然是没法做的,后效性太强,不容易进行动态规划,又没什么好的贪心思路,或许有神牛可以直接构造?
先观察样例,发现就是$2^3=8$,仔细想想$m$的上界就是$2^k$,能否构造出一种方案的长度为$2^k$呢?题目还要求字典序最小,显然把全是0的那个子串放在最前面最小,然后考虑什么串可以接在它后面?
想了想发现十分不可做,不过接在它后面这个关系可以用图论建模描述,我们把$2^k$个串作为图中的节点,能接在其后面的连有向边,仔细思考可以发现,一个点只会连两条出边和两条入边(全是0和全是1会形成自环),我们要求出的最优解其实就是图中的最大环,这其实就是要求哈密顿环,在一般图上是NP-hard的。
不重不漏的经过所有的点难以做到,所以我们可以把信息放在边上,即点是”长度为$m-1$的$01$串”,而边是”长度为$m$的$01$串”,按照上述方式建图后,每个点也只会连两条出边和两条入边,存在欧拉回路,所以我们可以直接求出方案。
另外吐槽一下网上的题解的代码实现大多是求”最大环”的那种,即dfs到一个点打一个vis标记,之后不重复访问,虽然从本题出发得到的结果是对的,但是推导的过程却是错误的。
}
Code:
@card{
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#define rint register int
#define lint long long
#define pii pair<int, int>
#define mp(x, y) make_pair((x), (y))
#define isnum(x) ('0' <= (x) && (x) <= '9')
template<typename tint>
inline bool readint(tint& x) {
int f = 1; char ch = getchar(); x = 0;
for(; !isnum(ch); ch = getchar()) if(ch == '-') f = -1;
for(; isnum(ch); ch = getchar()) x = x * 10 + ch - '0';
x *= f;
return x != 0;
}
using namespace std;
const int maxn = 12;
const int maxm = 1 << maxn;
const int maxedge = 4 * maxm;
int n, m, t;
int head[maxm], ev[maxedge], nxt[maxedge], totedge = 1;
inline void addedge(int nu, int nv) {
ev[++totedge] = nv, nxt[totedge] = head[nu], head[nu] = totedge;
}
int s[maxm], stop = 0;
void dfs(int x) {
while(head[x]) {
int y = ev[head[x]];
head[x] = nxt[head[x]];
dfs(y);
}
s[++stop] = x;
}
int main() {
readint(n);
int t = (1 << (n - 1)) - 1;
for(rint i=0; i<(1 << (n - 1)); i++) {
addedge(i, ((i << 1) & t) | 1);
addedge(i, (i << 1) & t);
}
dfs(0);
printf("%d ", 1 << n);
while(stop > 1) putchar((s[stop--] >> (n - 2)) + '0');
puts("");
return 0;
}
}
直接做过了捏