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

题目链接：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行，这样进行行交换操作的时候只要交换一下这个就可以了，原地图上的模样不变，列交换同理。

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<iostream>

 #include<map>

 using namespace std;

 #define maxn 100005

 struct node

 {

     int x,y,c;

 }mat[maxn];

 map<int,int> hang,lie;

 bool cmp(node a,node b)

 {

     if(a.x == b.x) return a.y < b.y;

     return a.x < b.x;

 }

 int query(int k,int x,int y)

 {

     int l = ,r = k,d = x,m;

     while(l < r)

     {

         m = (l + r) >> ;

         if(d <= mat[m].x) r = m;

         else l = m + ;

     }

     int s1 = l;

     if(mat[s1].x != x) return ;   //没找到一个符合的x，说明没有这一行

     l = ,r = k,d = x + ;

     while(l < r)

     {

         m = (l + r) >> ;

         if(d <= mat[m].x) r = m;

         else l = m + ;

     }

     int s2 = l;

     if(mat[s2].x != x) s2--;

     l = s1,r = s2;

     while(l < r)

     {

         m = (l + r) / ;

         if(y <= mat[m].y) r = m;

         else l = m + ;

     }

     if(mat[l].y != y) return ;   //没找到符合的y，说明这一行的这一列没有

     return mat[l].c;

 }

 int main()

 {

     int T,n,m,k,q,kase = ;

     scanf("%d",&T);

     while(T--)

     {

         scanf("%d%d%d",&n,&m,&k);

         hang.clear();

         lie.clear();

         for(int i = ;i <= k;++i)

         {

             scanf("%d%d%d",&mat[i].x,&mat[i].y,&mat[i].c);

             hang[mat[i].x] = mat[i].x;

             lie[mat[i].y] = mat[i].y;

         }

         sort(mat+,mat+k+,cmp);

         printf("Case #%d:\n",kase++);

         scanf("%d",&q);

         int op,a,b;

         while(q--)

         {

             scanf("%d%d%d",&op,&a,&b);

             if(op == )

             {

                 swap(hang[a],hang[b]);

             }

             else if(op == )

             {

                 swap(lie[a],lie[b]);

             }

             else if(op == )

             {

                 a = hang[a];

                 b = lie[b];

                 printf("%d\n",query(k,a,b));

             }

         }

     }

     return ;

 }

 /*

 5

 4 4 4dlsdfflsfls

 1 1 1

 2 4 4

 3 2 2

 4 4 3

 */

再附上一种短代码的完全用map实现的，其实关键就是用pair<int,int>作为键。

 #include<cstdio>

 #include<map>

 #include<iostream>

 #include<algorithm>

 using namespace std;

 int T,n,m,k,x,y,c,q,kase;

 map<int,int> hang,lie;

 map<pair<int,int>,int> mp;

 int main()

 {

     scanf("%d",&T);

     kase = ;

     while(T--)

     {

         scanf("%d%d%d",&n,&m,&k);

         hang.clear(),lie.clear(),mp.clear();

         while(k--)

         {

             scanf("%d%d%d",&x,&y,&c);

             hang[x] = x,lie[y] = y;

             mp[pair<int,int> (x,y)] = c;

         }

         printf("Case #%d:\n",kase++);

         scanf("%d",&q);

         while(q--)

         {

             scanf("%d%d%d",&c,&x,&y);

             if(c == ) swap(hang[x],hang[y]);

             else if(c == ) swap(lie[x],lie[y]);

             else

             {

                 x = hang[x],y = lie[y];

                 printf("%d\n",mp[pair<int,int> (x,y)]);

             }

         }

     }

     return ;

 }

巴特西

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

最新文章

热门文章