【LG3322】[SDOI2015]排序

题面

题解

交换顺序显然不影响答案，所以每种本质不同的方案就给答案贡献次数的阶乘。

从小往大的交换每次至多\(4\)中决策，复杂度\(O(4^n)\)。

代码

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

using namespace std;

const int MAX_N = 1 << 13;

int N, a[MAX_N];

long long fac[13], ans;

bool check(int x) {

	for (int i = 1; i <= 1 << (N - x); i++)

		if (a[(i - 1) * (1 << x) + 1] + (1 << (x - 1)) !=

			a[(i - 1) * (1 << x) + 1 + (1 << (x - 1))]) return 0;

	return 1;

}

void Swap(int p1, int p2, int k) {

	for (int i = 0; i < k; i++)

		swap(a[p1 + i], a[p2 + i]);

}

void dfs(int x, int p) {

	if (x && !check(x)) return ;

	if (x == N) return (void)(ans += fac[p]);

	dfs(x + 1, p);

	int tmp[5], tot = 0;

	for (int i = 1; i <= 1 << (N - x); i += 2)

		if (a[(i - 1) * (1 << x) + 1] + (1 << x) !=

			a[i * (1 << x) + 1]) {

			if (tot == 4) return ;

			tmp[++tot] = i, tmp[++tot] = i + 1;

		}

	if (!tot) return ;

	for (int i = 1; i <= tot; i++)

		for (int j = i + 1; j <= tot; j++) {

			Swap((1 << x) * (tmp[i] - 1) + 1, (1 << x) * (tmp[j] - 1) + 1, 1 << x);

			dfs(x + 1, p + 1);

			Swap((1 << x) * (tmp[i] - 1) + 1, (1 << x) * (tmp[j] - 1) + 1, 1 << x);

		}

}

int main () {

#ifndef ONLINE_JUDGE

    freopen("cpp.in", "r", stdin);

#endif

	fac[0] = 1;

	for (int i = 1; i < 13; i++) fac[i] = fac[i - 1] * i;

	scanf("%d", &N);

	for (int i = 1; i <= 1 << N; i++) scanf("%d", a + i);

	dfs(0, 0);

	printf("%lld\n", ans);

    return 0;

}

巴特西

【LG3322】[SDOI2015]排序

【LG3322】[SDOI2015]排序

题面

题解

代码

最新文章

热门文章