专栏文章

海亮 2025暑 VIII

个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性,并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio6rbp1
此快照首次捕获于
2025/12/02 14:17
3 个月前
此快照最后确认于
2025/12/02 14:17
3 个月前
查看原文

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,和无解的情况。
CPP
#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;
}
回家了,先不写了。

评论

0 条评论,欢迎与作者交流。

正在加载评论...