Codeforces 954C Matrix Walk (思维)

题目链接： Matrix Walk

题意：设有一个N×M的矩阵，矩阵每个格子都有从1～n×m的一个特定的数，具体数的排列如图所示。假设一个人每次只能在这个矩阵上的四个方向移动一格(上下左右)，给出一条移动的轨迹上的数字，求出满足这个人移动轨迹的一格矩阵的N和M。

题解：首先可以确定的是左右移动的话，相邻格子之间数字相差的绝对值一定是1，而向上或向下移动的数字只差的绝对值一定相等。按照这个思路，判断给出的轨迹相邻格子之间的差值，看是否差值的绝对值只有1和另外一个数字就可以基本解决问题了。但是这里还要进行特判，首先是轨迹中差值只有1的情况，就直接输出YES并将轨迹中的最大值取出，输出1，max。还要判定的是另一种情况，就是假设现在向上向下移动的数值确定了，假设为x，就有M = x。要注意的是差值为1的情况中，行尾的格子是不能移动到行头的(行头的格子同理不能移动到行尾)。所以遍历一下，看一下有没有这种情况。

#include<bits/stdc++.h>
using namespace std;
const int MAX_N = 2e5+9;
const int INF = 1e9+9;
int N,M,S;
int vec[MAX_N];
int main(){
    while(cin>>N){
        int maxn = -1;
        for(int i=0;i<N;i++){
            scanf("%d",&vec[i]);
            maxn = max(maxn,vec[i]);
        }
        int pos = -1;
        bool flag = true;
        for(int i=1;i<N;i++){
            int t = max(vec[i] - vec[i-1],vec[i-1] - vec[i]);
            if(t != 1){
                if(t ==0 ){
                    flag = false;
                    break;
                }
                if(pos == -1) pos = t;
                else if(pos != t){
                    flag = false;
                    break;
                }
            }
        }

        if(!flag){
            cout<<"NO"<<endl;
        }else{
            if(pos == -1){
                cout<<"YES"<<endl;
                cout<<1<<" "<<maxn<<endl;
            }
            else{
                int pre = maxn / pos;
                if(maxn % pos) pre++;

                bool f = true;
                for(int i=0;i<N-1;i++){
                    if(vec[i]%pos == 0 && vec[i] - vec[i+1] == -1){
                        f = false;  //cout<<"??"<<endl;
                        break;
                    }
                    else if(vec[i] %pos == 1 && vec[i]-vec[i+1] == 1) {
                        //cout<<vec[i]<<"...."<<vec[i+1]<<endl;
                        f = false; //cout<<"?????????"<<endl;
                        break;
                    }
                }
                if(!f){
                    cout<<"NO"<<endl;
                }else {
                    cout<<"YES"<<endl;
                    cout<<pre<<" "<<pos<<endl;
                }
            }
        }

    }
    return 0;
}