AcWing 400. 太鼓达人

大型补档计划

神仙题。考虑转为图论模型。

若以 \(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;

}

巴特西

AcWing 400. 太鼓达人

最新文章

热门文章