膜拜神犇

#include<iostream>
#include<stdio.h>
using namespace std;

int dir[2][5]={{1,-1,0,0},{0,0,1,-1}};

int n,m;
int h[1005][1005];
int father[1000005];
typedef pair<int,int> nodexy;
inline nodexy getxy(int t){
return make_pair((t-1)/m+1,(t-1)%m+1);
}
inline int getrl(int x,int y){
return (x-1)*m+y;
}
int T,t[100005];
int ans[100005];
int head[100005];
int NEXT[1000005];

int find(int x){
if(father[x]==x) return x;
father[x]=find(father[x]);
return father[x];
}

int main(){
cin>>n>>m;
int i,j;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{ scanf("%d",&h[i][j]);}
cin>>T;
for(i=1;i<=T;i++)
{ scanf("%d",&t[i]);}
int x,y,k;
nodexy xy;
for(i=1;i<=n*m;i++)
{ x=(i-1)/m+1; y=(i-1)%m+1;
int bot=0,top=T,mid=T/2;
while(bot<top)
{ if(t[mid]<h[x][y])
{ bot=mid;}
else
{ top=mid-1;}
mid=(bot+top+1)/2;
}
h[x][y]=mid;
NEXT[i]=head[mid];
head[mid]=i;
}
for(i=T;i>=1;i--)
{ k=head[i];
ans[i]=ans[i+1];
while(k)
{ ans[i]++;
father[k]=k;
k=NEXT[k];}
k=head[i];
int x1,y1,f0,f1;
while(k)
{ xy=getxy(k);
x=xy.first;
y=xy.second;
for(j=0;j<4;j++)
{ x1=x+dir[0][j];
y1=y+dir[1][j];
if(x1>=1&&x1<=n&&y1>=1&&y1<=m){
f0=find(getrl(x,y));
f1=find(getrl(x1,y1));
if(f0!=f1&&f0&&f1){
ans[i]--;
father[f0]=f1;
}}
}
k=NEXT[k];
}
}
for(i=1;i<=T;i++)
printf("%d ",ans[i]);
return 0;
}

这是最后一遍的程序，注意判断，仔细一点做，这题还是不难的

#include<algorithm>

#include<deque>

#include<functional>

#include<iterator>

#include<list>

#include<map>

#include<memory>

#include<memory.h>

#include<numeric>

#include<queue>

#include<set>

#include<stack>

#include<utility>

#include<vector>

#include<iostream>

#include<stdlib.h>

#include<string.h>

#include<math.h>

#include<stdio.h>

#include<time.h>

#include<conio.h>

using namespace std;

#ifdef WIN32
typedef __int64 ll;
#else
typedef long long ll;
#endif

int acmp(const void *p,const void *q){
return *(int )p-(int *)q;
}

int bcmp(const void *p,const void *q){
return acmp(q,p);
}

inline int mx(int a,int b){return a>b?a:b;}

inline int mn(int a,int b){return a<b?a:b;}

inline int ab(int x){return x>0?x:-x;}

const int SIZE=1005,SIZET=100005,dSIZE=1000005;

int ye[SIZET];
int h[SIZE][SIZE];
int t,n,m;
int ans[SIZET];
int head[SIZET];
int next[dSIZE];
int run[2][5]={{1,0,-1,0},
{0,1,0,-1}};
int father[dSIZE];
int l;
//i j的编号s为(i-1)*m+j
//i=(s-1)/m+1
//j=(s-1)%m+1

int find(int x){//路径压缩
if(father[x]==x) return x;
father[x]=find(father[x]);
return father[x];
}

void init(){//读入数据
scanf("%d%d",&n,&m);
int i,j;l=n*m;
for(i=1;i<=n;i++)
{ for(j=1;j<=m;j++)
{ scanf("%d",&h[i][j]);}
}
scanf("%d",&t);
for(i=1;i<=t;i++)
{ scanf("%d",ye+i);}
}

void discretization(){//进行离散化
int i,x,y;l=n*m;
for(i=1;i<=l;i++)
{ x=(i-1)/m+1; y=(i-1)%m+1;
int bot=0,top=t,mid=t/2;
while(bot<top)
{ if(ye[mid]<h[x][y])
{ bot=mid;}
else
{ top=mid-1;}
mid=(bot+top+1)/2;
}
h[x][y]=mid;
next[i]=head[mid];
head[mid]=i;//构造邻接表
father[i]=i;
}
//离散化检验
/*
for(i=1;i<=l;i++)
{ x=(i-1)/m+1; y=(i-1)%m+1;
printf("%d ",h[x][y]);
if(i%m==0)puts("");
}
putchar('\n');
/
//高度模板检验
/
for(i=0;i<=t;i++)
{ int k=head[i],l=0;
while(k){printf("%d,%d ",(k-1)/m+1,(k-1)%m+1);
k=next[k];l++;}
if(l) putchar('\n');
}
putchar('\n');
*/
}

void add(int k,int f){//增加k位置,即将k四周的一圈连接起来
int x=(k-1)/m+1, y=(k-1)%m+1 ,i ,xg ,yg ,fa ,fk;
ans[f]++;
for(i=0;i<4;i++)
if(h[x+run[0][i]][y+run[1][i]]>f)//该位置有岛
{ xg=x+run[0][i];
yg=y+run[1][i];
fa=find((xg-1)*m+yg);
fk=find(k);
if(fa!=fk)//不在同一个子集中
{ father[fk]=fa; ans[f]--;}//合并为同一子集
}
}

void cube_father(int P){
printf("\n\n%d:\n",P);int x,y,i;
for(i=1;i<=l;i++)
{ printf("%4d",find(father[i]));
if(i%m==0)puts("");}
puts("");
}

void basic_build(){//构造ans[t]和初始father
int k=head[t];//浮于水上的第一个结点
while(k)
{ add(k,t);
k=next[k];}
//father检验
//cube_father(t);
}

void ans_build(){
int i,k;
for(i=t-1;i>=1;i--){
k=head[i];
ans[i]=ans[i+1];
while(k)
{ add(k,i);
k=next[k];
//cube_father(i);
//cout<<ans[i]<<endl;
}
//cube_father(i);
}
}

void op(){
int i;
for(i=1;i<=t;i++)
{ printf("%d ",ans[i]);}
}

int main(){
freopen("lakepiwa.in","r",stdin);
freopen("lakepiwa.out","w",stdout);
init();
discretization();
basic_build();
ans_build();
op();
return 0;
}

这是第二次写的程序，相比之下肯定考虑的要成熟的多，也有了基本的结构模型，很遗憾还是错了，但是这其中的一些关于离散化的代码什么的，都检验无误，也给第三次的程序创造了条件。当然，写程序还是要多调试啊。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<queue>
#include<stack>
using namespace std;

int father[1000010];//f[i*n+j]表示第ij水位的父岛屿
int f[1010][1010];//表示第ij的高度
int L[100010];//表示年份
int ans[100010];//表示第L[i]年的岛屿情况
int n,m,l,now;
int Lfirst[100010];//表示第L[i]水位以上的位置

struct Edge{
int p;//表示坐标
int next;
}edge[1000010];//表示高于L[i]水位的情况

int find(int x){//路径压缩
if(father[x]==x) return x;
father[x]=find(father[x]);
return father[x];
}

int match(int i){//将i位置的格子连接起来,返回区域数
int x=i/m+1,y=i%m,s=1,j;//(i*m-m+j)+m
if(y==0){y=m;x--;}
int p[10]={find(i)},sa[10]={0};
if(x+1<=n&&f[x+1][y]>L[now]){p[1]=find(x*m+y);}else{p[1]=p[0];}
if(y+1<=m&&f[x][y+1]>L[now]){p[2]=find(x*m-m+y+1);}else{p[2]=p[0];}
if(y-1&&f[x][y-1]>L[now+1]){p[3]=find(x*m+y-1-m);}else{p[3]=p[0];}
if(x-1<=m&&f[x-1][y]>L[now+1]){p[4]=find(x*m-m*2+y);}else{p[4]=p[0];}
for(j=1;j<=4;j++)
if(find(p[j])!=p[0]){
father[p[j]]=p[0];
s--;
}
return s;
}

void init(){
scanf("%d%d",&n,&m);
int i,j,Fir,End,Now;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
scanf("%d",&f[i][j]);
scanf("%d",&l);
for(i=1;i<=l;i++)
scanf("%d",&L[i]);
for(i=1;i<=n;i++)
for(j=1;j<=m;j++){
Fir=0;End=l;
Now=(Fir+End)/2;
while(Fir<End){
if(L[Now]<f[i][j]) Fir=Now+1;
else End=Now;
Now=(Fir+End)/2;
}
edge[i*m-m+j].next=Lfirst[Fir-1];
edge[i*m-m+j].p=i*m-m+j;
Lfirst[Fir-1]=i*m-m+j;
father[i*m-m+j]=i*m-m+j;
}
}

void work(int k){
ans[now]=ans[now+1];
if(Lfirst[k]==0){return;}
k=Lfirst[k];
while(k){
ans[now]+=match(edge[k].p);
k=edge[k].next;
}
}

void workall(){
for(now=l;now>0;now--)
work(now);
for(now=1;now<=l;now++)
printf("%d ",ans[now]);
}

int main(){
freopen("lilypond.in","r",stdin);
freopen("lilypond.out","w",stdout);
init();
workall();
return 0;
}

不知道这个格式是怎么回事，可能可读性比较差，先就暂时这样吧。这是我第一次写的程序，当时考虑的是自下往上，从右往左的顺序添加结点，只考虑和右边、下边的等高结点和所有的比自身高的结点来合并。虽然到现在还不清楚到底为什么错了，但是程序可以说可读性很差，也很乱，很容易干扰思想，最后这种算法以失败告终