海亮 2025暑 VIII

skyx · 2025-08-22 20:39:57 · 个人记录

0822

how time flies!

很掉线啊，先不写了。

0823

home! Here we go!

T2

给定一个从小到大排好序的整数序列 A。

现在需要插入一些整数，使得序列中任意相邻两数之间的差值一样大，不能插入在开头和结尾。

问最少插入多少个整数才能满足要求，如果不能，则输出 -1。

由于值域只有 1e6，所以可以直接枚举公差 d 后进行判断。需要做的判断是序列 A 是否为序列b_i=i·d的子序列，总复杂度 O(V log V)。

或者把差分数组求出来，合法的最大公差一定是差分数组的 gcd，可直接完成判断。

注意对边界情况的特判，比如所有元素均相同，n=1，和无解的情况。

#include<bits/stdc++.h>
using namespace std;
int a[10000006];
int b[10000006];

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int ans=0;
        int g=0;
        int n;
        cin>>n;
        for(int i=1; i<=n; i++)
        {
            cin>>a[i];
        }
        bool flag=0;
        for(int i=1; i<n; i++)
        {
            b[i]=a[i+1]-a[i];
            if(b[i]==0) flag=1;
            if(b[i]==0 && i==1) g=b[i];
            else if(b[i]!=0) g=__gcd(g,b[i]);
        }
        if(flag && g!=0)
        {
            cout<<-1<<endl;
            continue;
        }
        if(flag && g==0)
        {
            cout<<0<<endl;
            continue;
        }

        for(int i=1; i<n; i++)
        {
            ans=ans+(b[i]/g)-1;
        }
        cout<<ans<<"\n";
    }
    return 0;
}

回家了，先不写了。