题解：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，有：

两者相等，满足条件。

实现

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

如果 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。

代码

//#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;
}
//
//              ⠀⢸⣿⣿⣿⠀⣼⣿⣿⣦⡀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⠀⠀⠀ ⠀⢸⣿⣿⡟⢰⣿⣿⣿⠟⠁
// ⠀⠀⠀⠀⠀⠀⠀⢰⣿⠿⢿⣦⣀⠀⠘⠛⠛⠃⠸⠿⠟⣫⣴⣶⣾⡆
// ⠀⠀⠀⠀⠀⠀⠀⠸⣿⡀⠀⠉⢿⣦⡀⠀⠀⠀⠀⠀⠀ ⠛⠿⠿⣿⠃
// ⠀⠀⠀⠀⠀⠀⠀⠀⠙⢿⣦⠀⠀⠹⣿⣶⡾⠛⠛⢷⣦⣄⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣧⠀⠀⠈⠉⣀⡀⠀ ⠀⠙⢿⡇
// ⠀⠀⠀⠀⠀⠀⢀⣠⣴⡿⠟⠋⠀⠀⢠⣾⠟⠃⠀⠀⠀⢸⣿⡆
// ⠀⠀⠀⢀⣠⣶⡿⠛⠉⠀⠀⠀⠀⠀⣾⡇⠀⠀⠀⠀⠀⢸⣿⠇
// ⢀⣠⣾⠿⠛⠁⠀⠀⠀⠀⠀⠀⠀⢀⣼⣧⣀⠀⠀⠀⢀⣼⠇
// ⠈⠋⠁⠀⠀⠀⠀⠀⠀⠀⠀⢀⣴⡿⠋⠙⠛⠛⠛⠛⠛⠁
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣾⡿⠋⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⢾⠿⠋⠀