首页 > 代码库 > HDU 4941 Magical Forest 【离散化】【map】
HDU 4941 Magical Forest 【离散化】【map】
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4941
题目大意:给你10^5个点,每个点有一个数值,点的xy坐标是0~10^9,点存在于矩阵中。然后给出10^5个操作,1代表交换行,2代表交换列,3代表查询坐标为xy点的数值。
数据量很大........ 所以一直没有思路
后来赛后看了题解是先用离散化然后存在线性map里面。
#include <iostream> #include <cstdio> #include <map> #include <algorithm> using namespace std; struct Node { int x; int y; int c; }l[100000]; map <int, int> fmap[100010]; map <int ,int>hashx,hashy; int T,n,m,k,mapx,mapy,t,cas,lianx[100010],liany[100010],Q,A,B,X,Y; bool cmpx(Node a,Node b) { return a.x<b.x; } bool cmpy(Node a,Node b) { return a.y<b.y; } int main() { int CAS; scanf("%d", &CAS); for(int cas=1;cas<=CAS;cas++) { scanf("%d%d%d",&n,&m,&k); printf("Case #%d:\n",cas); for(int i=0;i<k;i++) scanf("%d%d%d",&l[i].x,&l[i].y,&l[i].c); for(int i=0;i<100010;i++) fmap[i].clear(); hashx.clear(); hashy.clear(); mapx=mapy=0; sort(l,l+k,cmpx); for(int i=0;i<k;i++) if(!hashx[l[i].x]) hashx[l[i].x]=++mapx; sort(l,l+k,cmpy); for(int i=0;i<k;i++) { if(!hashy[l[i].y]) hashy[l[i].y]=++mapy; fmap[hashx[l[i].x]][hashy[l[i].y]]=l[i].c; } for(int i=1;i<=mapx;i++)lianx[i]=i; for(int i=1;i<=mapy;i++)liany[i]=i; scanf("%d",&t); for(int i=0;i<t;i++) { scanf("%d%d%d",&Q,&A,&B); if(Q==1) { X=hashx[A];Y=hashx[B]; if(X && Y) swap(lianx[X],lianx[Y]); } else if(Q==2) { X=hashy[A];Y=hashy[B]; if(X && Y) swap(liany[X],liany[Y]); } else if(Q==3) { X=hashx[A];Y=hashy[B]; if(X && Y)printf("%d\n",fmap[lianx[X]][liany[Y]]); else printf("0\n"); } } } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。