题目：1002 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】的数组保存就好了、还有因为杀怪有花费所以要用优先队列

#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;
}

2014 ACM/ICPC Asia Regional Guangzhou Online