大型补档计划
神仙题。考虑转为图论模型。
若以 \(2 ^ k\) 个点，相互转化，很容易看出要求一个哈密尔顿环，显然对于 \(1000\) 规模的数据求不出来。
对于图论中环的算法，并且能满足数据规模的算法只有欧拉回路了，考虑点边换一下。
若以 \(2 ^{k - 1}\) 为点，可以相互平移一个距离转换的连一条边，显然有 \(2 ^ k\) 个互不相同的边，而且符合欧拉图的性质（每个点都有两个入度、两个出度），这样跑欧拉回路算法就行了。
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1 << 10, M = (1 << 11) + 5;
int K, ans[N], s[M], tot, S1, S2, id[M];
int head[N], numE = 0;
struct E{
int next, v, w;
} e[M];
void add(int u, int v, int w) {
e[++numE] = (E) { head[u], v, w };
head[u] = numE;
}
void euler() {
int top = 0; s[++top] = 0;
while (top) {
if (id[top] != -1) {
ans[++tot] = id[top];
id[top] = -1;
}
int u = s[top], i = head[u];
if (i) {
id[top] = e[i].w;
s[++top] = e[i].v;
head[u] = e[i].next;
} else top--;
}
for (int i = 1; i <= K - 1; i++) putchar('0');
for (int i = tot; i > K - 1; i--) printf("%d", ans[i]);
}
int main() {
memset(id, -1, sizeof id);
scanf("%d", &K);
S1 = (1 << (K - 1)) - 1, S2 = (1 << K) - 1;
printf("%d ", 1 << K);
for (int i = 0; i <= S1; i++) {
add(i, (i << 1 | 1) & S1, 1);
add(i, (i << 1) & S1, 0);
}
euler();
return 0;
}