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

Bobi2014 · 2025-10-29 20:06:00 · 题解

这个一道可癌的数学题。

思路

考虑题目中的等式 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

#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;
}