Vijos1944 AHOI2015 琵琶湖 【并查集】
描述
滋贺县的琵琶湖享有盛名，尤其是湖中央的琵琶岛。
琵琶岛不仅外观上是矩形的，而且还被分割为了 n x m 的格子图。每一块格子区域都有着确定的高度。不幸的是，琵琶湖的水位最近开始上涨了，第 i 年湖面的高度将上涨至 i 米。另外一方面，琵琶岛是由松软的土质形成的，且琵琶湖的湖水可以自由渗入到其中。也就是说，如果有一块格子区域的高度不超过当前的水位，则将被淹没。相连的未被淹没的格子（有着公共边的格子区域）将组成一块未被淹没的区域。
现在，小可可希望知道对于指定的某一年来说，琵琶岛被分割为了多少块未被淹没的区域。
格式
输入格式
输入的第一行有两个整数 n 和 m，由一个空格隔开，表示琵琶岛的大小。
之后 n 行，每行有 m 个正整数，在 [1,10^9] 范围内,表示了对应格子区域的高度。
之后一行有一个整数 T。再之后的一行，有 T 个整数 tj，满足 0<=t_1<=t_2<=...<=t{T-1}<=t_T<=10^9。
输出格式
在输出中，你的程序应该输出单独一行，包含 T 个整数 r_j 以空格隔开。其中 r_j 表示了在第 t_j 年，未被淹没的区域的个数。
限制
对于20%的数据，1<=n<=100, 1<=m<=100, 1<=T<=2000。
有20%的数据，n = 1, 1<=m<=1000, 1<=T<=10^5。
还有20%的数据，n = 2, 1<=m<=1000, 1<=T<=10^5。
对于100%的数据，1<=n<=1000, 1<=m<=1000, 1<=T<=10^5。
来源
AHOI 2015
【题解】
二维转一维后并查集维护即可，对询问逆序处理，然后就是普通的并查集维护啦。
# include <stdio.h>
# include <algorithm>
using namespace std;
const int dx[]={1,-1,0,0},dy[]={0,0,-1,1};
struct block {
int x,y,h;
}c[1000100];
int k,q[100100];
int n,m,fa[1000100],b[100100];
bool up[1010][1010];
inline int getf(int x) {
int r=x;
while(fa[r]!=r) r=fa[r];
int i=x,j;
while(i!=r) {
j=fa[i];
fa[i]=r;
i=j;
}
return r;
}
inline int cmp_block(block _x,block _y) {return _x.h>_y.h;}
int main() {
scanf("%d%d",&n,&m);
for (int i=1;i<=n;++i)
for (int j=1;j<=m;++j) {
int id=(i-1)*m+j;
c[id].x=i,c[id].y=j;
fa[id]=id;
scanf("%d",&c[id].h);
}
sort(c+1,c+n*m+1,cmp_block);
scanf("%d",&k);
for (int i=1;i<=k;++i)
scanf("%d",&q[i]);
int now=1,ans=0;
for (int i=k;i>=1;--i) {
while(now<=n*m && c[now].h>q[i]) {
ans++; int nowx=c[now].x,nowy=c[now].y;
up[nowx][nowy]=1;
for (int j=0;j<4;++j) {
int xx=nowx+dx[j],yy=nowy+dy[j];
if(xx<1||xx>n||yy<1||yy>m|| !up[xx][yy]) continue;
int id1=(xx-1)*m+yy,id2=(nowx-1)*m+nowy,fid1=getf(id1),fid2=getf(id2);
if(fid1!=fid2) {
fa[fid1]=fid2;
ans--;
}
}
now ++;
}
b[i]=ans;
}
for(int i=1;i<k;++i) printf("%d ",b[i]);
printf("%d\n",b[k]);
return 0;
}
2024年1月09日 14:36
The Board model paper" typically refers to a sample or model question paper that is designed by educational boards or institutions for various exams. These papers serve as practice material for students preparing for exams, providing them with an idea of the question format, difficulty level, and the type of content that may be covered in the actual examination. boardmodelpaper.com Model papers are usually created for specific subjects or courses. They cover a range of topics and chapters that students are expected to have studied during the academic term. Students often use these educational board model papers as an integral part of their exam preparation strategy, helping them familiarize themselves with the exam pattern and refine their understanding of the subject matter.