题解：B4174 [BCSP-X 2024 6 月初中组] 厂房

· · 题解

此题为万恶の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;
}