CF954C Matrix Walk 题解
题目链接：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;
}参考文献：
