codeforces 954C. Matrix Walk(思维模拟)

http://codeforces.com/contest/954/problem/C

题意：

现在有一个大小为xy的矩阵(x,y大小未知)，然后规定A(i,j)的值为y(i-1)+j,并且每次移动只能往四个方向移动。现在输入一个数n,然后输入n个数代表走过的轨迹a1,a2,…,an，问你能不能求出x,y如果能输出YES，并输出x和y,否则输出NO。

题解：

这题不难看出移动的跨度的值的绝对值不是1,就是y,一旦跨度比1大肯定就是y，然后我们就确定了y。但是我们确定了y不代表这个y就是对的(这里我wa了几次)，因为有可能有其他跨度，或者走1的时候对于这个y来说是打斜走的。因此，得出y之后要进行第二次检查，跨度为1的两个点只能在同一行，我们可以用(a[i]+y-1)/y来确定在第几行，同理跨度为y只能在同一列，用a[i]%temp来确定第几列，这样就基本确定能不能找出来了。还有x是不用求的直接1e9就肯定满足了。

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
int a[maxn];
int main()
{
	int n;
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	}
	int temp=1;
	int flag=0;
	for(int i=1;i<n;i++)
	{
		if(abs(a[i]-a[i-1])>1)
		{
				temp=abs(a[i]-a[i-1]);
				break;
		}
	}
	for(int i=1;i<n;i++)
	{
		if(abs(a[i]-a[i-1])==temp)
		{
			if((a[i]%temp)!=(a[i-1]%temp))
			{
				flag=1;
				break;
			}
		}
		else if(abs(a[i]-a[i-1])==1)
		{
			if((a[i]+temp-1)/temp!=(a[i-1]+temp-1)/temp)
			{
				flag=1;
				break;
			}
		}
		else
		{
			flag=1;
			break;
		}
	}
	if(flag)
	{
		cout<<"NO"<<endl;
	}
	else
	{
		cout<<"YES"<<endl;
		cout<<1000000000<<" "<<temp<<endl;
	}
 } 

Q.E.D.