首页 > 代码库 > [ An Ac a Day ^_^ ] hdu 5925 Coconuts 离散化+BFS求连通块
[ An Ac a Day ^_^ ] hdu 5925 Coconuts 离散化+BFS求连通块
东北赛根本就没看懂的的题目……
也用到了离散化
1e9的x y范围 200个坏点 很典型的离散化数据范围
还是不太为什么离散化的遍历下标都要从1开始……
所以说只做这道题对离散化的理解还不是很深刻……
因为可能换一道题又不会了
还是要多做啊
1 #include<bits/stdc++.h> 2 #define cl(a,b) memset(a,b,sizeof(a)) 3 #define debug(x) cerr<<#x<<"=="<<(x)<<endl 4 using namespace std; 5 typedef long long ll; 6 7 const int maxn=2e2+10; 8 9 int dx[4]= {0,0,1,-1}; 10 int dy[4]= {1,-1,0,0}; 11 12 ll ans[maxn*maxn],sum; 13 int n,m,k,cntx,cnty; 14 int x[maxn],y[maxn]; 15 int xx[maxn],yy[maxn]; 16 int linex[maxn],liney[maxn]; 17 bool vis[maxn][maxn]; 18 map<int,int>ux,uy;//如果用数组的话会因为x y太大越界 所以这里用map映射 19 20 void init() 21 { 22 cntx=0,cnty=0; 23 cl(ans,0),cl(vis,0); 24 ux.clear(),uy.clear(); 25 } 26 27 bool judge(int x,int y) 28 { 29 if(x<1||x>cntx||y<1||y>cnty||vis[x][y]) return false; 30 return true; 31 } 32 33 void dfs(int x,int y) 34 { 35 if(!judge(x,y)) return ; 36 vis[x][y]=true; 37 sum+=1ll*linex[x]*liney[y]; 38 for(int i=0;i<4;i++) 39 dfs(x+dx[i],y+dy[i]); 40 } 41 42 int main() 43 { 44 int cas=1,T; 45 scanf("%d",&T); 46 while(T--) 47 { 48 init(); 49 scanf("%d%d%d",&n,&m,&k); 50 int nx=0,ny=0; 51 xx[++nx]=1,xx[++nx]=n; 52 yy[++ny]=1,yy[++ny]=m; 53 for(int i=1;i<=k;i++) 54 { 55 scanf("%d%d",&x[i],&y[i]); 56 xx[++nx]=x[i],yy[++ny]=y[i]; 57 } 58 //离散化x轴 59 sort(xx+1,xx+nx+1); 60 nx=unique(xx+1,xx+nx+1)-(xx+1); 61 for(int i=1;i<=nx;i++) 62 { 63 if(xx[i]!=xx[i-1]+1) 64 { 65 linex[++cntx]=xx[i]-(xx[i-1]+1); 66 } 67 linex[++cntx]=1; 68 ux[xx[i]]=cntx; 69 } 70 //离散化y轴 71 sort(yy+1,yy+ny+1); 72 ny=unique(yy+1,yy+ny+1)-(yy+1); 73 for(int i=1;i<=ny;i++) 74 { 75 if(yy[i]!=yy[i-1]+1) 76 { 77 liney[++cnty]=yy[i]-(yy[i-1]+1); 78 } 79 liney[++cnty]=1; 80 uy[yy[i]]=cnty; 81 } 82 //标记bad coconut 83 for(int i=1;i<=k;i++) 84 { 85 vis[ux[x[i]]][uy[y[i]]]=true; 86 } 87 //搜索联通块并记录ans 88 int cnt=0; 89 for(int i=1;i<=cntx;i++) 90 { 91 for(int j=1;j<=cnty;j++) 92 { 93 if(!vis[i][j]) 94 { 95 sum=0; 96 dfs(i,j); 97 ans[cnt++]=sum; 98 } 99 }100 }101 sort(ans,ans+cnt);102 printf("Case #%d:\n",cas++);103 printf("%d\n",cnt);104 for(int i=0;i<cnt;i++)105 printf("%lld%c",ans[i],i==cnt-1?‘\n‘:‘ ‘);106 }107 return 0;108 }109 /*110 111 2112 113 3 3114 2115 1 2116 2 1117 118 3 3119 1120 2 2121 122 */
[ An Ac a Day ^_^ ] hdu 5925 Coconuts 离散化+BFS求连通块
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。