嘘~ 正在从服务器偷取页面 . . .

CF954C Matrix Walk 题解

发布日期: 2023-06-01

更新日期: 2023-06-01

文章字数: 566

CF954C Matrix Walk 题解

题意：

你有一个大小未知（假设为 $x\times y$）的矩阵，这个矩阵中的格子的编号的排列有规律，比如说 $(i,j)$ 号格子的编号为 $y\times (i - 1) + j$。

但是现在这个矩阵的大小是未知的，我们的任务是算出来这个矩阵的任意一种可能的大小。

接下来，你有一个长度为 $n$ 序列，表示你在矩阵中行动时走到的格子的编号。（你在矩阵中只能上下左右行动，不能走出矩阵）如果说有符合这种序列的矩阵，那么输出 YES，并输出矩阵的任意一种可能的大小 ；否则输出 NO。

输入格式：

第一行一个整数 $n$。

第二行 $n$ 个整数，表示这个序列。

输出格式：

我们需要的矩阵的大小。

数据范围：

$1 \le n\le 2 \times 10^5$，序列中任意的数字都小于等于 $10^9$，矩阵大小小于 $10 ^ 9\times 10^9$。

简单的小结论题。容易发现上下两个数相差 $y$ ，并且这道题跟 $x$ 基本没有关系。

因此我们可以扫一遍，先确定一个可能的 $y$ ，然后检验一下这个 $y$ 是否合法。

时间复杂度 $\mathcal{O}(n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(2e5 + 15))

int n, c = 1, ok = 1, a[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
        if(i > 1 && a[i] == a[i - 1]) ok = 0;
        if(i > 1 && abs(a[i] - a[i - 1]) != 1 && a[i] != a[i - 1]) c = abs(a[i] - a[i - 1]);
    }
    for(int i = 2; i <= n; i++)
    {
        if(abs(a[i] - a[i - 1]) != 1 && abs(a[i] - a[i - 1]) != c) ok = 0;
        else if(abs(a[i] - a[i - 1]) == 1 && c != 1 && (a[i] - 1) / c != (a[i - 1] - 1) / c) ok = 0;
    }
    if(!ok) cout << "NO" << '\n';
    else cout << "YES\n1000000000 " << c << '\n';
    return 0;
}