一道挺有意思的题。
考场上推了半天，没推出来，直接弃了。
但是实际上算法很简单。
题目链接。
题意
现在有一个长度、宽度都为
的网格，每个格子上都是一个传送带。
从上数第 行，从左数第 列的网格称为 ，最左边的列是第 列（行同理）。
每一个格子上的传送带一开始都指向右边。
一开始，传送带
上有一滴水，其他格子是空的，每一秒会进行这样的变化：
- 每一滴水按照传送带方向，挪一个格子。如果对应方向上没有格子，水滴就会消失。两个水滴同时到一个格子，它们就会合并。
- 在上次移动前的时候所有有水的各自，全部切换方向（原来向右的指向下方，原来向下的指向右方）。
- 传送带
上多出一滴水。
现在有 组询问，每一次给出
，问在 秒时，格子 上有没有水。
每一秒传送带的情况可以去原题查看图片。
题解
首先我们定义“对角线 "为所有满足
的格子 。
然后我们就会发现，每一次移动时，每一个水滴不是向右移，就是向下移。
所以如果上一秒一个水滴在对角线 ，那么这个水滴在移动之后一定在对角线
。
或者再加强一下这个结论：一个在时间 出现的水滴，在时间 时（一共移动了 次）会出现在对角线 的一个格子上。
所以我们可以知道，所有的水滴是永远不会相遇（合并）的。
然后我们还能知道，对于一组询问 ，假如在时间 时 上有水滴，那么这个水滴一定是在时间
出现的。
所以对于每一个
的询问，我们可以直接进行回答（永远不可能出现这样的情况）。
然后对于每一组询问，令数组 为，前 出现的所有水滴中，经过格子 的有多少个。
首先我们知道，每一个水滴一开始都在 ，所以就会有 。
然后呢？怎么转移？
我们会发现，假如一共有
个水滴经过了格子 ，那么这
个水滴中，一定会有
个水滴向右走，有
个水滴向下走。
所以我们就可以得到转移：
现在我们就可以直接模拟，这个水滴的行走路径了，大概是这个样子：
假如这个水滴现在在格子 ，那么我们知道，这个水滴一定是第
个到达这个水滴的格子，因为我们的
统计的是这个水滴及之前的水滴中，到达过这个格子的水滴数。
那么如果 ，这个水滴一定向下走。
否则就会向右走。
我们模拟 步，看有没有 就可以了。
时间复杂度为 。
代码
代码里
的推导和上面不太一样，使用的是顺推。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
| #include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<map>
using namespace std;
using ll=long long;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
inline int read()
{
int s=0,w=1;char ch;
while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
inline ll lread()
{
ll s=0,w=1;char ch;
while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
ll dp[121][121];
int main()
{
int T=read();
while(T--)
{
ll t=lread();int x=read(),y=read();
if(t<x+y)
{
printf("NO\n");
continue;
}
memset(dp,0,sizeof(dp));
dp[0][0]=t=t-x-y+1;
for(int i=0;i<120;i++) for(int j=0;j<120;j++)
{
if(j!=119) dp[i][j+1]+=(dp[i][j]+1)/2;
if(i!=119) dp[i+1][j]+=dp[i][j]/2;
}
ll nowx=0,nowy=0;
for(int i=1;i<=x+y;i++)
{
if(dp[nowx][nowy]&1) nowy++;
else nowx++;
}
if(nowx==x) printf("YES\n");
else printf("NO\n");
}
return 0;
}
|
感谢观看！