蒟蒻在 MXOJ 的第一篇题解，当然，这篇题解在洛谷上早已通过，原作者：jiangyunuo。
吐槽一下，梦熊也太难操作了吧 QWQ，等等，好像不用审核。

题目大意：

本题意思很简单很简单，一个机器人在第奇数次移动要移动奇数步，在第偶数次移动也同理。最终，我们要让这个机器人从 $(1,1)$ 移动到 $(n,m)$。

大体思路：

本题主要考察的是奇偶性，别看它题面条件很多，感觉很复杂，但当你仔细观察样例的时候，你会发现，无论 $n$ 和 $m$ 有多大，但结果只有 $2$ 和 $3$，其实本题就两种情况：

1. $n$ 和 $m$ 奇偶性相同。
2. $n$ 和 $m$ 奇偶性不相同。

仔细想想，当第一种情况发生时，如果 $n$ 和 $m$ 都是偶数，那么可以按 $n \to m \to n$ 的顺序，$n$ 和 $m$ 分别表示横轴和纵轴，这就表示走横轴和纵轴的顺序，因为奇数加奇数等于偶数，偶数本身是偶数，可行；如果 $n$ 和 $m$ 都是奇数，那么可以按 $n \to m \to m$ 的顺序，因为奇数本身是奇数，而奇数加偶数等于奇数，因此可行，两种情况都只要 $3$ 步。
当第二种情况发生时，我们可以先走要走长度为奇数的，再走另一条要走长度为偶数的，当然如果 $n$ 或 $m$ 为奇数时那要走的长度是偶数，如果为偶数，那要走的长度是奇数（因为要走的长度为尾减头），只需 $2$ 步即可。

代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int t,m,n;
	cin>>t;
	for(int i=1;i<=t;i++){
		cin>>n>>m;
		if((n%2)==(m%2))cout<<3<<endl;  //判断奇偶性是否相同，再根据奇偶性选择输出 2 或 3。
		else cout<<2<<endl;
	}
return 0;
}

X1A 题解

第五篇题解。

下面将能使 $x$ 坐标满足要求的移动和能使 $y$ 坐标满足要求的移动记为最终移动。对于每组询问，先算出 $n$ 和 $m$ 的奇偶性，判断是否相等。如果相等，则需要一次最终移动，而第二次移动是无法成为最终移动的，所以一共需要 $3$ 次。否则，进行两次最终移动即可。

代码：

#include<iostream>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,m;
        cin>>n>>m;
        if(n%2==m%2)cout<<"3\n";
        else cout<<"2\n";
    }
    return 0;
}

思路

由题目可知，我们可以向任意方向移动任意个单位长度。 但是此时要求对于第 $i$ 次移动的单位长是有限制的。

对于奇偶的限定导致我们只需要判断目标的奇偶是否相同即可。

而且一次可以移动任意的单位长度，所以答案一定小于等于$3$。

复杂度

时间复杂度： $O(t)$

空间复杂度： $O(1)$

Code

#include<bits/stdc++.h>
using namespace std;
int t;
int main()
{
	std::cin.tie(0);
	std::cout.tie(0);
	cin>>t;
    while(t--){
        int a,b;
        cin>>a>>b;
        if(a%2!=b%2) cout<<2<<"\n";
        else cout<<3<<"\n";
    }
	return 0;
} 

简单的无限网格问题

题目大意

有一个无限大的网格，有一个点在 $(1,1)$ 处。它可以向上、下、左、右四个方向移动，移动的格数不限。但对于每个第 $i$ 次移动，格数的奇偶性必须与 $i$ 相同。求移动到 $(n,m)$ 的最少步数。

思路

妥妥的分类讨论题。

首先，我们发现题目中提到了奇偶性这三个字，那么我们就优先从奇偶性来分析。

因为题中提到：$n,m\ge 2$，因此，不可能 $1$ 步走到。考虑剩下的一种最优情况，即 $2$ 步走到。此时正好走了一个奇数和一个偶数，而此时到了 $(n,m)$，说明 $n,m$ 的奇偶性不同。

既然有奇偶性不同的情况，当然也得考虑奇偶性相同的情况。此时，很显然 $2$ 步也是走不到的。这时，我们在分两个情况进行讨论。

1. $n,m$ 均为奇数，此时我们可以先横向走到 $(1,m)$，再纵向走到 $(n+1,m)$ 或 $(n-1,m)$。接着又可以走奇数步，就把差的 $1$ 格补上就好了。

2. $n,m$ 均为偶数，此时我们可以先横向走到 $(1,m+1)$ 或 $(1,m-1)$，再纵向走到 $(n,m+1)$ 或 $(n,m-1)$。接着又可以走奇数步，就把差的 $1$ 格补上就好了。

综上所述，奇偶性不同时，需要 $2$ 步走到；奇偶性相同时，需要 $3$ 步走到。

复杂度

时间复杂度:

时间复杂度： $O(t)$

空间复杂度:

空间复杂度： $O(1)$

Code

#include <bits/stdc++.h>
using namespace std;
int main(){
	int t,n,m;
	cin>>t;
	while(t--){
		cin>>n>>m;
		if(n%2 != m%2) cout<<2<<endl;//奇偶性不同
		else cout<<3<<endl;//奇偶性相同
	}
	return 0;
}

X1A. 「KDOI-05」简单的无限网格问题

判断横纵坐标的奇偶性

知周所众，显然，本题可以通过观察样例模拟得出结论：当 n，m 奇偶性相同时，答案为 3，否则为 2。

##所以就有了下面的代码：

代码：

#include <bits/stdc++.h> using namespace std; int t,a[100010],b[100010]; int main() { cin >> t; for(int i=1;i<=t;i++){ cin>>a[i]>>b[i]; } for(int i=1;i<=t;i++){ if(a[i]%21&&b[i]%20) cout<<2<<endl; else if(a[i]%20&&b[i]%21) cout<<2<<endl; else if(a[i]%20&&b[i]%20) cout<<3<<endl; else if(a[i]%21&&b[i]%21) cout<<3<<endl; } return 0; }

题意：

要从起点 $(1,1)$ 的位置走到 $(n,m)$ 的位置，走第奇数次步时可以向上下左右一个方向走奇数个单位长度，第偶数次步时走偶数个单位长度，求最小需要多少步。

思路：

把网格看做一个大小为 $n \times m$ 的网格，要使步数小，那么每次就尽量走到底。

用样例举例：

8 7

从 $(1,1)$ 出发，到 $(8,1)$ 的距离刚好是奇数，算一步。从 $(8,1)$ 出发，到 $(8,7)$ 的距离刚好是偶数，算一步。最后答案就是 $2$ 步。

999999 1000000

从 $(1,1)$ 出发，到 $(1,1000000)$ 的距离刚好是奇数，算一步。从 $(1,1000000)$ 出发，到 $(999999,1000000)$ 的距离刚好是偶数，算一步。最后答案就是 $2$ 步。

3 3

从 $(1,1)$ 出发，到 $(1,2)$ 的距离是奇数，算一步。从 $(1,2)$ 出发，到 $(3,2)$ 的距离是偶数，算一步。从 $(3,2)$ 出发，到 $(3,3)$ 的距离是奇数，算一步。最后答案就是 $3$ 步。

从前两个样例中可以看出若 $n$ 与 $m$ 中有一个为奇数且另一个为偶数，那么需要的步数最小为 $2$。这条结论也不难证明，因为这样走的两个方向的距离是一个奇数和一个偶数，刚好可以走两步，所以答案为 $2$。

从第三个样例可以看出若 $n$ 与 $m$ 都是奇数时，最小步数为 $3$，这也不难证明，在结论一的基础上我们可以证明这条结论，一个奇数与一个偶数（结论一的条件）和两个奇数（结论二的条件）只改变了一个数，就是偶数变成了奇数，偶数与奇数的差是奇数，第三步刚好是走奇数步，所以得到了第二条结论。

现在考虑了两个奇数的情况与一奇一偶的情况，还剩下一个两个偶数的情况。在此情况下，所需最小步数为 $3$，这也可以在结论一的基础上证明，与证明结论二的方法基本相同。两个偶数与一奇一偶改变一个数，奇数变成了偶数，偶数与奇数的差为奇数，第三步刚好是走奇数步，所以得到了第三条结论。

将上面三个结论总结一下，就是当 $n$ 与 $m$ 中有一个奇数和一个偶数，那么只需要走 $2$ 步，否则要走 $3$ 步。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int t;
signed main(){
	cin>>t;
	while(t--){
		int n,m;
		cin>>n>>m;
     	if((n%2==1 and m%2==0) or (n%2==0 and m%2==1))cout<<2<<endl;
    	else cout<<3<<endl;
   	}
	return 0; 
}

题解：简单的无限网格问题

解题方法

容易发现，当 $n,m$ 奇偶性相同时，最小操作次数为 $3$；当 $n,m$ 奇偶性不同时，最小操作次数为 $2$。每次输入 $n,m$ 时判断奇偶性即可。时间复杂度 $O(T)$，期望得分 $100$ 分。

复杂度

时间复杂度:

$O(T)$

空间复杂度:

$O(1)$

Code

#include<bits/stdc++.h>
using namespace std;
int t,n,m;
int rd()//快读
{
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-')
			f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}
int main()
{
	t=rd();
	while(t--)
	{
		n=rd();m=rd();
		if((n&1)!=(m&1))//相当于if(n%2!=m%2)
			printf("2\n");
		else
			printf("3\n");
	}
	return 0;
}

简单的无限网格问题 题解

题目链接

题目分析

这是一道找规律的题目。

考虑从他应该怎么走入手，进行分类讨论：

• 当行数之差与列数之差恰好一奇一偶时，可以用 $2$ 步完成操作，用第一步抵消差为奇数，用第二步抵消差为偶数即可；

• 当行数之差与列数之差奇偶性相同时，我们必须要在以起点和终点为对角线的一个矩形的一条边上花费两次操作，所以需要 $3$ 次操作即可完成。

参考代码

#include<bits/stdc++.h>
#define c continue;
using namespace std;
int T;
int n, m;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> T;
	while (T--) {
		cin >> n >> m;
		if (((n - 1) % 2 == 1 && (m - 1) % 2 == 0) || ((m - 1) % 2 == 1 && (n - 1) % 2 == 0)){
			cout << "2\n";
			c;
		}
		cout << "3\n";
	}
	return 0;
}

P10713【MX-X1-T1】「KDOI-05」简单的无限网格问题题解

比赛的时候入场晚惹QAQ……以为要完蛋了，结果打开第一题，仔细一看：有没有种可能，这题找找规律就秒了？再一看数据：我的天，$n$ 和 $m$ 都大于 $1$，特判都不用了？？？

根据样例，可以猜测：当 $n$ 和 $m$ 的奇偶性不同时，答案是 $2$；当 $n$ 和 $m$ 的奇偶性相同时，答案是 $3$。

我们可以实际模拟一组实际数据：例如样例没有的 $(3,2)$。因为我们可以无限移动格数，所以我们只需要根据题目的限制，然后这样移：$(1,1)=>(1,2)=>(3,2)$，然后就能到达 $(3,2)$。再比如样例中一组超大的数据（超大？）： $(999999,1000000)$。我们可以这样：$(1,1)=>(1,1000000)=>(999999,1000000)$。

至于样例剩下的那一行呢？可以发现，$n$ 和 $m$ 的奇偶性相同，所以我们可以大致猜测：在 $n$ 和 $m$ 奇偶性相同时，答案为 $3$。

我们也可以通过模拟来看这个猜测是否正确。例如 $(6,6)$。我们可以发现：$(1,1)=>(1,6)=>(5,6)=>(6,6)$。总共用了 $3$ 步。下面，我们再来试一组$(2,2)$：$(1,1)=>(2,1)=>(2,3)=>(2,2)$。

下面我们的代码就很好写了：

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int t;
	cin>>t;
	for(int i=1;i<=t;i++)//多组数据
	{
		int n,m;
		cin>>n>>m;
		if((n%2==0&&m%2==1)||(n%2==1&&m%2==0))//如果n和m奇偶性不同，输出2
		{
			cout<<2<<endl;
		}
		else if(n%2==m%2)//如果n和m奇偶性相同，输出3
		{
			cout<<3<<endl;
		}
	}
	return 0;
}

思路

简单签到，因为他说 $x_i$ 的奇偶性只要与 $i$ 的奇偶性相同即可，也就是说 $x_i$ 可以无限大，那么不难想到，若一个为奇数，一个为偶数，则第一次到为奇数的坐标，第二次到偶数的坐标，如果要到 $(3,4)$ 这个点，则 $(1,1)-(3,1)-(3,4)$。如果要到 $(6,5)$，则 $(1,1)-(1,5)-(6,5)$，两种情况可以证明都只需要两步，所以得出第一个结论，当 $n$ 与 $m$ 的奇偶性不同时，则直接输出 $2$。如果奇偶性相同呢，不难发现，当两个数都为奇数时，只要让一个数做两次即可，因为当 $i$ 为 $1$ 时，其中一个奇数可以直接到达，而另一个数需要加一次偶数再加一次奇数完成。例如要到 $(5,7)$ 这个点，则其中一种方法为 $(1,1)-(5,0)-(5,4)-(5,7)$。当两个数都为奇数时，方法相同，因为当 $i$ 为 $1$ 时，其中一个偶数可以先加上一个奇数，而另一个数就可以在下一次直接完成，到下次 $i$ 为奇数时前面那个只加了一个奇数的偶数就可以再加一个奇数，从而完成。例如要到 $(4,8)$ 这个点，则其中一种方法为 $(1,1)-(1,0)-(1,8)-(4,8)$，那么这两种奇偶性相同的情况就都只要输出 $3$ 即可。

最后总结一下结论：

• 当两个数奇偶性不同时输出 $2$。
• 当两个数奇偶性相同时输出 $3$。

每次判断时间复杂度为 $O(1)$，总时间复杂度为 $O(t)$，可以通过此题。

代码

#include<bits/stdc++.h>
#define int long long
const int mod = 1e9 + 7;
using namespace std;

signed main()
{
	int t;
	cin >> t;
	while(t--){
		int n, m;
		cin >> n >> m;
		if((n % 2 == 0 && m % 2 != 0) || (n % 2 != 0 && m % 2 == 0)){
			cout << 2 << endl;
		}
		else{
			cout << 3 << endl;
		}
	}
	return 0;
}