【JZOJ3635】【BOI2012】Peaks

    xiaoxiao2021-03-26  7

    ╰( ̄▽ ̄)╭

    有一个居住在多山岛屿的登山家,已经攀上了一座山峰,并且要攀爬另外一座更高的山峰。

    更精确地说,岛上的每一点都有一个大于零的海拔(海面的海拔为零),并且如果登山家位于海拔Ei的山峰上,那么他的目标是到达其他海拔为Ej(Ej>Ei)的山峰。因为登山家在一个山峰上,所以无法马上向上爬——为了到达一个海拔更高的地点,登山家需要先下山才能上山。下山的路不及上山精彩,因此,登山家想将从当前地点到达更高山峰途中最低点的海拔最大化。

    例如,如果岛屿的轮廓如图中所示,并且登山家在海拔为E4的山峰,那么有三个山峰有更高的海拔(E5,E6和E7),但是路途中最低点最高的路径是到达海拔E7的山峰的路径——在路上他不会走到海拔E2以下(在其他路径中他必须经过海拔E1的地点)。如果他从海拔E5的山峰出发,那么对应路径经过的最低海拔为E3(到达E6的路径),但是如果他从E6 出发,那么最低点就是E1。

    岛屿的地图是一个二维的N*M的矩形网格,并且描述了岛屿每一部分的海拔——格子里的数字表示岛屿对应地区的海拔。如果两个各自有公共点,那么他们相邻。因此,每个格子(除了在边界上的)和其他8个格子相邻。一条路径是一系列的格子,序列中连续的两个格子相邻。一个“平区域”是一个相同海拔格子的集合,并且集合中任意两个格子能够用仅经过这个集合内格子的路径连接。任意两个等高的相邻格子属于同一“平区域” 。一座山峰,是一个相邻的格子中没有更高海拔的“平区域”。

    写一个程序,找到所有山峰,并且计算每个山峰到达更高山峰路途中最大的最低海拔。对于岛上最高的山峰(岛上没有更高的山峰),可以确定登山家会离开岛屿寻找更高的山峰,因此,路途中的最低海拔为零(海平面的海拔)。

    1<=N,M<=2000NM<=105,1<=Eij<=106

    (⊙ ▽ ⊙)

    先把网格按高度从大到小排序, 然后依次插入网格。

    每次插入网格 C 后,询问其相邻的网格; 若其相邻的网格存在已被访问过的,那么这个网格所在的“平区域”肯定不是峰; 同时可以更新其相邻的网格所在的峰的答案。

    否则C就是峰。


    细节很多,特判很多,出题人是SB。

    ( ̄~ ̄)

    #include<iostream> #include<stdio.h> #include<algorithm> #include<string.h> #include<math.h> #define ll long long #define pos(x,y) (((x)-1)*m+(y)) using namespace std; const char* fin="peaks.in"; const char* fout="peaks.out"; const int inf=0x7fffffff; const int maxn=100007,maxm=2006; const int f[8][2]={{0,1},{1,1},{1,0},{-1,0},{-1,-1},{0,-1},{1,-1},{-1,1}}; int n,m,i,j,k,tot,xx; int a[maxm][maxm],rf[maxm][maxm],go[maxm*maxm],Rf[maxm*maxm]; bool bz[maxm][maxm]; int dad[maxn]; int ans1; struct node{ int x,y,z,ans; int feng; }b[maxn],ans[maxn]; bool cmp(const node &a,const node &b){ return a.z>b.z || (a.z==b.z && a.x<b.x) || (a.z==b.z && a.x==b.x && a.y<b.y); } bool cmp1(node a,node b){ return a.feng>b.feng || (a.feng==b.feng && a.z>b.z) || (a.feng==b.feng && a.z==b.z && a.ans>b.ans); } bool cmp2(node a,node b){ return a.x>b.x || (a.x==b.x && a.y>b.y); } int getdad(int v){ if (!dad[v]) return v; dad[v]=getdad(dad[v]); return dad[v]; } int getgo(int v){ if (!go[v]) return v; go[v]=getgo(go[v]); return go[v]; } void merge(int v,int u){ int j=getdad(v),k=getdad(u); dad[j]=k; } int main(){ freopen(fin,"r",stdin); freopen(fout,"w",stdout); scanf("%d%d",&n,&m); k=0; for (i=1;i<=n;i++) for (j=1;j<=m;j++){ scanf("%d",&a[i][j]); b[++tot].x=i; b[tot].y=j; b[tot].z=a[i][j]; } sort(b+1,b+tot+1,cmp); for (i=1;i<=tot;i++) rf[b[i].x][b[i].y]=i; for (i=1;i<=tot;i++){ b[i].feng=1; for (j=0;j<8;j++){ int X=b[i].x+f[j][0],Y=b[i].y+f[j][1]; if (X>0 && X<=n && Y>0 && Y<=m){ if (bz[X][Y]){ b[i].feng=0; int tmp=getdad(rf[b[i].x][b[i].y]); int tmd=getdad(rf[X][Y]); if (b[tmp].z>b[tmd].z){ if (tmp!=tmd){ dad[tmd]=tmp; b[tmd].ans=max(b[tmd].ans,b[i].z); } }else{ if (tmp!=tmd){ dad[tmp]=tmd; if (b[tmp].z!=b[tmd].z){ b[tmp].ans=max(b[tmp].ans,b[i].z); }else{ if (b[i].z==b[tmp].z) b[tmp].feng=0; go[pos(b[tmp].x,b[tmp].y)]=pos(b[tmd].x,b[tmd].y); } } } } } } bz[b[i].x][b[i].y]=true; } sort(b+1,b+tot+1,cmp1); for (i=1;i<=tot;i++) Rf[pos(b[i].x,b[i].y)]=i; for (i=1;i<=tot;i++){ if (!b[i].feng) break; if (b[i].z==b[Rf[getgo(pos(b[i].x,b[i].y))]].ans){ continue; } ans1++; ans[ans1].x=b[i].z; ans[ans1].y=b[Rf[getgo(pos(b[i].x,b[i].y))]].ans; } sort(ans+1,ans+ans1+1,cmp2); printf("%d\n",ans1); for (i=1;i<=ans1;i++) printf("%d %d\n",ans[i].x,ans[i].y); return 0; }

    (⊙v⊙)

    关键点: 1.把网格按高度从大到小排序 由于要求最小值的最大值,又可以通过单个网格来更新答案; 所以可以采用排序的方法。

    转载请注明原文地址: https://ju.6miu.com/read-500191.html

    最新回复(0)