题解：P10852 【MX-X2-T1】「Cfz Round 4」Awaken

upd：修正了读取两个

n

的问题

题目大意

给定一个长度为

n

（

n \ge 5

）的序列的部分位置的值，要求判断是否存在一个完整的整数序列，满足：

对于所有满足

x_2 + x_3 = x_1 + x_4

的互异下标

x_1, x_2, x_3, x_4

，都有

a_{x_2} + a_{x_3} = a_{x_1} + a_{x_4}

。

思路

实际上要求序列是一个等差数列

考虑特殊情况：

取

x_1 = i-1, x_2 = i, x_3 = i+1, x_4 = i+2

，则

(i) + (i+1) = (i-1) + (i+2)

根据条件得到：

a_i + a_{i+1} = a_{i-1} + a_{i+2}

。

对于等差数列

a_i = a_1 + (i-1)d

，有：

$a_i + a_{i+1} = [a_1 + (i-1)d] + [a_1 + id] = 2a_1 + (2i-1)d$ ；
$a_{i-1} + a_{i+2} = [a_1 + (i-2)d] + [a_1 + (i+1)d] = 2a_1 + (2i-1)d$ 。

两者相等，满足条件。

实现

比较简单，需要注意一下特殊情况。

如果

m = 0

，总是可以构造一个等差数列（如全 0 序列），输出 Yes。

如果

m = 1

，总是可以构造一个等差数列（如所有项等于已知值），输出 Yes。

如果

m \ge 2

：

先将已知点按位置排序，再计算相邻点的位置差和值差，确定公差

d = \frac{a_{p_{i+1}} - a_{p_i}}{p_{i+1} - p_i}

，然后检查所有已知点是否满足等差数列关系。

如果所有点都满足且公差为整数，输出 Yes，否则输出 No。

代码

CPP

//#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define ull unsigned long long 
#define int long long
using namespace std;
using ll=long long;
inline void read(int& a) {
	int w=1;char c;a=0;
	while((c=getchar())<'0'||c>'9')if(c=='-')w=-1;
	do a=a*10+(c^48); while((c=getchar())>='0'&&c<='9');
	a*=w;
}
void write(int x){
	if(x<0)putchar('-'),x=-x;
	if(x>9)write(x/10);
	putchar(x%10+'0');
	return ;
}
const int N=1e9;
void solve(){
	int n,m;
	read(n),read(m);
	vector<pair<int,int>>a(m);
	for(int i=0;i<m;i++)read(a[i].first),read(a[i].second);
	if(m<=1){
		puts("Yes");
		return;
	}
	sort(a.begin(),a.end());
	bool is=1;
	int num=a[1].second-a[0].second;
	int numm=a[1].first-a[0].first;
	if(num%numm!=0)is=0;
	else {
		int d=num/numm;
		int pos=a[0].second-(a[0].first-1)*d;
		for(auto [x,y]:a){
			if(pos+(x-1)*d!=y){
				is=0;break;
			}
		}
	}
	if(is)puts("Yes");
	else puts("No");
}
signed main() {
	int T;
	read(T);
	while(T--)solve();
	return 0;
}
//
//              ⠀⢸⣿⣿⣿⠀⣼⣿⣿⣦⡀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⠀⠀⠀ ⠀⢸⣿⣿⡟⢰⣿⣿⣿⠟⠁
// ⠀⠀⠀⠀⠀⠀⠀⢰⣿⠿⢿⣦⣀⠀⠘⠛⠛⠃⠸⠿⠟⣫⣴⣶⣾⡆
// ⠀⠀⠀⠀⠀⠀⠀⠸⣿⡀⠀⠉⢿⣦⡀⠀⠀⠀⠀⠀⠀ ⠛⠿⠿⣿⠃
// ⠀⠀⠀⠀⠀⠀⠀⠀⠙⢿⣦⠀⠀⠹⣿⣶⡾⠛⠛⢷⣦⣄⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣧⠀⠀⠈⠉⣀⡀⠀ ⠀⠙⢿⡇
// ⠀⠀⠀⠀⠀⠀⢀⣠⣴⡿⠟⠋⠀⠀⢠⣾⠟⠃⠀⠀⠀⢸⣿⡆
// ⠀⠀⠀⢀⣠⣶⡿⠛⠉⠀⠀⠀⠀⠀⣾⡇⠀⠀⠀⠀⠀⢸⣿⠇
// ⢀⣠⣾⠿⠛⠁⠀⠀⠀⠀⠀⠀⠀⢀⣼⣧⣀⠀⠀⠀⢀⣼⠇
// ⠈⠋⠁⠀⠀⠀⠀⠀⠀⠀⠀⢀⣴⡿⠋⠙⠛⠛⠛⠛⠛⠁
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣾⡿⠋⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⢾⠿⠋⠀

题解：P10852 【MX-X2-T1】「Cfz Round 4」Awaken

文章操作

题目大意

思路

实现

代码

相关推荐

评论

题解：P10852 【MX-X2-T1】「Cfz Round 4」Awaken