noip2005篝火晚会

这是一道不算太难的题，但愚蠢的我并没有想到。

首先，判断无解的情况：他想相邻的不想与他相邻。

然后，构造出合法的数列，因为第一位左边有两种选择，且构造出的环不等价，所以要做两次。

(这一点我并没有想清楚)

然后，考虑对于构造出的数列(断环为链)，如何计算他与原数列的差别，即答案。

这是这道题最难的地方：如何 \(O(n)\) 的求出两个环的不同之处。

朴素算法：\(O(n^2)\)，显然无法接受。

因为环无论怎么旋转，两个人的相对位置是不会变的，于是，可以对于每一个位置求出的数列与原数列的差 \(x\)，表示数列要旋转 \(x\) 个位置，此位置才会与原数列重合。然后条统计出每个 \(x\) 出现的次数，\(n-max(x)\) 就是答案。

#include <bits/stdc++.h>

using namespace std;

#define db double

#define ll long long

#define RG register

inline int gi()

{

	RG int ret; RG bool flag; RG char ch;

	ret=0, flag=true, ch=getchar();

	while (ch < '0' || ch > '9')

		ch == '-' ? flag=false : 0, ch=getchar();

	while (ch >= '0' && ch <= '9')

		ret=(ret<<3)+(ret<<1)+ch-'0', ch=getchar();

	return flag ? ret : -ret;

}

const db pi = acos(-1.0);

const int N = 5e4+5, inf = 1<<30;

int n,ans,f[N],s[N],pos[N],cnt[N];

bool vis[N];

inline void cal()

{

	RG int i;

	for (i=1; i<=n; ++i)

		cnt[(pos[i]-i+n)%n]++;

	for (i=0; i<n; ++i)

		ans=max(ans,cnt[i]), cnt[i]=0;

}

inline void dfs(RG int o,RG int dep)

{

	pos[dep]=o;

	if (dep == n)

		return cal();

	if (!vis[f[o]])

		vis[f[o]]=true, dfs(f[o],dep+1), vis[f[o]]=false;

	if (!vis[s[o]])

		vis[s[o]]=true, dfs(s[o],dep+1), vis[s[o]]=false;

}

int main()

{

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

	freopen("fire.out","w",stdout);

	RG int i;

	n=gi();

	for (i=1; i<=n; ++i)

		f[i]=gi(), s[i]=gi();

	for (i=1; i<=n; ++i)

		if ((f[f[i]] != i  && s[f[i]] != i) || (f[s[i]] != i && s[s[i]] != i))

			return puts("-1"), 0;

	vis[1]=true;

	dfs(1,1);

	printf("%d\n",n-ans);

	return 0;

}