本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-10-23 14:41:50

CF1733E Conveyor

题意

给定一个 $n,m$ 的矩阵，每时刻在 $(1,1)$ 上新增一个人，每个点有初始为向右的方向，每个人每时刻都会向当前点的方向走一格，然后翻转原点的方向（向右或向下）。$Q$ 次询问，每次问在 $t$ 时刻的时候，$(x,y)$ 上有没有人。

$n,m=120,x,y<120,t\le10^{18},Q\le 10^4$。

思路

看到 $t$ 很大，显然我们不能直接模拟矩阵变化的过程。

我们发现，对于一个点 $(i,j)$，它的方向一定是“右下右下右下...”的形式（第一个方向是右）。这其实就是告诉了我们，如果有 $p$ 个人经过了这个点，那么一定会有 $\lceil \frac{p}{2} \rceil$ 个人往右走，$\lfloor \frac p 2 \rfloor$ 个人往下走。

知道了这个性质，我们就可以发现，对于一个点，我们只要知道了它上面和左面走过的人数，就可以求出经过此点的人数。这个可以用 DP 求解。

那如何知道具体某个时刻一点上是否有人呢？对于询问的时刻 $t$，我们可以求出它在 $t$ 时刻走过多少人和在 $t-1$ 时刻走过多少人，如果两结果不等，那么就说明在 $t$ 时刻有人，反之没人。

单次询问复杂度 $O(nm)$，由于 $n,m$ 同阶，则总复杂度 $O(Qn^2)$。

代码

注意 DP 状态的初值。

#include<bits\/stdc++.h>
#define int long long
#define F(i,l,r) for(int i=(l); i<=(r); i++)
using namespace std;

int T;
int f[2][130][130];

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	
	cin>>T;
	F(cas,1,T){
		int t,x,y; cin>>t>>x>>y;
		memset(f,0,sizeof f);
		f[0][1][1]=t-x-y+1, f[1][1][1]=t-x-y;
		++x, ++y;
		F(i,1,x) F(j,1,y)
			F(o,0,1) f[o][i][j] += f[o][i-1][j]\/2 + (f[o][i][j-1]+1)\/2;
		cout<<(f[0][x][y]-f[1][x][y]>0?"YES\n":"NO\n");
	}
	
	return 0;
}