#4697. 格

题目描述

题解

看对题目！

首先我们可以把答案看成对于被经过的格子，最后经过的是第几天的总和

对于 $n>1,m>1$ 的时候，如果 $k\ge nm$ ，那说明你可以现在原地蹲着，等到最后的时候找一条路走满这 $nm$ 个格子，考虑到一个网格图中如果 $n,m$ 都是奇数，那么对于一个格子 $(x,y)$ ，如果 $x+y$ 是偶数那它就存在哈密顿路径，所以如果一开始你在 $(x,y)$ 且 $x+y$是奇数的格子上的话，你可以趁第一天下午溜过去然后蹲着；如果 $n,m$ 有一个是偶数，那图中存在哈密顿回路，因此答案就是 $k-nm+1+...+k$ 。如果 $k<nm$ 的话，那就直接走就好了，答案就是 $1+...+k$

对于 $n=1$ 的情况，假设 $v=min(y,m-y+1)$ 。如果 $m-v+1\ge k$ 的话，那就直接走就好了，答案就是 $1+...+k$ ，如果 $k\ge m+m-v-1$ 的话说明你可以先往小的方向走然后蹲着，等到最后再出来，否则的话你就可以先往小的方向走几步，然后再往大的方向走即可

代码

#include <bits/stdc++.h> #define LL long long using namespace std; const LL P=; int T;LL n,m,k,X,Y; LL C(LL l,LL r){ 
    return (l+r)%P*((r-l+1)%P)%P*((P+1)>>1)%P; } void work(){ 
    scanf("%lld%lld%lld%lld%lld",&n,&m,&X,&Y,&k); if (n>1 && m>1) printf("%lld\n",C(max(k-n*m,0ll)+1,k)); else{ 
    if (m==1) swap(n,m),swap(X,Y);Y=min(Y,m-Y+1); if (m-Y+1>=k) printf("%lld\n",C(1,k)); else if (k>=m+m-Y-1) printf("%lld\n",C(k-m+1,k)); else printf("%lld\n",C((k+Y-m+1)/2,k)); } } int main(){ 
    for (scanf("%d",&T);T--;work()); return 0; } 

今天的文章
#4697. 格分享到此就结束了，感谢您的阅读。