2014 ACM/ICPC Asia Regional Guangzhou Online

喜欢ヅ旅行 2022-08-12 06:29 134阅读 0赞

题目：1002 A Corrupt Mayor’s Performance Art

题意：有一个长度 n 的序列，初始染色2，有两种操作，P x ,y ,z,区间x—-y染色为z，另一种Q x，y，查询区间 x — y 有几种颜色，并输出，注意会覆盖。

分析：跟POJ 2777一样，不过这个要输出颜色，所以线段树查询的时候顺便把路径存起来打印。代码：

AC代码：

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <algorithm>
  4. #include <iostream>
  5. #include <vector>
  6. #include <map>
  7. using namespace std;
  8. const int N = 1110000;
  9. struct Node
  10. {
  11.     int l,r;
  12.     long long num;
  13. };
  14. Node tree[4*N];
  15. map<int,int> mp;
  16. //int vis[35];
  17. vector<int> v;
  18. void build(int l,int r,int o)
  19. {
  20.     tree[o].l=l;
  21.     tree[o].r=r;
  22.     tree[o].num=2;
  23.     if(l==r)
  24.         return ;
  25.     int mid=(l+r)/2;
  26.     build(l,mid,o*2);
  27.     build(mid+1,r,o*2+1);
  28. }
  29. void update(int l,int r,int t,int o)
  30. {
  31.     if(tree[o].l==l && tree[o].r==r)
  32.     {
  33.         tree[o].num=t;
  34.         return;
  35.     }
  36.     if(tree[o].num==t) return;
  37.     if(tree[o].num!=-1)
  38.     {
  39.         tree[2*o].num=tree[o].num;
  40.         tree[2*o+1].num=tree[o].num;
  41.         tree[o].num=-1;
  42.     }
  43.     int mid=(tree[o].l+tree[o].r)>>1;
  44.     if(r<=mid)
  45.         update(l,r,t,o+o);
  46.     else if(l>mid)
  47.         update(l,r,t,o+o+1);
  48.     else
  49.     {
  50.         update(l,mid,t,o*2);
  51.         update(mid+1,r,t,o*2+1);
  52.     }
  53. }
  54. void query(int l,int r,int o)
  55. {
  56.     if(tree[o].num!=-1)
  57.     {
  58.         if(!mp[tree[o].num]){
  59.             v.push_back(tree[o].num);
  60.             mp[tree[o].num]=1;
  61.         }
  62.         return ;
  63.     }
  64.     int mid=(tree[o].l+tree[o].r)>>1;
  65.     if(r<=mid)
  66.         query(l,r,o+o);
  67.     else if(l>mid)
  68.         query(l,r,o+o+1);
  69.     else
  70.     {
  71.         query(l,mid,o*2);
  72.         query(mid+1,r,o*2+1);
  73.     }
  74. }
  75. int main()
  76. {
  77.     //freopen("Input.txt","r",stdin);
  78.     int n,m;
  79.     while(~scanf("%d%d",&n,&m))
  80.     {
  81.         if(n==0 && m==0)
  82.             break;
  83.         build(1,n,1);
  84.         while(m--)
  85.         {
  86.             getchar();
  87.             char ok;
  88.             int x,y,z;
  89.             scanf("%c",&ok);
  90.             if(ok=='P')
  91.             {
  92.                 scanf("%d%d%d",&x,&y,&z);
  93.                 update(x,y,z,1);
  94.             }
  95.             else
  96.             {
  97.                 int ans=0;
  98.                 v.clear();
  99.                 mp.clear();
  100.                 scanf("%d%d",&x,&y);
  101.                 query(x,y,1);
  102.                 sort(v.begin(),v.end());
  103.                 for(int i=0;i<v.size();i++)
  104.                     printf("%d%c",v[i],i==(v.size()-1)?'\n':' ');
  105.             }
  106.         }
  107.     }
  108.     return 0;
  109. }

题目：1003 Wang Xifeng’s Little Plot

题意：给出一个图，只能转90度，求最大的能走多少？

分析：枚举每一个点为转角点，然后判断8个方向的值，保存起来，然后保存一个最大值就可以了、

AC代码：

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <algorithm>
  4. #include <iostream>
  5. #include <vector>
  6. #include <map>
  7. using namespace std;
  8. const int N = 111;
  9. char mp[N][N];
  10. int dis[10];
  11. int n;
  12. int solve(int x,int y)
  13. {
  14.     memset(dis,0,sizeof(dis));
  15.     for(int j=y;j<n;j++)
  16.     {
  17.         if(mp[x][j]=='.')
  18.             dis[0]++;
  19.         else
  20.             break;
  21.     }
  22.     for(int i=x,j=y;i<n&&j<n;i++,j++)
  23.     {
  24.         if(mp[i][j]=='.')
  25.             dis[1]++;
  26.         else
  27.             break;
  28.     }
  29.     for(int i=x;i<n;i++)
  30.     {
  31.         if(mp[i][y]=='.')
  32.             dis[2]++;
  33.         else
  34.             break;
  35.     }
  36.     for(int i=x,j=y;i<n && j>=0;i++,j--)
  37.     {
  38.         if(mp[i][j]=='.')
  39.             dis[3]++;
  40.         else
  41.             break;
  42.     }
  43.     for(int j=y;j>=0;j--)
  44.     {
  45.         if(mp[x][j]=='.')
  46.             dis[4]++;
  47.         else
  48.             break;
  49.     }
  50.     for(int i=x,j=y;i>=0 && j>=0;i--,j--)
  51.     {
  52.         if(mp[i][j]=='.')
  53.             dis[5]++;
  54.         else
  55.             break;
  56.     }
  57.     for(int i=x;i>=0;i--)
  58.     {
  59.         if(mp[i][y]=='.')
  60.             dis[6]++;
  61.         else
  62.             break;
  63.     }
  64.     for(int i=x,j=y;i>=0 && j<n;i--,j++)
  65.     {
  66.         if(mp[i][j]=='.')
  67.             dis[7]++;
  68.         else
  69.             break;
  70.     }
  71.     int ans=0;
  72.     for(int i=0;i<8;i++)
  73.     {
  74.         ans=max(ans,dis[i]+dis[(i+2)%7]);
  75.         ans=max(ans,dis[i]+dis[(i+4)%7]);
  76.     }
  77.     return (ans-1);
  78. }
  79. int main()
  80. {
  81.     //freopen("Input.txt","r",stdin);
  82.     while(~scanf("%d",&n) && n)
  83.     {
  84.         for(int i=0;i<n;i++)
  85.         {
  86.             getchar();
  87.             for(int j=0;j<n;j++)
  88.                 scanf("%c",&mp[i][j]);
  89.         }
  90.         int ans=0;
  91.         for(int i=0;i<n;i++)
  92.         {
  93.             for(int j=0;j<n;j++){
  94.                 //printf("%c",mp[i][j]);
  95.                 if(mp[i][j]=='.')
  96.                     ans=max(ans,solve(i,j));
  97.             }
  98.         }
  99.         printf("%d\n",ans);
  100.     }
  101.     return 0;
  102. }

题目：1004 Saving Tang Monk

题意：给出一个图，从 K 往 T 走，路上有钥匙，最多9个，然后有怪，杀死怪花费1，必须拿够全部的钥匙才行，求最短时间。

分析：BFS+状态压缩

开始想到状态压缩钥匙，后面发现杀怪物也要状态压缩，这样的话数组内存太大，发现钥匙有个条件，就是必须要全部拿到前几个钥匙才能拿下一个，那么我们可以直接用【9】的数组保存就好了、还有因为杀怪有花费所以要用优先队列

AC代码：

  1. #include <cstdio>
  2. #include<iostream>
  3. #include <queue>
  4. #include <cstring>
  5. using namespace std;
  6. const int N = 100;
  7. char mp[N][N];
  8. int vis[N][N][10][1<<5];
  9. struct Node
  10. {
  11.     int x,y,step;
  12.     int key ,e ;
  13. };
  14. int dx[6]= {0,0,1,-1};
  15. int dy[6]= {1,-1,0,0};
  16. int m,n,t;
  17. bool operator <(Node a, Node b)
  18. {
  19.     return a.step > b.step;
  20. }
  23. int BFS(Node st,Node en)
  24. {
  25.     memset(vis,0,sizeof(vis));
  26.     st.step = 0;
  27.     st.key=0,st.e=0;
  28.     vis[st.x][st.y][0][0]=1;
  29.     priority_queue<Node> q;
  30.     q.push(st);
  31.     Node tmp1,tmp2;
  32.     while(!q.empty())
  33.     {
  34.         tmp1 = q.top();
  35.         //printf("xxx%d\n",tmp1.step);
  36.         q.pop();
  37.         //printf("---%d %dxx\n",tmp1.key ,(1<<(t)-1));
  38.         if(tmp1.x==en.x && tmp1.y==en.y && tmp1.key== t)
  39.             return tmp1.step;
  40.         for(int i=0; i<4; i++)
  41.         {
  42.             tmp2.x=tmp1.x+dx[i];
  43.             tmp2.y=tmp1.y+dy[i];
  44.             tmp2.step = tmp1.step+1;
  45.             tmp2.e = tmp1.e ;
  46.             tmp2.key = tmp1.key ;
  47.             if(tmp2.x >=1 && tmp2.x <= n && tmp2.y >= 1 && tmp2.y <= n && mp[tmp2.x][tmp2.y] != '#')
  48.             {
  51.                 if(mp[tmp2.x][tmp2.y]>='A' && mp[tmp2.x][tmp2.y] <='F')
  52.                 {
  53.                     //printf("No\n");
  54.                     int tu = mp[tmp2.x][tmp2.y]-'A' ;
  55.                     if(tmp2.e &(1<<tu))//
  56.                     {
  57.                         if(!vis[tmp2.x][
  58.                            tmp2.y][tmp2.key][tmp2.e])
  59.                         {
  60.                             vis[tmp2.x][tmp2.y][tmp2.key][tmp2.e] = true ;
  61.                             q.push(tmp2) ;
  62.                         }
  63.                     }
  64.                     else
  65.                     {
  66.                         tmp2.step++ ;
  67.                         tmp2.e |= (1<<tu) ;
  68.                         q.push(tmp2) ;
  69.                     }
  70.                 }
  71.                 else if(mp[tmp2.x][tmp2.y]>='1' && mp[tmp2.x][tmp2.y]<='9')
  72.                 {
  73.                     //printf("YES\n");
  74.                     int tu = mp[tmp2.x][tmp2.y]-'0' ;
  75.                     if(tu == tmp2.key + 1)
  76.                     {
  77.                         tmp2.key = tu ;
  78.                         q.push(tmp2) ;
  79.                     }
  80.                     else
  81.                     {
  82.                         if(!vis[tmp2.x][tmp2.y][tmp2.key][tmp2.e])
  83.                         {
  84.                             vis[tmp2.x][tmp2.y][tmp2.key][tmp2.e] = true ;
  85.                             q.push(tmp2) ;
  86.                         }
  87.                     }
  88.                 }
  89.                 else if(!vis[tmp2.x][tmp2.y][tmp2.key][tmp2.e])
  90.                 {
  91.                     vis[tmp2.x][tmp2.y][tmp2.key][tmp2.e] = true ;
  92.                     q.push(tmp2) ;
  93.                 }
  94.             }
  95.         }
  96.     }
  97.     return -1;
  98. }
  99. int main()
  100. {
  101.     //freopen("Input.txt","r",stdin);
  102.     while(~scanf("%d%d",&n,&t))
  103.     {
  104.         char c='A';
  105.         if(n==0 && t==0)
  106.             break;
  107.         Node st,en;
  108.         m=n;
  109.         for(int i=1; i<=m; i++)
  110.         {
  111.             getchar();
  112.             for(int j=1; j<=n; j++)
  113.             {
  114.                 scanf("%c",&mp[i][j]);
  115.                 if(mp[i][j]=='S')
  116.                 {
  117.                     mp[i][j]=c++;
  118.                 }
  119.                 if(mp[i][j]=='K')
  120.                     st.x=i,st.y=j;
  121.                 if(mp[i][j]=='T')
  122.                     en.x=i,en.y=j;
  123.             }
  124.         }
  125.         int ans=BFS(st,en);
  126. //        for(int i=1;i<=n;i++)
  127. //        {
  128. //            for(int j=1;j<=n;j++)
  129. //            {
  130. //                printf("%d",vis[i][j][1]);
  131. //            }
  132. //            printf("\n");
  133. //        }
  134.         if(ans==-1)
  135.             printf("impossible\n");
  136.         else
  137.             printf("%d\n",ans);
  138.     }
  139.     return 0;
  140. }

发表评论

表情：
评论列表 （有 0 条评论，134人围观）

还没有评论，来说两句吧...

相关阅读