标签：le 洛谷题解样例测试数据 Downarrow 序列 Yes Awaken

洛谷P10852题解

摸鱼环节

【MX-X2-T1】「Cfz Round 4」Awaken

题目背景

能否等到梦醒了的时候。

图片与题目做法无关，图片来源网络，侵删

题目描述

月做了一个梦。在梦中，她拿到了一个长度为 \(n\) 的整数序列 \(a_1, \ldots, a_n\)，其中 \(\bm{n \ge 5}\)。

梦醒了。月忘记了这个序列中的一部分元素，留下了空白。所幸，月还记得 \(m\) 个非空白的位置。月希望将空白的位置填上，还原整个序列。

月还记得梦中的序列有性质：对于所有满足 \(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}\) 成立。

月想知道是否可以还原出一个满足性质的序列（如果不能的话，就是她记错了）。若可以，输出 Yes；否则输出 No。

输入格式

本题有多组测试数据。

输入的第一行包含一个整数 \(T\)，表示测试数据组数。

接下来依次输入每组测试数据。对于每组测试数据：

第一行两个整数 \(n,m\)，其中 \(n \ge 5\)，\(m\) 表示 \(a_i\) 中不为空的位置的个数。
接下来 \(m\) 行，每行两个整数 \(p_i,x_i\)，表示 \(a_{p_i}\) 不为空，且 \(a_{{p_i}}=x_i\)。保证 \(p_i\) 两两不同。

输出格式

对于每组测试数据，输出一个字符串 Yes 或 No，表示原序列是否存在。

本题中字符串大小写不敏感，即 yes、yeS、yEs、Yes、YEs、YeS、yES、YES 都被认为是 Yes，No 同理。

样例 #1

样例输入 #1

样例输出 #1

Yes
No
Yes

样例 #2

样例输入 #2

样例输出 #2

Yes

样例 #3

样例输入 #3

2
9 6
1 -856675560
8 479857596
5 -92942328
4 -283875636
3 -474808944
9 670790904
10 7
4 -32297373
10 -633066970
9 831032854
5 -43726758
2 -699796467
1 -918486370
8 612342951

样例输出 #3

Yes
No

提示

【样例解释 #1】

对于第 \(1\) 组测试数据，当前序列为 \([1,?,?,4,5]\)。可以构造出原序列 \([1,2,3,4,5]\)，你可以检查此序列满足性质。

对于第 \(2\) 组测试数据，当前序列为 \([1,4,7,1,5,4]\)。可以证明不存在满足性质的原序列。这组样例提醒你，\(\bm p\) 不一定升序给出。

对于第 \(3\) 组测试数据，当前序列为 \([?,?,?,?,?]\)。可以构造出原序列 \([0,0,0,0,0]\)，当然 \([-1,-1,-1,-1,-1]\) 也可以。这组样例提醒你，\(m\) 可以等于 \(0\)，以及原序列可以含有负数或 \(0\)。

【数据范围】

设 \(\sum n\) 表示单个测试点中 \(n\) 的和。

对于所有测试数据，\(1 \le T\le 4\times10^4\)，\(5\le n\le2\times 10^5\)，\(\sum n\le 2\times10^5\)，\(0\le m\le n\)，\(1\le p_i\le n\)，\(-10^{9} \le x_i \le 10^{9}\)。保证在同一组数据内 \(p_i\) 两两不同。

本题采用捆绑测试。

Subtask 1（20 points）：\(n\le2000\) 且 \(m=n\)。
Subtask 2（30 points）：\(n\leq 6\)，\(|x|\le7\)。
Subtask 3（20 points）：\(m=2\)。
Subtask 4（30 points）：无特殊限制。

可恶的MX居然不开题解，真的是醉了TNT。

正片开始

首先将等式化为\(x_{1}-x_{2}=x_{3}-x_{4}\)和\(a_{x_{1}}-a_{x_{2}}=a_{x_{3}}-a_{x_{4}}\)，可以发现这个序列必须是等差序列。

此时，我们只需要考虑任意两点的值差除以两点的坐标差是否为定值。细节处理见代码。

code：

int f=0;
cin>>n>>m;
for(int i=1;i<=m;i++)
    cin>>a[i].x>>a[i].y;
for(int i=1;i<m;i++)
{
    if((a[i+1].y-a[i].y)%(a[i+1].x-a[i].x)==0)//整除的向下取整可能会寄
    {
        sum[i]=(a[i+1].y-a[i].y)/(a[i+1].x-a[i].x);//统计两点值差除两点坐标差的值
    }
    else{f=1;break;}
}
for(int i=1;i<m-1;i++){if(sum[i]!=sum[i+1]){f=1;break;}}   
if(f==1)cout<<"NO"<<endl;
else cout<<"YES"<<endl;
for(int i=1;i<=m;i++){ a[i].x=0;a[i].y=0;sum[i]=0;}

~~不得不说图片挺好看的，果断保存~~

完整代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+10;
ll t,n,m,sum[N];
struct node
{
    ll x,y;//编号，数值
}a[N];
int main()
{
    cin>>t;
    while(t--)
    {
        int f=0;
        cin>>n>>m;
        for(int i=1;i<=m;i++)
            cin>>a[i].x>>a[i].y;
        for(int i=1;i<m;i++)
        {
            if((a[i+1].y-a[i].y)%(a[i+1].x-a[i].x)==0)
            {
                sum[i]=(a[i+1].y-a[i].y)/(a[i+1].x-a[i].x);
            }
            else{f=1;break;}
        }
        for(int i=1;i<m-1;i++){if(sum[i]!=sum[i+1]){f=1;break;}}   
        if(f==1)cout<<"NO"<<endl;
        else cout<<"YES"<<endl;
        for(int i=1;i<=m;i++){ a[i].x=0;a[i].y=0;sum[i]=0;}
    }
    return 0;
}

完结收工！！！！！

个人主页

看完点赞，养成习惯

\(\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\)

标签：le,洛谷,题解,样例,测试数据,Downarrow,序列,Yes,Awaken
From： https://www.cnblogs.com/qc0817/p/18352640

洛谷 P10852 Awaken——题解