首页 > 代码库 > 【codevs1106】 篝火晚会

【codevs1106】 篝火晚会

http://codevs.cn/problem/1106/ (题目链接)

题意

  将1~n顺序排列的环改成另一个环,问n-不动点数。

Solution

  啊智障啦,不会做×_×

  左转hzwer

代码

// codevs1106#include<algorithm>#include<iostream>#include<cstdlib>#include<cstring>#include<cstdio>#include<cmath>#define LL long long#define inf 1<<30#define Pi acos(-1.0)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);using namespace std;const int maxn=50010;int vis[maxn],t1[maxn],t2[maxn],a[maxn],b[maxn],c[maxn],n;int main() {	scanf("%d",&n);	for (int i=1;i<=n;i++) scanf("%d%d",&a[i],&b[i]);	c[1]=1;c[2]=a[1];	vis[c[1]]=vis[c[2]]=1;	for (int i=2;i<n;i++) {		if (c[i-1]==a[c[i]]) c[i+1]=b[c[i]];		else if (c[i-1]==b[c[i]]) c[i+1]=a[c[i]];		else {puts("-1");return 0;}		vis[c[i+1]]=1;	}	for (int i=1;i<=n;i++) if (!vis[i]) {puts("-1");return 0;}	int ans=1;	for (int i=1;i<=n;i++) {		int t=(c[i]-i+n)%n;		t1[t]++;		ans=max(ans,t1[t]);		t=(c[n-i+1]-i+n)%n;		t2[t]++;		ans=max(ans,t2[t]);	}	printf("%d",n-ans);	return 0;}

 

【codevs1106】 篝火晚会