学校网站建设方案及报价,猎头公司前十名有哪些,asp.net 网站写好后如何运行,无锡门户网站制作服务https://codeforces.com/gym/104128/problem/A
题意 思路
二维差分经典模型
考虑如果没有洞那么经历操作之后会剩下什么样子的袋鼠。发现上下左右移动可以看成是边界在移动#xff0c;边界一直保持一个原初的矩形形状#xff0c;而且上下移动和左右移动没有任何关系。一旦…https://codeforces.com/gym/104128/problem/A
题意 思路
二维差分经典模型
考虑如果没有洞那么经历操作之后会剩下什么样子的袋鼠。发现上下左右移动可以看成是边界在移动边界一直保持一个原初的矩形形状而且上下移动和左右移动没有任何关系。一旦边界移动到了一个位置这个位置前面的袋鼠都会消失。
所以记录u,d,l,r,表示在移动时所产生的最小矩阵的上下左右边界这样剩下的袋鼠数量就是有(d-u1)*(r-l1)个。
加入有洞的情况发现洞产生的路径都可以通过平移获得那么就只维护一条路径就是从(0,0)点开始的路径那么所有的点ij的路径就是00点开始的路径上的点加ij。 那么我们要维护有洞会让袋鼠消失多少只有在uxd,lyr的才是有效被消失的袋鼠那么就维护mp[i][j]表示从ij)点开始会让多少只袋鼠消失发现对于点(x,y),只会对一个矩形内的数加1左上角为(u-x,l-y),右下角为d-x,r-y)的矩形变成二维差分维护那么在二维差分中给一个点加1等于给它往右往下的全部点加1.
注意要去除经过的重复的点重复点不能重复计算答案因为他们去除的是同一片袋鼠。 Code
#include bits/stdc.hconstexpr 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;
}
