自动搬运

查看原文

来自洛谷，原作者为

	ダ月 可爱，可爱！

搬运于2025-08-24 23:01:52，当前版本为作者最后更新于2024-08-10 16:13:07，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

• 我会检查。

注意到 Subtask 1 中 $m=n$。我们依次枚举 $z$，所有满足 $x+y=z$ 的二元对 $(x,y)$，要求 $a_x+a_y$ 的值两两相等。时间复杂度：$O(n^2)$

• 我会暴力。

应该随便写个指数级暴力就能过 Subtask 2 了吧。确信。

• 我会正解。

先猜一手结论：$a_i$ 是等差序列。接下来进行证明。

若 $n=5$，我们有以下式子：

1. $a_1+a_4=a_2+a_3$;
2. $a_1+a_5=a_2+a_4$;
3. $a_2+a_5=a_3+a_4$。

$2$ 式减去 $1$ 式得到 $a_5-a_4=a_4-a_3$。以此类推，不难发现 $a_i$ 序列为等差数列。

不过要特判 $m\le 1$。

如果 $m\ge 2$，我们只需要算出公差（要求是整数），然后看是否能够还原出一个等差数列。

时间复杂度：$O(n+m)$。

void solve(){
	//don't forget to open long long;
	int n,m;IO::cin>>n>>m;std::vector<int>v(n,1e9+1);
	while(m--){int x,y;mp[x]++;;IO::cin>>x>>y;x--;v[x]=y;}
	while(!v.empty()&&v.back()==1e9+1)v.pop_back();
	reverse(all(v));
	while(!v.empty()&&v.back()==1e9+1)v.pop_back();
	reverse(all(v));
	if(v.size()<=1)return IO::cout<<"Yes"<<'\n',void();
	int d=v.size()-1;ll L=v[0],R=v[d];
	if((R-L)%d)return IO::cout<<"No\n",void();
	ll B=(R-L)/d;
	for(int i=1;i<=d;i++){
		if(v[i]==1e9+1)v[i]=v[i-1]+B;
		if(v[i]!=v[i-1]+B)return IO::cout<<"No"<<'\n',void();
	}IO::cout<<"Yes"<<'\n';
}

代码是去年的代码了，有点丑。/yun