2022icpc 南京站 Stop, Yesterday Please No More

2022icpc 南京站 Stop, Yesterday Please No More - 二维差分

本文主要是介绍2022icpc 南京站 Stop, Yesterday Please No More - 二维差分，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题面

分析

题面很长，发现都是一些废话，最初不难想到可以先不看那个洞在哪，先进行处理，找出最后留下的袋鼠有多少，难点是接下来怎么操作能够来记录洞的移动，可以进行差分记录矩形的左上角位置，保证洞只会移动一次在一个位置，为了防止矩形出界，可以在第一次没有洞处理时，并不是真正模拟，只不过是消去相对的袋鼠，假如向上移动，那么第一行就会出界，所以相应操作就是删去第一行，类似这样，最后得到最终矩形，第二次就可以正常模拟，因为第一次模拟已经保证了不会出界，记录左上角的下标，最后通过对差分的统计，计算有多少个位置可以满足题意。

代码

#include <bits/stdc++.h>using namespace std;
using ll = long long;const int N = 1010;int b[N][N];
int vis[N][N];void insert(int x1, int y1, int x2, int y2) {b[x1][y1] ++;b[x2 + 1][y1] --;b[x1][y2 + 1] --;b[x2 + 1][y2 + 1] ++;
}void solve() {int n, m, k;cin >> n >> m >> k;memset(b, 0, sizeof b);memset(vis, 0, sizeof vis);string s;cin >> s;int u = 1;int l = 1;int r = m;int d = n;int U = u;int D = d;int R = r;int L = l;for(int i = 0; i < s.size(); i ++) {if(s[i] == 'U') U ++, D ++;else if(s[i] == 'D') D --, U --;else if(s[i] == 'L') L ++, R ++;else L --, R --;u = max(U, u);d = min(d, D);l = max(L, l);r = min(r, R);}int last = (d - u + 1) * (r - l + 1) - k;if(l > r || u > d) {if(k) cout << 0 << "\n";else cout << n * m << "\n";return ;}if(last < 0) {cout << 0 << "\n";return ;}insert(u, l, d, r);vis[u][l] = 1;for(int i = 0; i < s.size(); i ++) {if(s[i] == 'U') u --, d --;else if(s[i] == 'D') u ++, d ++;else if(s[i] == 'L') l --, r --;else l ++, r ++;//cout << u << ' ' << l << ' ' << d << ' ' << r << endl;if(vis[u][l]) continue;vis[u][l] = 1;insert(u, l, d, r);}for(int i = 1; i <= n; i ++) {for(int j = 1; j <= m; j ++) b[i][j] = b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1] + b[i][j];}int ans = 0;for(int i = 1; i <= n; i ++) {for(int j = 1; j <= m; j ++) {if(b[i][j] == last) ans ++;}}cout << ans << "\n";
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int T;cin >> T;while(T --) {solve();}
}