首页 > 代码库 > HDU 4941 Magical Forest（map映射+二分查找）杭电多校训练赛第七场1007

HDU 4941 Magical Forest（map映射+二分查找）杭电多校训练赛第七场1007

2024-07-17 08:43:56   221人阅读

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4941

解题报告：给你一个n*m的矩阵，矩阵的一些方格中有水果，每个水果有一个能量值，现在有三种操作，第一种是行交换操作，就是把矩阵的两行进行交换，另一种是列交换操作，注意两种操作都要求行或列至少要有一个水果，第三种操作是查找，询问第A行B列的水果的能量值，如果查询的位置没有水果，则输出0.

因为n和m都很大，达到了2*10^9，但水果最多一共只有10^5个，我的做法是直接用结构体存了之后排序，然后map[i] = j，表示当前的i行相当于原地图中的j行，这样进行行交换操作的时候只要交换一下这个就可以了，原地图上的模样不变，列交换同理。

 1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<iostream> 5 #include<map> 6 using namespace std; 7 #define maxn 100005 8 struct node 9 {10     int x,y,c;11 }mat[maxn];12 map<int,int> hang,lie;13 bool cmp(node a,node b)14 {15     if(a.x == b.x) return a.y < b.y;16     return a.x < b.x;17 }18 int query(int k,int x,int y)19 {20     int l = 1,r = k,d = x,m;21     while(l < r)22     {23         m = (l + r) >> 1;24         if(d <= mat[m].x) r = m;25         else l = m + 1;26     }27     int s1 = l;28     if(mat[s1].x != x) return 0;   //没找到一个符合的x，说明没有这一行 29     l = 1,r = k,d = x + 1;30     while(l < r)31     {32         m = (l + r) >> 1;33         if(d <= mat[m].x) r = m;34         else l = m + 1;35     }36     int s2 = l;37     if(mat[s2].x != x) s2--;38     l = s1,r = s2;39     while(l < r)40     {41         m = (l + r) / 2;42         if(y <= mat[m].y) r = m;43         else l = m + 1;44     }45     if(mat[l].y != y) return 0;   //没找到符合的y，说明这一行的这一列没有 46     return mat[l].c;47 }48 int main()49 {50     int T,n,m,k,q,kase = 1;51     scanf("%d",&T);52     while(T--)53     {54         scanf("%d%d%d",&n,&m,&k);55         hang.clear();56         lie.clear();57         for(int i = 1;i <= k;++i)58         {59             scanf("%d%d%d",&mat[i].x,&mat[i].y,&mat[i].c);60             hang[mat[i].x] = mat[i].x;61             lie[mat[i].y] = mat[i].y;62         }63         sort(mat+1,mat+k+1,cmp);64         printf("Case #%d:\n",kase++);65         scanf("%d",&q);66         int op,a,b;67         while(q--)68         {69             scanf("%d%d%d",&op,&a,&b);70             if(op == 1)71             {72                 swap(hang[a],hang[b]);73             }74             else if(op == 2)75             {76                 swap(lie[a],lie[b]);77             }78             else if(op == 3)79             {80                 a = hang[a];81                 b = lie[b];82                 printf("%d\n",query(k,a,b));83             }84         }85     }86     return 0;87 }        88 /*89 590 4 4 4dlsdfflsfls91 1 1 192 2 4 493 3 2 294 4 4 395 */
View Code

 


联系
我们