首页 > 代码库 > 【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】 篝火晚会
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。