题解：P14153 [ICPC 2022 Nanjing R] 停停，昨日请不要再重现

· · 题解

题解：P14153 [ICPC 2022 Nanjing R] 停停，昨日请不要再重现

Problem

给你一个 n\times m 的网格，网格上有一个需要你确定位置的洞，其余位置上都有一只袋鼠，给定所有袋鼠同步的移动步骤，如果一只袋鼠移出边界或是移到洞中则它会消失，问要是移动后网格中恰剩 k 只袋鼠洞的可能位置的数量。

Solution

首先，容易想到的是，这个移动路径是有范围的，于是考虑统计 x 和 y 方向的移动范围，然后直接排除一些格子，这样能剩下里面一个较小的矩形，假设范围是 (u,l)\sim(d,r)。（如果范围不存在就退出。）

然后，由于每个袋鼠的移动路径都是全等的，所以可以取一个点（此处取左上角 (u,l)）的路径作为代表进行考虑，该路径记为代表路径。

那么再利用我们惊人的注意力就会发现，每一个袋鼠与左上角那个袋鼠的相对位置不改变，于是就会发现，对于代表路径上的每个点，以之为左上角的一个矩形内的格子都是可以抓住袋鼠的。而这个矩形的大小就是前面所说较小矩形的大小。

对于范围内的部分，我们需要记录一下这个位置能抓住一只袋鼠，于是我们就得到了每个范围内的点能抓住几只袋鼠，如果这个数量等于 (r-l+1)(d-u+1)-k，那么这个点就是合法的。

Implementation

先求出小矩形的位置，然后求出其中左上角袋鼠的路径上的所有点，然后利用二维差分，对以这些点为左上角，小矩形大小为大小的矩形内的点的标记全部 +1，然后求前缀和统计即可。

If you TLE

本人已经连续被 memset 坑了两回了（这是第二回），所以，当你 TLE 的时候，删删没用的 memset 吧。

Code

AC Record

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf = 0x3f3f3f3f;
const int N = 1005;

bool vis[N][N];
int chafen[N][N], cfqzh[N][N];
pair<int, int> lujing[N * N];
int ljcnt;

int t, n, m, k;
string s;

signed main() {
    ios :: sync_with_stdio(false);
    cin >> t;
    while (t--) {
        memset(vis, 0, sizeof(vis));
        memset(chafen, 0, sizeof(chafen));
        memset(cfqzh, 0, sizeof(cfqzh));
        ljcnt = 0;
        cin >> n >> m >> k >> s;
        int len = s.length();
        int minx = inf, maxx = -inf, miny = inf, maxy = -inf, dx = 0, dy = 0;
        for (int i = 0; i < len; i++) {
            switch (s[i]) {
                case 'U': {
                    dy--;
                    break;
                }
                case 'D': {
                    dy++;
                    break;
                }
                case 'L': {
                    dx--;
                    break;
                }
                case 'R': {
                    dx++;
                    break;
                }
                default:
                    break;
            }
            minx = min(minx, dx);
            maxx = max(maxx, dx);
            miny = min(miny, dy);
            maxy = max(maxy, dy);
        }
        int u = max(1ll, 1ll - miny);
        int d = min(n, n - maxy);
        int l = max(1ll, 1ll - minx);
        int r = min(m, m - maxx);
        if (l > r || u > d || (r - l + 1) * (d - u + 1) <= 0) {
            if (k)
                cout << "0\n";
            else
                cout << n * m << "\n";
            continue;
        }
        int x = u, y = l;
        vis[x][y] = 1;
        lujing[++ljcnt] = make_pair(x, y);
        for (int i = 0; i < len; i++) {
            switch (s[i]) {
                case 'U': {
                    x--;
                    break;
                }
                case 'D': {
                    x++;
                    break;
                }
                case 'L': {
                    y--;
                    break;
                }
                case 'R': {
                    y++;
                    break;
                }
                default:
                    break;
            }
            if (!vis[x][y]) {
                vis[x][y] = true;
                lujing[++ljcnt] = make_pair(x, y);
            }
        }
        for (int i = 1; i <= ljcnt; i++) {
            x = lujing[i].first;
            y = lujing[i].second;
            int ex = x + d - u;
            int ey = y + r - l;
            chafen[x][y]++;
            chafen[ex + 1][y]--;
            chafen[x][ey + 1]--;
            chafen[ex + 1][ey + 1]++;
        }
        int cnt = 0;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++) {
                cfqzh[i][j] = cfqzh[i - 1][j] + cfqzh[i][j - 1] - cfqzh[i - 1][j - 1] + chafen[i][j];
                if ((r - l + 1) * (d - u + 1) - cfqzh[i][j] == k)
                    cnt++;
            }
        cout << cnt << "\n";
    }
    return 0;
}