CF1733E Conveyor
我们发现若 \((t,x,y)\) 存在史莱姆，则它一定是第 \(t-(x+y)+1\) 只史莱姆。
处理这只史莱姆在第 \(t\) 秒的位置不是很容易。但是我们可以考虑作差。
令 \(f_1[i][j]\) 为前 \(t-(x+y)+1\) 只史莱姆在 \(t\) 秒内经过 \((i,j)\) 的数量。
令 \(f_2[i][j]\) 为前 \(t-(x+y)\) 只史莱姆在 \(t\) 秒内经过 \((i,j)\) 的数量。
则 \(f_1[x][y]-f_2[x][y]=0/1\) 就是第 \(t-(x+y)+1\) 只史莱姆在第 \(t\) 秒到达 \((x,y)\) 的情况。
时间复杂度 \(O(qn^2)\)。
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=120;
int q,x,y,t,f1[N][N],f2[N][N];
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>q;while(q--){cin>>t>>x>>y;memset(f1,0,sizeof f1),memset(f2,0,sizeof f2);f1[0][0]=t-x-y+1,f2[0][0]=t-x-y;for(int i=0;i<=x;i++){for(int j=0;j<=y;j++){if(i) f1[i][j]+=f1[i-1][j]/2,f2[i][j]+=f2[i-1][j]/2;if(j) f1[i][j]+=(f1[i][j-1]+1)/2,f2[i][j]+=(f2[i][j-1]+1)/2;}}if(f1[x][y]^f2[x][y]) cout<<"YES\n";else cout<<"NO\n";}return 0;
}