自动搬运

查看原文

来自洛谷，原作者为

	wbqhasvcf 为了你唱下去，为你将希冀传递

搬运于2025-08-24 21:17:35，当前版本为作者最后更新于2025-02-23 18:00:44，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

此题为万恶のBCSP-X上半年比赛初中组第一题，难度已经接近黄级。不得不说这道题思路不仅有一定难度，坑点也不少，啊啊啊。

鄙人当年作为北京市一名普通の初中生现场参加过这场比赛的复赛，赛时还是成功A了这道题，所以谨以此篇题解。不过很险的是鄙人在最后 $10$ 分钟内忽然查出来第一题代码有漏洞（即下面提到的坑点一），迅速做了修改，不然AC代码差点儿变成 $40$ 分代码。

言归正传。此题的正解思路就是先将相邻两个机器人的质量作差，将所得结果的绝对值用一个数组 $d$ 记录下来。再循环扫一遍每个 $d_{i}$，不停取它们的最大公约数，如果最大公约数为 $1$ 就说明前面的机器人属于同一个家族，断开两个区间再重新操作即可。

需要注意的坑点有两个：一是每次不仅要判断最大公约数是否为 $1$，还要判断其对应的 $a_{i+1}$ 是否和前面的元素重复，重复的话也要断开（例如当 $a=[1,3,1]$ 时如果不加此判断，输出的就会是 $1$ 而不是 $2$，而中间应该断开分为 $[1,3]$ 和 $[1]$）；二是特判 $n=1$！！！这种情况下 $d$ 数组为空，需要输出 $1$！不过经查证此题原数据有漏洞，没有 $n=1$ 的数据，也就是说如果代码对于 $n=1$ 的数据输出的答案不是 $1$ 也能AC，建议多提供一组 $n=1$ 的hack数据。

以上两点，第一点用set查重，第二点特判即可。

下面附上本人赛时满分代码（算上查重，时间复杂度为 $O(n\log n)$），仅供参考：

#include<iostream>
#include<cmath>//abs()
#include<algorithm>//__gcd()
#include<set>
using namespace std;
const int N=1e5+5;

int n,a[N],d[N],ans=1;//默认至少有一个家族，所以ans初值赋为1
set<int> st;//用来查重
int main()
{
	cin>>n;
	if(n==1)//此参考代码的逻辑对于n=1不会输出1，所以需要特判 
	{
		cout<<1;
		return 0;
	}
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int i=1;i<n;i++)
	    d[i]=abs(a[i+1]-a[i]);//初始化d数组
	int gcd=d[1];
	st.insert(a[1]);
	if(gcd<=1)//特判第一个机器人的家族里是否只有它自己一个“人”
	{
		ans++;
		st.clear();
		gcd=d[2];
	}
	st.insert(a[2]);
	for(int i=2;i<n;i++)
	{
		gcd=__gcd(gcd,d[i]);//不断gcd
		if(gcd<=1||st.count(a[i+1]))//判断是否需要断开
		{
			ans++;
			st.clear();
			gcd=d[i+1];
		}
		st.insert(a[i+1]);
	}
	cout<<ans;
	return 0;
}