【二维差分】ICPC南京 A

电玩女神 2024-02-21 10:29 67阅读 0赞

[https://codeforces.com/gym/104128/problem/A][https_codeforces.com_gym_104128_problem_A]

题意

![f9adf5396a2c4bda935608c22181897f.png][]

![3f83b3412a1c4d9c9d7fce29fb567c3c.png][]

思路

二维差分+经典模型

考虑如果没有洞那么经历操作之后会剩下什么样子的袋鼠。发现上下左右移动可以看成是边界在移动，边界一直保持一个原初的矩形形状，而且上下移动和左右移动没有任何关系。一旦边界移动到了一个位置，这个位置前面的袋鼠都会消失。

所以记录u,d,l,r,表示在移动时所产生的最小矩阵的上下左右边界，这样剩下的袋鼠数量就是有(d-u+1)\*(r-l+1)个。

加入有洞的情况，发现洞产生的路径都可以通过平移获得，那么就只维护一条路径，就是从(0,0)点开始的路径，那么所有的点（i，j）的路径就是（0，0）点开始的路径上的点加（i，j）。 那么我们要维护有洞会让袋鼠消失多少，只有在u<=x<=d,l<=y<=r的才是有效被消失的袋鼠，那么就维护mp\[i\]\[j\]表示从（i，j)点开始会让多少只袋鼠消失，发现对于点(x,y),只会对一个矩形内的数加1，左上角为(u-x,l-y),右下角为（d-x,r-y)的矩形，变成二维差分维护，那么在二维差分中给一个点加1等于给它往右往下的全部点加1.

注意：要去除经过的重复的点，重复点不能重复计算答案，因为他们去除的是同一片袋鼠。

Code：

#include <bits/stdc++.h>
    
    constexpr int N = 1e3 + 10;
    constexpr int mod = 998244353;
    constexpr int Inf = 0x3f3f3f3f;
    
    std::string s;
    
    int n, m, k;
    int f[N][N];
    int vis[N][N];
    
    void add(int x1, int y1, int x2, int y2) {
    	f[x1][y1] ++;
    	f[x2 + 1][y1] --;
    	f[x1][y2 + 1] --;
    	f[x2 + 1][y2 + 1] ++;
    }
    void solve() {
    	std::cin >> n >> m >> k;
    	for (int i = 0; i <= n + 5; i ++) {
    		for (int j = 0; j <= m + 5; j ++) {
    			vis[i][j] = f[i][j] = 0;
    		}
    	}
    	std::cin >> s;
    	int sz = s.size();
    	s = " " + s;
    	int u = 1, d = n, l = 1, r = m;
    	int U = 1, D = n, L = 1, R = m;
    	for (int i = 1; i <= sz; i ++) {
    		if (s[i] == 'U') {
    			u ++;
    			d ++;
    		}else if (s[i] == 'D') {
    			u --;
    			d --;
    		}else if (s[i] == 'L') {
    			l ++;
    			r ++;
    		}else {
    			l --;
    			r --;
    		}
    		U = std::max(U, u);
    		D = std::min(D, d);
    		L = std::max(L, l);
    		R = std::min(R, r);
    	}
    	if (L > R || U > D) {
    		if (k) {
    			std::cout << 0 << "\n";
    		}else {
    			std::cout << n * m << "\n";
    		}
    		return;
    	}
    	int del = (R - L + 1) * (D - U + 1) - k;
    	if (del < 0) {
    		std::cout << 0 << "\n";
    		return;
    	}
    	add(U, L, D, R);
    	vis[L][U] = 1;
    	for (int i = 1; i <= sz; i ++) {
    		if (s[i] == 'L') {
    			L --;
    			R --;
    		}else if (s[i] == 'R') {
    			L ++;
    			R ++;
    		}else if (s[i] == 'U') {
    			U --;
    			D --;
    		}else {
    			U ++;
    			D ++;
    		}
    		if (vis[L][U]) continue;
    		vis[L][U] = 1;
    		add(U, L, D, R);
    	}
    	for (int i = 1; i <= n; i ++) {
    		for (int j = 1; j <= m; j ++) {
    			f[i][j] += f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1];
    		}
    	}
    	int ans = 0;
    	for (int i = 1; i <= n; i ++) {
    		for (int j = 1; j <= m; j ++) {
    			if (f[i][j] == del) ans ++;
    		}
    	}
    	std::cout << ans << "\n";
    }
    signed main() {
    	std::ios::sync_with_stdio(false);
    	std::cin.tie(nullptr);
    
    	int t = 1;
    	std::cin >> t;
    	while (t--) {
    		solve();
    	}
    	return 0;
    }

[https_codeforces.com_gym_104128_problem_A]: https://codeforces.com/gym/104128/problem/A
[f9adf5396a2c4bda935608c22181897f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/21/e1acc51e220d4ce295afecf5adf06314.png
[3f83b3412a1c4d9c9d7fce29fb567c3c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/21/c501182347e844dcbeb5c3ab87eee304.png