CF1733E Conveyor 题解

题目链接：Conveyor

题意：

有一个 \(120\) 行，\(120\) 列的棋盘，行列编号均为 \(0,1,\cdots,119\)，\(i\) 行 \(j\) 列的格子的坐标为 \((i,j)\)，左上角的格子坐标为 \((0,0)\)。每一个格子上都有一个传送带，初始方向为右。

一开始，有一个史莱姆在 \((0,0)\)，其他格子都什么也没有，每一秒传送带的方向都会如下变化：

• 所有的史莱姆随着传送带的方向移动一格。
  • 如果传送带的方向没有格子，史莱姆就会离开棋盘；
  • 如果两个史莱姆到了同一个格子上，就会合并为一个史莱姆。
• 所有有史莱姆的传送带的方向都会改变，向右的会变成向下的，向下的会变成向右的。
• \((0,0)\) 处会出现一个史莱姆。

给定 \(q\) 个询问，问在第 \(t\) 秒，\((x,y)\) 格是否有史莱姆。

输入格式：

第一行，一个整数 \(q\)（ \(1\le q\le10^4\) ），表示询问个数。

每一行询问依次有三个整数 \(t,x,y\)（\(0\le t\le10^{18},0\le x,y<120\)）。

输出格式：

如果在第 \(t\) 秒，\((x,y)\) 格有史莱姆，输出 YES，否则输出 NO。

这个合并两个史莱姆的操作看起来非常难搞。

然而由于每次史莱姆都会往右方/下方走一格，而每个史莱姆的出生时间是不同的

因此这个条件根本没有用！那么很容易想到dp。dp 什么好呢？

考虑记 \(f_{t,x,y}\) 为前 \(t\) 个时刻有多少个史莱姆经过了 \((x,y)\) ，

那么我们只需要判断 \(f_{t,x,y} - f_{t-1,x,y}\) 的结果是否为 \(0\) 即可，这个套路有点像概率期望的那种 dp 。

转移的话，设有 \(t\) 只史莱姆经过了 \((x,y)\) ，那么有 \(\left\lfloor\frac{t+1}{2}\right\rfloor\) 只去了 \((x,y+1)\) ，\(\left\lfloor\frac{t}{2}\right\rfloor\) 去了 \((x,y)\) 。

时间复杂度 \(\mathcal{O}(Tn^2)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define mem(a) memset((a), 0, sizeof(a))
#define N ((int)(155))

int f[N][N], g[N][N];
void solve()
{
    int t, x, y; cin >> t >> x >> y;
    mem(f); mem(g); t -= x + y; f[0][0] = t + 1; g[0][0] = t;
    rep(i, 0, x) rep(j, 0, y)
    {
        f[i + 1][j] += f[i][j] / 2; f[i][j + 1] += (f[i][j] + 1) / 2;
        g[i + 1][j] += g[i][j] / 2; g[i][j + 1] += (g[i][j] + 1) / 2;
    }
    if(t < 0) f[x][y] = 0;
    if(t < 1) g[x][y] = 0;
    cout << (f[x][y] == g[x][y] ? "NO\n" : "YES\n");
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int qwq; cin >> qwq; while(qwq--) solve();
    return 0;
}

---

参考文献：

[1] https://www.luogu.com.cn/article/1ekajnp5