「雅礼集训 2017 Day7」蛐蛐国的修墙方案

#include<bits/stdc++.h>
using namespace std;

int n;
int ans[105];
int p[105];
bool force_right[105];

void dfs(int dep, int cnt) {
	if (dep == n + 1) {
		for (int i = 1; i <= n; ++i) 
			putchar('(' + ans[i]);
		exit(0);
	}
	if (cnt < n / 2) {
		if (force_right[dep] == 0) {
			if (p[dep] < dep) {
				if (ans[p[dep]] == 1) {
					ans[dep] = 0;
					dfs(dep + 1, cnt + 1);
					ans[dep] = 0;
				}
			} else {
				force_right[p[dep]] = 1;
				dfs(dep + 1, cnt + 1);
				force_right[p[dep]] = 0;
			}
		}
	} 
	if (dep - cnt <= cnt) {
		ans[dep] = 1;
		dfs(dep + 1, cnt);
		ans[dep] = 0;
	}
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i)
		scanf("%d", &p[i]);
	dfs(1, 0);
	return 0;
}

#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;

int n, p[105];

vector<int> circ[105];
bool vis[105], ans[105];
int cnt = 0;

bool check() {
	int cnt1 = 0, cnt2 = 0;
	for (int i = 1; i <= n; ++i) {
		cnt1 += (ans[i] == 0), cnt2 += ans[i];
		if (cnt1 < cnt2) return 0;
	}
	return 1;
}

void dfs(int u) {
	if (u == cnt + 1) {
		if (check()) {
			for (int i = 1; i <= n; ++i)
				putchar('(' + ans[i]);
			exit(0);
		}
		return;
	}
	int len = circ[u].size();
	if (!(len ^ 2)) {
		ans[circ[u][0]] = 0, ans[circ[u][1]] = 1;
		dfs(u + 1);
	} else {
		for (int i = 0; i ^ len; ++i) ans[circ[u][i]] = i & 1;
		dfs(u + 1);
		for (int i = 0; i ^ len; ++i) ans[circ[u][i]] = !(i & 1);
		dfs(u + 1);
	}
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) 
		scanf("%d", &p[i]);
	for (int i = 1; i <= n; ++i) {
		if (vis[i] == 0) {
			cnt += 1;
			int cur = i;
			do {
				circ[cnt].push_back(cur);
				vis[cur] = 1;
				cur = p[cur];
			} while (cur != i);
		}
	}
	dfs(1);
	return 0;
}