做数学题好的网站,建设网站需要做的工作内容,抖音代运营合同模板免费下载,免费版多用户商城源码Time Limit: 10 Sec Memory Limit: 64 MB Submit: 784 Solved: 422 [Submit][Status][Discuss] Description 佳佳有一个 nnn 行 nnn 列的黑白棋盘#xff0c;每个格子都有两面#xff0c;一面白色#xff0c;一面黑色。佳佳把棋盘平放在桌子上#xff0c;因此每个格子恰好一… Time Limit: 10 Sec Memory Limit: 64 MB Submit: 784 Solved: 422 [Submit][Status][Discuss] Description 佳佳有一个 nnn 行 nnn 列的黑白棋盘每个格子都有两面一面白色一面黑色。佳佳把棋盘平放在桌子上因此每个格子恰好一面朝上如下图所示 QQ20180116200234.png 我们把每行从上到下编号为 111 222 333 ……nnn 各列从左到右编号为 111 222 333 ……nnn 则每个格子可以用棋盘坐标(x,y)(x, y)(x,y) 表示。在上图中有 888 个格子黑色朝上另外 171717 个格子白色朝上。 如果两个同色格子有一条公共边我们称这两个同色格子属于同一个连通块。上图共有 555 个黑色连通块和 333 个白色连通块。 佳佳可以每分钟将一个格子翻转即白色变成黑色黑色变成白色然后计算当前有多少个黑色连通块和白色连通块你能算得更快吗 Input 输入文件的第一行包含一个正整数 nnn 为格子的边长。以下 nnn 行每行 nnn 个整数非 000 即 111 表示初始状态。000 表示白色111 表示黑色。下一行包含一个整数 mmm 表示操作的数目。以下 mmm 行每行两个整数 xxx , yyy (111 ≤ xxx , yyy ≤ nnn )表示把坐标为(x,y)(x, y)(x,y) 的格子翻转。 Output 输出文件包含 mmm 行每行对应一个操作。该行包括两个整数 bbb , www 表示黑色区域和白色区域数目。 【约定】 ○1 ≤ n ≤ 200 ○1 ≤ m ≤ 10,000 Sample Input 5 0 1 0 0 0 0 1 1 1 0 1 0 0 0 1 0 0 1 0 0 1 0 0 0 0 2 3 2 2 3 Sample Output 4 3 5 2 HINT 翻转(3,2)(3, 2)(3,2) 之后棋盘变为 QQ20180116200629.png 有 444 个黑色区域和 333 个白色区域 翻转(2,3)(2, 3)(2,3) 之后棋盘变为 QQ20180116200639.png 有 555 个黑色区域和 222 个白色区域 Source 鸣谢刘汝佳先生授权使用 题解 用线段树维护行并查集合并 线段树每个节点维护区间[l,r]中行l的并查集行r的并查集用于查询l与r的联通情况维护[l,r]行的白色连通块数和黑色连通块数。维护并查集父节点个数。 合并即可。 注意并查集维护的时候其所指的父亲不是这些格子自身而是虚出来的节点。在两个区间合并的时候处理虚的节点的连通性右区间虚节点编号要加上左区间虚的节点的个数合并后的虚节点继承回区间的左右并查集即可。离散化一下不然可能会很大。。 推荐题解 #include iostream
#include cstdio
#include cstdlib
#include cstring
#include algorithm
#include map
#include cmath
inline int max(int a, int b){return a b ? a : b;}
inline double max(double a, double b){return a - b 0 ? a : b;}
inline int min(int a, int b){return a b ? a : b;}
inline void swap(int x, int y){int tmp x;x y;y tmp;}
inline void read(int x)
{x 0;char ch getchar(), c ch;while(ch 0 || ch 9) c ch, ch getchar();while(ch 9 ch 0) x x * 10 ch - 0, ch getchar();if(c -) x -x;
}
const int INF 0x3f3f3f3f;
const int MAXN 200 10;
int n, q, fa[MAXN 2], g[MAXN][MAXN], vis[MAXN 2];
int find(int x)
{return x fa[x] ? x : fa[x] find(fa[x]);
}
struct Node
{int cnt, fal[MAXN 1], far[MAXN 1], wsize, bsize, l, r;Node(){cnt wsize bsize l r 0, memset(fa, 0, sizeof(fa)), memset(far, 0, sizeof(far));}
}node[MAXN 2];void pushup(int o)
{int l o 1, r o 1 | 1;if(node[l].cnt 0){node[o] node[r];return;}if(node[r].cnt 0){node[o] node[l];return;}for(int i node[l].cnt node[r].cnt;i;-- i) fa[i] i, vis[i] 0;node[o].wsize node[l].wsize node[r].wsize;node[o].bsize node[l].bsize node[r].bsize;for(int i 1;i n; i)if(g[node[l].r][i] g[node[r].l][i]){int f1 find(node[l].far[i]), f2 find(node[r].fal[i] node[l].cnt);if(f1 ! f2){fa[f1] f2;if(g[node[l].r][i]) -- node[o].bsize;else -- node[o].wsize;}}node[o].cnt 0;for(int i 1;i n; i){int f1 find(node[l].fal[i]), f2 find(node[r].far[i] node[l].cnt);if(!vis[f1]) vis[f1] node[o].cnt;if(!vis[f2]) vis[f2] node[o].cnt;node[o].fal[i] vis[f1], node[o].far[i] vis[f2];}
}
void calc(int o)
{int wsize 0, bsize 0, pos node[o].l, *fal node[o].fal, *far node[o].far;if(g[pos][1]) bsize; else wsize;fal[1] far[1] 1;for(int i 2;i n; i){if(g[pos][i] ! g[pos][i - 1])if(g[pos][i]) bsize;else wsize;fal[i] far[i] wsize bsize;}node[o].cnt wsize bsize, node[o].wsize wsize, node[o].bsize bsize;
}
void build(int o 1, int l 1, int r n)
{node[o].l l, node[o].r r;if(l r){calc(o);return;}int mid (l r) 1;build(o 1, l, mid);build(o 1 | 1, mid 1, r);pushup(o);
}
void modify(int p, int o 1, int l 1, int r n)
{if(l r){calc(o);return;}int mid (l r) 1;if(p mid) modify(p, o 1, l, mid);else modify(p, o 1 | 1, mid 1, r);pushup(o);
}int main()
{read(n);for(register int i 1;i n; i)for(register int j 1;j n; j)read(g[i][j]);build();read(q);for(register int i 1;i q; i){int tmp1, tmp2;read(tmp1), read(tmp2);g[tmp1][tmp2] ^ 1;modify(tmp1);printf(%d %d\n, node[1].bsize, node[1].wsize);}return 0;
} 转载于:https://www.cnblogs.com/huibixiaoxing/p/8599072.html
