CF1733E

模拟赛题，虚高，场上几乎秒了。

首先考虑在 $t$ 时刻经过 $(x,y)$ ，那么它一定是在 $t-x-y$ 时刻从 $(0,0)$ 出发。于是问题就变成了这个时刻出发，是否会经过 $(x,y)$ 。

第一想法肯定是看每个时刻开始的移动是否有规律。打表出来发现没有什么规律。于是换个思路，看每个位置被经过了多少次。

类似 pkusc2024 D2T1 地，发现对于 $(x,y)$ 这个点，每经过两次 $(x-1,y)$ 就会经过一次 $(x,y)$ ， $(x,y-1)$ 同理。于是先令一个点走完（走到 $x>100$ 或 $y>100$ ）后下一个点再出发，设 $dp_{i,j}$ 为 $(i,j)$ 累计被经过的次数，则有 $dp_{0,0}=t+1,dp_{i,j}=\left\lfloor \frac{dp_{i-1,j}}{2}\right\rfloor+\left\lceil \frac{dp_{i-1,j}}{2}\right\rceil$ 。

于是我们就可以在 $O(xy)$ 的时间复杂度内求出 $dp_{x,y}$ 。这有什么用呢？想到差分。只要知道 $t-x-y$ 时刻的 $dp_{x,y}$ 和 $t-x-y-1$ 时刻的，那么就可以知道 $t-x-y$ 时刻出发的这个点是否经过 $(x,y)$ 了！

$O(qxy)$ 解决。

code：

int n,m;
ll dp[N][N];
ll solve(ll t,int x,int y){
	if(t<0){
		return 0;
	}
	dp[0][0]=t+1;
	rep(i,0,x){
		rep(j,0,y){
			if(!i&&!j){
				continue;
			}
			dp[i][j]=0;
			if(i){
				dp[i][j]+=dp[i-1][j]/2;
			}
			if(j){
				dp[i][j]+=(dp[i][j-1]+1)/2;
			}
		}
	}
	return dp[x][y];
}
void Yorushika(){
	read(m);
	while(m--){
		ll t,x,y;read(t,x,y);
		if(!t){
			if(!x&&!y){
				puts("YES");
			}else{
				puts("NO");
			}
			continue;
		}
		if(t-x-y<0){
			puts("NO");
			continue;
		}
		puts(solve(t-x-y,x,y)-solve(t-x-y-1,x,y)?"YES":"NO");
	}
}
signed main(){
	int t=1;
	//read(t);
	while(t--){
		Yorushika();
	}
}

感谢您的支持，我会继续努力的!