CodeForces - 954C - Matrix Walk

坑题
题目：CodeForces - 954C
题意:矩阵的每一元素可以用 Ai, j = y*(i - 1) + j 来表示，（就是二维数组用一维指针表示的方法），给你一个路径序列，问这样的序列能否在前述矩阵中实现。能输出YES和x，y值（x的值不是必须最优），否则输出NO。
坑点：不能站着不动，任意的a[i] != a[i-1];

思路：

1. for循环找a数组中有没有相同的元素，有直接退出，顺便求出y值，当a中相邻元素绝对值不相差1时，y = abs(a[i] - a[i-1]);因为增减1则就一列（y = 1）没问题，如果是1，2，3，4，6 这种也没关系，之后再for循环检查一遍，看是不是所有a[i] 都在 a[i-1] 旁边就ok了。
2. 做题WA了好多次，WA在第7组的提供个样例
   10
   1 2 3 4 5 6 7 8 9 11
   参考了一篇博客（博客链接），但是它的代码WA了，我给他改AC了，在此也提供他的思路，并给出AC代码。他的思路是两个点要么差1，要么差y，如果差1，但是不相邻，就特判一下。但是他没有考虑到for循环找y值时，y值会被多次修改，以及当只有一列（y == 1）时不需要做判断。

代码实现me：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN = 200010;
int n,a[MAXN];

int dir[4][2] = {{1,0},{0,1},{-1,0},{0,-1}};
bool check(int a1,int a2,int y){
    LL a1x = a1/y + ((a1%y)?1:0);
    LL a1y = a1 - (a1x-1)*y;
    if(a1y > y || a1y < 1)//a[i]超范围 
        return false;
    LL a2x = a2/y + ((a2%y)?1:0);
    LL a2y = a2 - (a2x-1)*y;
    bool flag = 0;
    for(int i=0;i<4;i++){
        LL a2x_ = a2x+dir[i][0];
        LL a2y_ = a2y+dir[i][1];
        if(a2y_ > y || a2y_<1)
            continue;
        if(a2x_ == a1x && a2y_ == a1y){
            flag = 1;
            break;
        }
    }
    if(flag)
        return true;
    return false;
}

int main(int argc, char const *argv[])
{
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    LL y = 1;
    bool ans = 1;
    for(int i=1;i<n;i++){
        if(a[i] == a[i-1]){
            ans = 0;
            break;
        }
        if(y==1 && abs(a[i]-a[i-1])!=1){//不增减一，则可确定y
            y = abs(a[i] - a[i-1]);
        }
    }
    for(int i=1;i<n;i++){
        if(!check(a[i],a[i-1],y)){//a[i]不在a[i-1]旁边，输出错误信息
            ans = 0;
            break;
        }   
    }
    if(ans) 
        cout<<"YES"<<endl<<1000000000<<' '<<y<<endl;
    else 
        cout<<"NO"<<endl;
    return 0;
}

代码实现he：

#include<bits/stdc++.h>
using namespace std;
const int N = 3e5 + 10;
int a[N];
int main(){
    ios_base::sync_with_stdio(0);
    int n;cin>>n;
    int y = 1;
    for (int i = 0; i < n; i++) {
        cin>>a[i];
        if(i == 0) continue;
        if(a[i] == a[i - 1]) {
            cout<<"NO"<<endl;return 0;
        }
        if(y==1 && abs(a[i] - a[i - 1] != 1)) {//修改为只有在y为1时修改
            y = abs(a[i] - a[i - 1]);
        }
    }
    for (int i = 1; i < n; i++) {
        if(y == 1) continue;//y==1时不做判断
        if((abs(a[i] - a[i - 1]) != 1 && abs(a[i] - a[i - 1]) != y)){
            cout<<"NO"<<endl;return 0;
        }
        if(a[i] % y == 0 && a[i - 1] - a[i] == 1) {
            cout<<"NO"<<endl;return 0;
        } else if(a[i] % y == 1 && a[i] - a[i - 1] == 1) {
            cout<<"NO"<<endl;return 0;
        }
    }
    cout<<"YES"<<endl<<1000000000<<' '<<y<<endl;
    return 0;
}

小结：这道题Debug的时间比我想象的要长的多，做了一晚上，醉了，太菜，看不懂英文，理解错题意，无话可说。