【MXOJ-X1-T2】简单的有限网格问题

题意分析

由于题目让我们求的是全部的 $(n+m-2)^2$ 种情况下，能捕捉到的星星数量之和，又因为题目给的 $n,m$ 非常大（$10^{18}$），所以我们可以考虑研究每一颗星星能被捕获的方案数。这样的好处之一就是边读入就边解决了，不然呢？你开一个 $10^{36}$ 的数组？

我们可以以捕捉器初始位置 $(x,y)$ 为原点建立一个平面直角坐标系，我把星星的位置分成了三种情况：在象限内、在横轴上和在纵轴上。

分类讨论

象限内

如果格子在象限内，那么至少需要 $2$ 步才能捕获到星星。而我们第一步就要将捕捉器的横坐标移到 $p$ 或纵坐标移到 $q$。

之后要保证碰到星星，那么捕捉器可以到达从星星到边缘的任意一个整点。从星星在相对于捕捉器的象限位置来看，即有 | | 第三象限 | 第一象限 | | :----------- | :----------- | :----------- | | 第二象限 | $p$ | $q$ | | 第四象限 | $m-q+1$ | $n-p+1$ |

我们就能得到如下判断代码：

if ( p < x ) s += p;
else s += n - p + 1;
if ( q < y ) s+=q;
else s += m - q + 1;

x 轴上

当星星在坐标系的 $x$ 轴上，即与捕获器的横坐标相等——$x=p$ 时，那捕获器的第一步就必须垂直移动：如果第一步使 $x\neq p$，那第二步仅凭一步是无法将星星捕获的。

如果第一步捕获了该星星，根据上文可得知有 $q$ 或 $m-q+1$ 种可能性。那第二步就可以去任意一个可以移动到的新位置了。如果第二步水平移动，共有 $n-1$ 种可能；如果垂直移动，共有 $m-1$ 种可能。即 | $q<y$ | $(n-1+m-1)\cdot q\Rightarrow(n+m-2)\cdot q$ | | ----------- | :----------- | | $q>y$ | $(n-1+m-1)(m-q+1)\Rightarrow(n+m-2)(m-q+1)$ |

如果第一步没有捕获星星，且捕捉器仍然与星星处于同一横坐标，那就有 $m-q-1$ 或 $m-(m-q+1)-1$ 种可能。比上文多减的 $1$ 是捕捉器原位置，因为 你可以将捕捉器移动到同行或同列的某个位置，使得新位置与原位置不同 。

而这样第二步就需要去捕获星星，与上文相同有 $q$ 或 $m-q+1$ 种可能。
即： | $q<y$ | $(m-q-1)\cdot q$ | | ----------- | ----------- | | $q>y$ | $(m-q+1)[m-(m-q+1)-1]\Rightarrow(m-q+1)(q-2)$ |

然后将两种可能性相加，得到 | $q<y$ | $q\cdot(2m+n-3-q)$ | | ----------- | ----------- | | $q>y$ | $(m-q+1)(n+m+q-4)$ |

代码：

if ( q < y ) s += q * ( m * 2 + n - 3 - q );
else s += ( m - q + 1 ) * ( n + m + q - 4 );

y 轴上

类似地，我们有 $y=q$ 时的判断： | $p<x$ | $p\cdot(2n+m-3-p)$ | | -----------: | ----------- | | $p>x$ | $(n-p+1)(n+m+p-4)$ |

一种特殊情况

如果星星的位置与捕捉器重合，那这 $(n+m-2)^2$ 种路径每种都可以捕获星星。不过题目数据中没有出现这种情况。

代码编写

将以上情况汇总，就可以编写出代码了。

#include<iostream>
using namespace std;
int main(){
	long long n,m,x,y,s=0,p,q;
	int k;
	cin>>n>>m>>k>>x>>y;
	while(k--){
		cin>>p>>q;
		if(p==x&&q==y)s+=(n+m-2)*(n+m-2);
		else if(p==x){
			if(q<y)s+=q*(m*2+n-3-q);
			else s+=(m-q+1)*(n+m+q-4);
		}
		else if(q==y){
			if(p<x)s+=p*(n*2+m-3-p);
			else s+=(n-p+1)*(n+m+p-4);
		}
		else{
			if(p<x)s+=p;
			else s+=n-p+1;
			if(q<y)s+=q;
			else s+=m-q+1;
		}
	}
	cout<<s;
	return 0;
}

当然你把这份代码直接交上去可能连 85 分也得不到，因为 求捕捉到的星星数量之和，答案对 $10^9+7$ 取模。

好，我取模了，我甚至每次运算都取了模，然而还是只得 85 分。看来 long long 也会爆，所以我们可以高精度，但是我用的是int128。

int128 是这么定义的：__int128_t n;——定义了一个叫 n 的变量。它有个坏处就是不能直接用 cin 和 cout 输入输出，但是这难不倒机智的OIer我们直接用 long long 输入再赋值就行了。

最终代码

#include<iostream>
using namespace std;
const long long mod=1000000007;
int main(){
	long long n1,m1,x1,y1,s=0,p1,q1;
	int k;
	cin>>n1>>m1>>k>>x1>>y1;
	__uint128_t n=n1,m=m1,x=x1,y=y1,p,q;//uint128的意思就是无符号的int128，我为了保险用的是uint128.
	while(k--){
		cin>>p1>>q1;
		p=p1;
		q=q1;
		if(p==x&&q==y)s+=(n+m-2)*(n+m-2);
		else if(p==x){
			if(q<y)s+=q*(m*2+n-3-q)%mod;
			else s+=(m-q+1)*(n+m+q-4)%mod;
		}
		else if(q==y){
			if(p<x)s+=p*(n*2+m-3-p)%mod;
			else s+=(n-p+1)*(n+m+p-4)%mod;
		}
		else{
			if(p<x)s+=p;
			else s+=n-p+1;
			s%=mod;
			if(q<y)s+=q;
			else s+=m-q+1;
		}
	}
	cout<<s%mod;
	return 0;
}

（鞠躬）

标题

思路

解题方法

复杂度

时间复杂度:

添加时间复杂度, 示例： $O(n)$

空间复杂度:

添加空间复杂度, 示例： $O(n)$

Code

#1114514