2014 ACM/ICPC Asia Regional Guangzhou Online

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

题目：1002 [A Corrupt Mayor's Performance Art][A Corrupt Mayor_s Performance Art]

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

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

AC代码：

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <iostream>
    #include <vector>
    #include <map>
    using namespace std;
    const int N = 1110000;
    struct Node
    {
        int l,r;
        long long num;
    };
    Node tree[4*N];
    map<int,int> mp;
    //int vis[35];
    vector<int> v;
    void build(int l,int r,int o)
    {
        tree[o].l=l;
        tree[o].r=r;
        tree[o].num=2;
        if(l==r)
            return ;
        int mid=(l+r)/2;
        build(l,mid,o*2);
        build(mid+1,r,o*2+1);
    }
    void update(int l,int r,int t,int o)
    {
        if(tree[o].l==l && tree[o].r==r)
        {
            tree[o].num=t;
            return;
        }
        if(tree[o].num==t) return;
        if(tree[o].num!=-1)
        {
            tree[2*o].num=tree[o].num;
            tree[2*o+1].num=tree[o].num;
            tree[o].num=-1;
        }
        int mid=(tree[o].l+tree[o].r)>>1;
        if(r<=mid)
            update(l,r,t,o+o);
        else if(l>mid)
            update(l,r,t,o+o+1);
        else
        {
            update(l,mid,t,o*2);
            update(mid+1,r,t,o*2+1);
        }
    }
    void query(int l,int r,int o)
    {
        if(tree[o].num!=-1)
        {
            if(!mp[tree[o].num]){
                v.push_back(tree[o].num);
                mp[tree[o].num]=1;
            }
            return ;
        }
        int mid=(tree[o].l+tree[o].r)>>1;
        if(r<=mid)
            query(l,r,o+o);
        else if(l>mid)
            query(l,r,o+o+1);
        else
        {
            query(l,mid,o*2);
            query(mid+1,r,o*2+1);
        }
    }
    int main()
    {
        //freopen("Input.txt","r",stdin);
        int n,m;
        while(~scanf("%d%d",&n,&m))
        {
            if(n==0 && m==0)
                break;
            build(1,n,1);
            while(m--)
            {
                getchar();
                char ok;
                int x,y,z;
                scanf("%c",&ok);
                if(ok=='P')
                {
                    scanf("%d%d%d",&x,&y,&z);
                    update(x,y,z,1);
                }
                else
                {
                    int ans=0;
                    v.clear();
                    mp.clear();
                    scanf("%d%d",&x,&y);
                    query(x,y,1);
                    sort(v.begin(),v.end());
                    for(int i=0;i<v.size();i++)
                        printf("%d%c",v[i],i==(v.size()-1)?'\n':' ');
                }
            }
        }
        return 0;
    }

题目：1003 Wang Xifeng's Little Plot

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

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

AC代码：

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <iostream>
    #include <vector>
    #include <map>
    using namespace std;
    const int N = 111;
    char mp[N][N];
    int dis[10];
    int n;
    int solve(int x,int y)
    {
        memset(dis,0,sizeof(dis));
        for(int j=y;j<n;j++)
        {
            if(mp[x][j]=='.')
                dis[0]++;
            else
                break;
        }
        for(int i=x,j=y;i<n&&j<n;i++,j++)
        {
            if(mp[i][j]=='.')
                dis[1]++;
            else
                break;
        }
        for(int i=x;i<n;i++)
        {
            if(mp[i][y]=='.')
                dis[2]++;
            else
                break;
        }
        for(int i=x,j=y;i<n && j>=0;i++,j--)
        {
            if(mp[i][j]=='.')
                dis[3]++;
            else
                break;
        }
        for(int j=y;j>=0;j--)
        {
            if(mp[x][j]=='.')
                dis[4]++;
            else
                break;
        }
        for(int i=x,j=y;i>=0 && j>=0;i--,j--)
        {
            if(mp[i][j]=='.')
                dis[5]++;
            else
                break;
        }
        for(int i=x;i>=0;i--)
        {
            if(mp[i][y]=='.')
                dis[6]++;
            else
                break;
        }
        for(int i=x,j=y;i>=0 && j<n;i--,j++)
        {
            if(mp[i][j]=='.')
                dis[7]++;
            else
                break;
        }
        int ans=0;
        for(int i=0;i<8;i++)
        {
            ans=max(ans,dis[i]+dis[(i+2)%7]);
            ans=max(ans,dis[i]+dis[(i+4)%7]);
        }
        return (ans-1);
    }
    int main()
    {
        //freopen("Input.txt","r",stdin);
        while(~scanf("%d",&n) && n)
        {
            for(int i=0;i<n;i++)
            {
                getchar();
                for(int j=0;j<n;j++)
                    scanf("%c",&mp[i][j]);
            }
            int ans=0;
            for(int i=0;i<n;i++)
            {
                for(int j=0;j<n;j++){
                    //printf("%c",mp[i][j]);
                    if(mp[i][j]=='.')
                        ans=max(ans,solve(i,j));
                }
            }
            printf("%d\n",ans);
        }
        return 0;
    }

题目：1004 Saving Tang Monk

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

分析：BFS+状态压缩

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

AC代码：

#include <cstdio>
    #include<iostream>
    #include <queue>
    #include <cstring>
    using namespace std;
    const int N = 100;
    char mp[N][N];
    int vis[N][N][10][1<<5];
    struct Node
    {
        int x,y,step;
        int key ,e ;
    };
    int dx[6]= {0,0,1,-1};
    int dy[6]= {1,-1,0,0};
    int m,n,t;
    bool operator <(Node a, Node b)
    {
        return a.step > b.step;
    }
    
    
    int BFS(Node st,Node en)
    {
        memset(vis,0,sizeof(vis));
        st.step = 0;
        st.key=0,st.e=0;
        vis[st.x][st.y][0][0]=1;
        priority_queue<Node> q;
        q.push(st);
        Node tmp1,tmp2;
        while(!q.empty())
        {
            tmp1 = q.top();
            //printf("xxx%d\n",tmp1.step);
            q.pop();
            //printf("---%d %dxx\n",tmp1.key ,(1<<(t)-1));
            if(tmp1.x==en.x && tmp1.y==en.y && tmp1.key== t)
                return tmp1.step;
            for(int i=0; i<4; i++)
            {
                tmp2.x=tmp1.x+dx[i];
                tmp2.y=tmp1.y+dy[i];
                tmp2.step = tmp1.step+1;
                tmp2.e = tmp1.e ;
                tmp2.key = tmp1.key ;
                if(tmp2.x >=1 && tmp2.x <= n && tmp2.y >= 1 && tmp2.y <= n && mp[tmp2.x][tmp2.y] != '#')
                {
    
    
                    if(mp[tmp2.x][tmp2.y]>='A' && mp[tmp2.x][tmp2.y] <='F')
                    {
                        //printf("No\n");
                        int tu = mp[tmp2.x][tmp2.y]-'A' ;
                        if(tmp2.e &(1<<tu))//
                        {
                            if(!vis[tmp2.x][
                               tmp2.y][tmp2.key][tmp2.e])
                            {
                                vis[tmp2.x][tmp2.y][tmp2.key][tmp2.e] = true ;
                                q.push(tmp2) ;
                            }
                        }
                        else
                        {
                            tmp2.step++ ;
                            tmp2.e |= (1<<tu) ;
                            q.push(tmp2) ;
                        }
                    }
                    else if(mp[tmp2.x][tmp2.y]>='1' && mp[tmp2.x][tmp2.y]<='9')
                    {
                        //printf("YES\n");
                        int tu = mp[tmp2.x][tmp2.y]-'0' ;
                        if(tu == tmp2.key + 1)
                        {
                            tmp2.key = tu ;
                            q.push(tmp2) ;
                        }
                        else
                        {
                            if(!vis[tmp2.x][tmp2.y][tmp2.key][tmp2.e])
                            {
                                vis[tmp2.x][tmp2.y][tmp2.key][tmp2.e] = true ;
                                q.push(tmp2) ;
                            }
                        }
                    }
                    else if(!vis[tmp2.x][tmp2.y][tmp2.key][tmp2.e])
                    {
                        vis[tmp2.x][tmp2.y][tmp2.key][tmp2.e] = true ;
                        q.push(tmp2) ;
                    }
                }
            }
        }
        return -1;
    }
    int main()
    {
        //freopen("Input.txt","r",stdin);
        while(~scanf("%d%d",&n,&t))
        {
            char c='A';
            if(n==0 && t==0)
                break;
            Node st,en;
            m=n;
            for(int i=1; i<=m; i++)
            {
                getchar();
                for(int j=1; j<=n; j++)
                {
                    scanf("%c",&mp[i][j]);
                    if(mp[i][j]=='S')
                    {
                        mp[i][j]=c++;
                    }
                    if(mp[i][j]=='K')
                        st.x=i,st.y=j;
                    if(mp[i][j]=='T')
                        en.x=i,en.y=j;
                }
            }
            int ans=BFS(st,en);
    //        for(int i=1;i<=n;i++)
    //        {
    //            for(int j=1;j<=n;j++)
    //            {
    //                printf("%d",vis[i][j][1]);
    //            }
    //            printf("\n");
    //        }
            if(ans==-1)
                printf("impossible\n");
            else
                printf("%d\n",ans);
        }
        return 0;
    }

[A Corrupt Mayor_s Performance Art]: http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1002&cid=535