10 条题解

  • -1

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

    比赛的时候入场晚惹QAQ……以为要完蛋了,结果打开第一题,仔细一看:有没有种可能,这题找找规律就秒了?再一看数据:我的天,nnmm 都大于 11,特判都不用了???

    根据样例,可以猜测:当 nnmm 的奇偶性不同时,答案是 22;当 nnmm 的奇偶性相同时,答案是 33

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

    至于样例剩下的那一行呢?可以发现,nnmm 的奇偶性相同,所以我们可以大致猜测:在 nnmm 奇偶性相同时,答案为 33

    我们也可以通过模拟来看这个猜测是否正确。例如 (6,6)(6,6)。我们可以发现:(1,1)=>(1,6)=>(5,6)=>(6,6)(1,1)=>(1,6)=>(5,6)=>(6,6)。总共用了 33 步。下面,我们再来试一组(2,2)(2,2)(1,1)=>(2,1)=>(2,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;
    }
    

    信息

    ID
    7
    时间
    1000ms
    内存
    512MiB
    难度
    2
    标签
    递交数
    350
    已通过
    246
    上传者