【正经题解】篝火晚会

AC君

2024-02-20 17:28:49

发布于：浙江

102阅读

0回复

0点赞

一开始的读入之后判定能否围成环，不能直接退。

然后先求出正确的环的样子，因为不可能存下环，所以默认从1开始断，先正着存一遍。

那么就是最关键的比较了这个地方我给大家手动模拟下并说明为什么是所有不匹配的。

我先设置一个目标的数列 1 2 3 4 5

那么一开始的初始数列为 1 4 3 5 2

首先我们将4替换到本该在的位置

1 2 3 4 5

1 3 4 2 5 5被踢出来了再找5的位置

1 3 4 5 2 2又被踢出来

1 2 3 4 5 最后就排完了，一共是代价3，也就是所有不匹配的数目

你很容易可以证明，每次替换将一个不匹配的替换到匹配的代价最小为1，并且无论怎样的数据都会形成上面的循环排，因为其他的已经对上了根本就不用换。

这就是为什么是不匹配的数目。

至于为什么这样你还会wa就是因为你还要反跑一遍

匹配 1 2 3 4

你的 4 3 2 1

最后结果会是4，但是其实你发现这两个在环状态其实是一样的，所以其实正解是0，这就是为啥要反跑一边，等会我会在解法说明为什么

那么就到了关键的解法，n^2不用讲了吧，TLE妥妥的。那么怎么优化？

你先对每一个点先循环，用算出它的位置到正解位置所需移动的距离%n(注意负数)，将记录的spin[]++。这就是求出最多的相同的。为什么？给你十分钟想想想不到再看吧。

那么接下来讲为啥，因为你可以手动做两个环，一个大点一个小点，外圈放正解，里面的圈放一开始的序列也就是1-n。先把1和1对位，那么所有本来的数到正解距离为0的都会对位，对位的数的个数也就是spin【0】中存的数字，然后把里面的圈向右移一位。这下所有与正解距离唯一的就对位啦！那么就是spin[1]咯。同理，求出最大spin就是最小不同的。

为啥咱要反跑一边，因为你这样只是右移，但你很明显可以把圈往左移，也许能更快匹配，举个栗子吧。

这是以4为断点（我不好构造数据谅解下）

目标 4 3 2 1

当前2 3 4 1

你发现 2 与正确位置差2 ，4也是，但是3和1却对位了！那么就会的出答案为2。很明显是错的，因为你把这两玩意化成环是一样的，那么我们反着来

目标 4 1 2 3

当前 2 3 4 1

你发现所有与正确的位置差都为2！

于是不用移动！！！

#include<bits/stdc++.h>
using namespace std;
#define MAXN 50000+10
int a[MAXN],b[MAXN],circle[MAXN],spin[MAXN];
 
inline int read()//读入优化 不用写 
{
    char ch='*';
    while(!isdigit(ch=getchar()));
    int num=ch-'0';
    while(isdigit(ch=getchar()))num=num*10+ch-'0';
    return num;
}
int main()
{
    int n;
    n=read();
    for(int i=1;i<=n;i++)
    {    
        a[i]=read();b[i]=read();
    }
    circle[1]=1;
    circle[2]=a[1];//第一个点默认切环点
    for(int i=1;i<=n;i++)
    {
        if(b[a[i]]!=i&&a[a[i]]!=i||a[b[i]]!=i&&b[b[i]]!=i)//判断是否可行,由于是个圈，可逆，所以两次判定 
        {
            printf("-1");
            return 0;
        }
        //if(i>1)
            if(a[circle[i]]==circle[i-1])circle[i+1]=b[circle[i]];    //由于你并不知道这两个同学的左右，所以判断一下，免得建环重复一个点
            else circle[i+1]=a[circle[i]]; 
    }
    int ans=n+10;//最多n-1,n+10没问题了 
    for(int i=1;i<=n;i++)//这里开始是重点，就是找旋转次数，本蒟蒻一开始一直没理解，找大佬讲了好久才懂，如果旋转次相同，就可以看作与序列匹配，即为不用换位置的个数 
    {
        spin[((i-circle[i]+n))%n]++;//直接膜就可以，+n把负数改过来，最后移动步数为0~n-1；
        ans=min(ans,n-spin[((i-circle[i]+n))%n]);//答案是否需要更新 
    }
    memset(spin,0,sizeof(spin));//重新初始化，准备反跑 
    memset(circle,0,sizeof(circle));
    circle[0]=1;
    circle[1]=b[1];
    for(int i=1;i<=n;i++)
    {
        if(b[circle[i]]==circle[i-1])circle[i+1]=a[circle[i]];
        else circle[i+1]=b[circle[i]];//反跑直接反过来，ctrl+c&&ctrl+v 
    }
    for(int i=1;i<=n;i++) 
    {
        spin[((i-circle[i]+n))%n]++;
        ans=min(ans,n-spin[((i-circle[i]+n))%n]);//反跑反正数组不会变，一样的ctrl+c&&ctrl+v
    }
    printf("%d",ans);
}

有帮助，赞一个

去预览

0/2000

全部评论 3

起个很长的名字才能引起一个傻孑读
一开始的读入之后判定能否围成环，不能直接退。

然后先求出正确的环的样子，因为不可能存下环，所以默认从1开始断，先正着存一遍。

那么就是最关键的比较了这个地方我给大家手动模拟下并说明为什么是所有不匹配的。

我先设置一个目标的数列 1 2 3 4 5

那么一开始的初始数列为 1 4 3 5 2

首先我们将4替换到本该在的位置

1 2 3 4 5

1 3 4 2 5 5被踢出来了再找5的位置

1 3 4 5 2 2又被踢出来

1 2 3 4 5 最后就排完了，一共是代价3，也就是所有不匹配的数目

你很容易可以证明，每次替换将一个不匹配的替换到匹配的代价最小为1，并且无论怎样的数据都会形成上面的循环排，因为其他的已经对上了根本就不用换。

这就是为什么是不匹配的数目。

至于为什么这样你还会wa就是因为你还要反跑一遍

匹配 1 2 3 4

你的 4 3 2 1

最后结果会是4，但是其实你发现这两个在环状态其实是一样的，所以其实正解是0，这就是为啥要反跑一边，等会我会在解法说明为什么

那么就到了关键的解法，n^2不用讲了吧，TLE妥妥的。那么怎么优化？

你先对每一个点先循环，用算出它的位置到正解位置所需移动的距离%n(注意负数)，将记录的spin[]++。这就是求出最多的相同的。为什么？给你十分钟想想想不到再看吧。

那么接下来讲为啥，因为你可以手动做两个环，一个大点一个小点，外圈放正解，里面的圈放一开始的序列也就是1-n。先把1和1对位，那么所有本来的数到正解距离为0的都会对位，对位的数的个数也就是spin【0】中存的数字，然后把里面的圈向右移一位。这下所有与正解距离唯一的就对位啦！那么就是spin[1]咯。同理，求出最大spin就是最小不同的。

为啥咱要反跑一边，因为你这样只是右移，但你很明显可以把圈往左移，也许能更快匹配，举个栗子吧。

这是以4为断点（我不好构造数据谅解下）

目标 4 3 2 1

当前2 3 4 1

你发现 2 与正确位置差2 ，4也是，但是3和1却对位了！那么就会的出答案为2。很明显是错的，因为你把这两玩意化成环是一样的，那么我们反着来

目标 4 1 2 3

当前 2 3 4 1

你发现所有与正确的位置差都为2！

于是不用移动！！！

#include<bits/stdc++.h>
using namespace std;
#define MAXN 50000+10
int a[MAXN],b[MAXN],circle[MAXN],spin[MAXN];

inline int read()//读入优化不用写
{
char ch='';
while(!isdigit(ch=getchar()));
int num=ch-'0';
while(isdigit(ch=getchar()))num=num10+ch-'0';
return num;
}
int main()
{
int n;
n=read();
for(int i=1;i<=n;i++)
{
a[i]=read();b[i]=read();
}
circle[1]=1;
circle[2]=a[1];//第一个点默认切环点
for(int i=1;i<=n;i++)
{
if(b[a[i]]!=i&&a[a[i]]!=i||a[b[i]]!=i&&b[b[i]]!=i)//判断是否可行,由于是个圈，可逆，所以两次判定
{
printf("-1");
return 0;
}
//if(i>1)
if(a[circle[i]]==circle[i-1])circle[i+1]=b[circle[i]]; //由于你并不知道这两个同学的左右，所以判断一下，免得建环重复一个点
else circle[i+1]=a[circle[i]];
}
int ans=n+10;//最多n-1,n+10没问题了
for(int i=1;i<=n;i++)//这里开始是重点，就是找旋转次数，本蒟蒻一开始一直没理解，找大佬讲了好久才懂，如果旋转次相同，就可以看作与序列匹配，即为不用换位置的个数
{
spin[((i-circle[i]+n))%n]++;//直接膜就可以，+n把负数改过来，最后移动步数为0~n-1；
ans=min(ans,n-spin

1周前来自广东
0
137****6933
#include<bits/stdc++.h>
using namespace std;
#define MAXN 50000+10
int a[MAXN],b[MAXN],circle[MAXN],spin[MAXN];

inline int read()//读入优化不用写
{
char ch='';
while(!isdigit(ch=getchar()));
int num=ch-'0';
while(isdigit(ch=getchar()))num=num10+ch-'0';
return num;
}
int main()
{
int n;
n=read();
for(int i=1;i<=n;i++)
{
a[i]=read();b[i]=read();
}
circle[1]=1;
circle[2]=a[1];//第一个点默认切环点
for(int i=1;i<=n;i++)
{
if(b[a[i]]!=i&&a[a[i]]!=i||a[b[i]]!=i&&b[b[i]]!=i)//判断是否可行,由于是个圈，可逆，所以两次判定
{
printf("-1");
return 0;
}
//if(i>1)
if(a[circle[i]]==circle[i-1])circle[i+1]=b[circle[i]]; //由于你并不知道这两个同学的左右，所以判断一下，免得建环重复一个点
else circle[i+1]=a[circle[i]];
}
int ans=n+10;//最多n-1,n+10没问题了
for(int i=1;i<=n;i++)//这里开始是重点，就是找旋转次数，本蒟蒻一开始一直没理解，找大佬讲了好久才懂，如果旋转次相同，就可以看作与序列匹配，即为不用换位置的个数
{
spin[((i-circle[i]+n))%n];//直接膜就可以，+n把负数改过来，最后移动步数为0~n-1；
ans=min(ans,n-spin[((i-circle[i]+n))%n]);//答案是否需要更新
}
memset(spin,0,sizeof(spin));//重新初始化，准备反跑
memset(circle,0,sizeof(circle));
circle[0]=1;
circle[1]=b[1];
for(int i=1;i<=n;i)
{
if(b[circle[i]]==circle[i-1])circle[i+1]=a[circle[i]];
else circle[i+1]=b[circle[i]];//反跑直接反过来，ctrl+c&&ctrl+v
}
for(int i=1;i<=n;i++)
{
spin[((i-circle[i]+n))%n]++;
ans=min(ans,n-spin[((i-circle[i]+n))%n]);//反跑反正数组不会变，一样的ctrl+c&&ctrl+v
}
printf("%d",ans);
}

有帮助，赞一个

userId_undefined
去预览
此处输入正文，2千字以内，可点击右上角【去预览】按钮查看markdown展示效果
0/2000发布
全部评论 1
userId_undefined
🥥

倔强青铜模拟·模拟练习生出道萌新
运行超时，您的程序未能在规定时间内运行结束，请检查是否循环有误或算法复杂度过大

2025-03-01 来自甘肃

0
userId_undefined
射手骑着龙——互

回复
🥥
啊,ac,哪里运行错误？

2025-04-14 来自广东

2025-11-06 来自浙江
0
🥥
运行超时，您的程序未能在规定时间内运行结束，请检查是否循环有误或算法复杂度过大

2025-03-01 来自甘肃
0
- 凤凰涅槃浴火重生
  回复
  🥥
  啊,ac,哪里运行错误？
  
  2025-04-14 来自广东
  0