停停，昨日请不要再重现（2022南京区域赛）题解

核心思路

1. 无坑时剩余袋鼠数cnt
   模拟一只袋鼠的移动轨迹，得到最终偏移量(dx, dy)。初始位置(i,j)的袋鼠能存活 ⇔ (i+dx, j+dy)仍在网格内，遍历所有格子统计即可。

2. 计算每个位置被经过的次数cnt1
   用一只袋鼠模拟移动，记录所有经过的相对坐标(去重)

对每个相对坐标(px,py)，所有初始位置(i,j)满足(i+px, j+py)在网格内的都会被经过一次

用二维差分快速标记：给矩形[1-px, n-px] × [1-py, m-py]加1

3. 统计答案
   坑放(i,j)时，掉入袋鼠数为cnt1[i][j]，剩余袋鼠数为cnt - cnt1[i][j]
   满足 cnt - cnt1[i][j] == k 的位置即为答案

复杂度分析：

模拟路径：O(|s|)

路径去重：O(|s| log |s|)

二维差分：O(|path|)，其中 |path| 是路径中不同坐标数，最多 |s|+1

前缀和与统计：O(nm)

总复杂度：O(nm + |s| log |s|)，可以承受。

#include <bits/stdc++.h>
using ll = long long;
using namespace std;
const ll N = 1e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
ll n, idx, m, k;
string s;
void solve() {cin >> n >> m >> k >> s;ll le = 0, ri = 0, down = 0, up = 0, x = 0, y = 0;for (auto i : s) {//找没有出界的那一部分袋鼠 找上下左右最大值if (i == 'U') {x--;} else if (i == 'D') {x++;} else if (i == 'R') {y++;} else if (i == 'L') {y--;}le = max(le, -y);ri = max(ri, y);up = max(up, -x);down = max(down, x);}ll l = le + 1;ll r = m - ri;ll u = up + 1;ll d = n - down;if (l > r || d < u) {//判断是否无解if (k == 0) {cout << n * m << '\n';} else {cout << 0 << '\n';}return;}s = ' ' + s;x = u, y = l;ll lenx = d - u + 1;ll leny = r - l + 1;ll cnt = lenx * leny;map<int, map<int, int>> vis;vector<vector<int>> t(n + 5, vector(m + 5, 0)), dd(n + 5, vector(m + 5, 0));for (auto i : s) {if (i == 'U') {x--;} else if (i == 'D') {x++;} else if (i == 'R') {y++;} else if (i == 'L') {y--;}if (vis[x][y]) continue;//如果标记过就不用再标记了vis[x][y] = 1;dd[x][y]++;//二维差分dd[x][y + leny]--;dd[x + lenx][y]--;dd[x + lenx][y + leny]++;}ll ans = 0;for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {t[i][j] = t[i - 1][j] + t[i][j - 1] - t[i - 1][j - 1] + dd[i][j];//二维前缀和// cout << t[i][j] << ' ';if (t[i][j] == cnt - k) ans++;}// cout << '\n';}cout << ans << '\n';
}
int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int _ = 1;cin >> _;while (_--) {solve();}return 0;
}