题解：CF954C Matrix Walk

tangtianyao0123 · 2025-11-30 13:33:18 · 题解

这么简单为什么评绿？？？？？

题目传送门，CF题目传送门。

通过分析：

• 当 (i,j)\to(i,j\pm1) 时，权值 \pm1。
• 当 (i,j)\to(i\pm1,j) 时，权值 \pm y。

所以，|a_i-a_{i-1}|=1 或 y，那么就可以求出 y。

显然，如果 |a_i-a_{i-1}|\ne1 的值超过两个，必然无解。

当求出 y 后，对于权值为 a 的点，可以求出它的行，列（怎么求自己想），所以再扫一遍所有的 a_i(i\ge2)，如果 |a_i-a_{i-1}|=1，则需判断 a_i 和 a_{i-1} 是否在同一行即可。

对于 x，直接输出 10^9 即可。

code

#include<bits/stdc++.h>

using namespace std;

const int N = 2e5 + 1;

int n, a[N], num = 0;

int main(){
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n;
  for(int i = 1; i <= n; i++)
    cin >> a[i];
  for(int i = 2; i <= n; i++){
    if(abs(a[i] - a[i - 1]) == 1) continue;
    if(a[i] == a[i - 1]) return cout << "NO", 0;
    if(num && abs(a[i] - a[i - 1]) != num) return cout << "NO", 0;
    num = abs(a[i] - a[i - 1]);
  }
  if(!num) num = 1e9;
  for(int i = 2; i <= n; i++){
    if(abs(a[i] - a[i - 1]) == 1 && (a[i] - 1) / num != (a[i - 1] - 1) / num) return cout << "NO", 0;
  }
  cout << "YES\n1000000000 " << num;
  return 0;
}