题解：CF1733E Conveyor
Handezheng
·
·
题解
CF1733E Conveyor
题意
给定一个 n,m 的矩阵，每时刻在 (1,1) 上新增一个人，每个点有初始为向右的方向，每个人每时刻都会向当前点的方向走一格，然后翻转原点的方向（向右或向下）。Q 次询问，每次问在 t 时刻的时候，(x,y) 上有没有人。
### 思路
看到 $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 状态的初值。
```cpp
#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;
}
``````