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

这个一道~~可癌的~~数学题。

思路

考虑题目中的等式

x_{2} + x_{3} = x_{1} + x_{4}

可以转换成

x_{2} - x_{4} = x_{1} - x_{3}

，而

a_{x_{2}} + a_{x_{3}} = a_{x_{1}} + a_{x_{4}}

可以转化成

a_{x_{2}} - a_{x_{4}} = a_{x_{1}} - a_{x_{3}}

，也就是题目的要求变为了这个序列是等差序列。

那么我们只需要判断这个序列在满足题目给出的特定位置上是特定值的条件的情况下是否可以是等差序列即可。

时间复杂度

O(Tm)

。

Code

CPP

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
struct node{
	int p,x;
} dat[N];
int Q,n,m;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> Q;
	while(Q --){
		cin >> n >> m;
		for(int i = 1;i <= m;i ++){
			cin >> dat[i].p >> dat[i].x;
		}
		if(m <= 1){
			cout << "Yes\n";
			continue;
		}
		sort(dat + 1,dat + m + 1,[](node a,node b){
			return a.p < b.p;
		});
		int x = (dat[2].x - dat[1].x) / (dat[2].p - dat[1].p);
		bool flag = true;
		for(int i = 2;i <= m;i ++){
			if(dat[i].x - dat[i - 1].x != x * (dat[i].p - dat[i - 1].p)){
				flag = false;
				break;
			}
		}
		cout << (flag == true ? "Yes\n" : "No\n");
	}
	return 0;
}

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

文章操作

思路

Code

相关推荐

评论

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