AGC015 C Nuske vs Phantom Thnook(前缀和)
2018-09-19 02:44:14来源:博客园 阅读 ()
题意
题目链接
给出一张$n \times m$的网格,其中$1$为蓝点,$2$为白点。
$Q$次询问,每次询问一个子矩阵内蓝点形成的联通块的数量
保证任意联通块内的任意蓝点之间均只有一条路径可达
Sol
mdzz不好好读题目还想做题,。。
题目中说“联通块内的任意点都只有一条路径可达”,不难推断出这是一棵树
因此 联通块个数 = 蓝点的数量 - 蓝点间边的数量
考虑用前缀和维护,点的数量好处理,但是这个边的数量有点麻烦
反正我用一个数组是搞不出来,因为无法判断左右的方向。。
那就行列分别记录一下就可以了。
#include<cstdio> #include<iostream> #include<cstring> #define LL long long using namespace std; const int MAXN = 2001; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int N, M, Q; char s[MAXN][MAXN]; int P[MAXN][MAXN], R[MAXN][MAXN], L[MAXN][MAXN]; int GetP(int x, int y) { if(x == 0 || y == 0) return 0; return P[x - 1][y] + P[x][y - 1] - P[x - 1][y - 1]; } int GetR(int x, int y) { if(x == 0 || y == 0) return 0; return R[x - 1][y] + R[x][y - 1] - R[x - 1][y - 1]; } int GetL(int x, int y) { if(x == 0 || y == 0) return 0; return L[x - 1][y] + L[x][y - 1] - L[x - 1][y - 1]; } main() { N = read(); M = read(); Q = read(); for(int i = 1; i <= N; i++) { scanf("%s", s[i] + 1); for(int j = 1; j <= M; j++) { P[i][j] = GetP(i, j); R[i][j] = GetR(i, j); L[i][j] = GetL(i, j); if(s[i][j] == '1') L[i][j] += (s[i - 1][j] == '1'), R[i][j] += (s[i][j - 1] == '1'), P[i][j]++; } } /*for(int i = 1; i <= N; i++, puts("")) for(int j = 1; j <= M; j++) printf("%d ", L[i][j]);*/ while(Q--) { int x1 = read(), y1 = read(), x2 = read(), y2 = read(); // printf("%d %d %d %d\n", GetP(x2, y2), GetP(x1 - 1, y2), GetP(x2, y1 - 1), GetP(x1 - 1, y1 - 1)); int ans1 = P[x2][y2] - P[x1 - 1][y2] - P[x2][y1 - 1] + P[x1 - 1][y1 - 1]; int ans2 = R[x2][y2] - R[x1 - 1][y2] - R[x2][y1] + R[x1 - 1][y1]; int ans3 = L[x2][y2] - L[x2][y1 - 1] - L[x1][y2] + L[x1][y1 - 1]; cout << ans1 - ans2 - ans3 << endl; } return 0; } /* */
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- agc015E - Mr.Aoki Incubator(dp) 2018-09-29
- AGC015 D A or...or B Problem(智商题) 2018-09-19
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash