2011 Asia Fuzhou Regional Contest

Xiangqi http://acm.hdu.edu.cn/showproblem.php?pid=4121

模拟,用高内聚低耦合的思想来写模拟题还是很好的，提高了函数的可重用性，程序的可读性，正确性，总而言之，写函数麻烦，总比debug麻烦来的好。

#include<cstdio>
const int M=16;
struct point{
    int x,y;
}p[M];
char has[M][M],op[M];
bool vis[M][M];
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
bool insidemap(const point &a){
    if(a.x>=1&&a.x<=10&&a.y>=1&&a.y<=9) return true;return false;
}
void flag(const point &a){
    vis[a.x][a.y]=true;
}
bool had(const point &a){
    if(has[a.x][a.y]!='.') return true;return false;
}
void step(point &a,int dir){
    a.x+=dx[dir];
    a.y+=dy[dir];
}
void solveG(point a){
    while(true){
        step(a,0);
        if(!insidemap(a)) return ;
        flag(a);
        if(had(a)) return ;
    }
}
void solveR(const point &b){
    for(int i=0;i<4;i++){
        point a=b;
        while(true){
            step(a,i);
            if(!insidemap(a)) break;
            flag(a);
            if(had(a)) break;
        }
    }
}
void solveH(const point &b){
    for(int i=0;i<4;i++){
        point a=b;
        step(a,i);
        if(had(a)) continue;
        step(a,i);
        if(i<2){
            for(int j=2;j<4;j++){
                point c=a;
                step(c,j);
                if(insidemap(c)) flag(c);
            }
        }
        else{
            for(int j=0;j<2;j++){
                point c=a;
                step(c,j);
                if(insidemap(c)) flag(c);
            }
        }
    }
}
void solveC(const point &b){
    for(int i=0;i<4;i++){
        point a=b;
        while(true){
            step(a,i);
            if(!insidemap(a)||had(a)) break;
        }
        while(true){
            step(a,i);
            if(!insidemap(a)) break;
            flag(a);
            if(had(a)) break;
        }
    }
}
bool insidehouse(const point &a){
    if(a.x>=1&&a.x<=3&&a.y>=4&&a.y<=6) return true;return false;
}
bool judge(const point &b){
    for(int i=0;i<4;i++){
        point a=b;
        step(a,i);
        if(insidehouse(a)&&!vis[a.x][a.y]) return false;
    }
    return true;
}
int main(){
    int n;
    while(~scanf("%d%d%d",&n,&p[0].x,&p[0].y),n|p[0].x|p[0].y){
        for(int i=1;i<=10;i++){
            for(int j=1;j<=9;j++){
                has[i][j]='.';
                vis[i][j]=false;
            }
        }
        for(int i=1;i<=n;i++){
            scanf("%s%d%d",op,&p[i].x,&p[i].y);
            has[p[i].x][p[i].y]=op[0];
        }
        for(int i=1;i<=n;i++){
            op[0]=has[p[i].x][p[i].y];
            if(op[0]=='G'){
                solveG(p[i]);
            }
            else if(op[0]=='R'){
                solveR(p[i]);
            }
            else if(op[0]=='H'){
                solveH(p[i]);
            }
            else{
                solveC(p[i]);
            }
        }
        puts(judge(p[0])?"YES":"NO");
    }
    return 0;
}

Alice's mooncake shop http://acm.hdu.edu.cn/showproblem.php?pid=4122

订单按顺序来，然后对第一个订单，暴力算，然后记录一下最小的id，第二个就可以从上一个订单时刻往后找，因为前面已经找过了，单调队列的思想。

#include<cstdio>
#include<cstring>
typedef __int64 LL;
const LL inf=0x3f3f3f3f3f3f3f3fLL;
const int M=32;
struct Date {
    int year, month, day;
}now;
int days[12]= {31,28,31,30,31,30,31,31,30,31,30,31};  //日期函数
class DATE {
public:
    int leap(int year) {       //判闰年
        return (year%4==0&&year%100!=0)||year%400==0;
    }
    int date2int(Date a) {  //日期转天数偏移
        int ret=a.year*365+(a.year-1)/4-(a.year-1)/100+(a.year-1)/400;
        days[1]+=leap(a.year);
        for(int i=0; i<a.month-1; ret+=days[i++]);
        days[1]=28;
        return ret+a.day;
    }
} help;
char yuefen[M][M]={"Jan", "Feb", "Mar", "Apr", "May", "Jun", "Jul", "Aug", "Sep", "Oct", "Nov" , "Dec"};
char month[M];
struct IN{
    LL time,R;
}in[3000];
int cost[100010];
int main(){
    int n,m,data,year,H,R;
    LL T,S;
    now.year=2000;
    now.month=now.day=1;
    int preday=help.date2int(now);
    while(~scanf("%d%d",&n,&m),n|m){
        int s=1,t=1;
        for(int i=0;i<n;i++){
            scanf("%s%d%d%d%I64d",month,&now.day,&now.year,&H,&in[i].R);
            for(int j=0;j<12;j++){
                if(!strcmp(yuefen[j],month)){
                    now.month=j+1;
                    break;
                }
            }
            in[i].time=(help.date2int(now)-preday)*24+H+1;
        }
        scanf("%I64d%I64d",&T,&S);
        for(int i=1;i<=m;i++){
            scanf("%d",&cost[i]);
        }
        LL ans=0;
        for(int i=0;i<n;i++){
            int id=0;
            LL sma=inf;
            for(int j=t;j<=in[i].time;j++){
                if(j+T<in[i].time) continue;
                LL c=(cost[j]+(in[i].time-j)*S)*in[i].R;
                if(sma>c){
                    sma=c;
                    id=j;
                }
            }
            if(s+T>=in[i].time){
                LL c=(cost[s]+(in[i].time-s)*S)*in[i].R;
                if(sma>c){
                    sma=c;
                    id=s;
                }
            }
            ans+=sma;
            s=id;
            t=in[i].time;
        }
        printf("%I64d
",ans);
    }
    return 0;
}

Bob’s Race http://acm.hdu.edu.cn/showproblem.php?pid=4123

用树上最长路，就是树的直径，然后求出每个点能到最远距离数组，对其rmq预处理，然后单调队列求。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#define mt(a,b) memset(a,b,sizeof(a))
using namespace std;
const int inf=0x3f3f3f3f;
const int M=50010;
struct G{
    struct E{
        int v,w,next;
    }e[M<<1];
    int le,head[M];
    void init(){
        le=0;
        mt(head,-1);
    }
    void add(int u,int v,int w){
        e[le].v=v;
        e[le].w=w;
        e[le].next=head[u];
        head[u]=le++;
    }
}g;
bool vis[M];
int n;
queue<int> q;
void bfs(int s,int dist[]){
    for(int i=1;i<=n;i++){
        dist[i]=inf;
        vis[i]=false;
    }
    vis[s]=true;
    dist[s]=0;
    while(!q.empty()) q.pop();
    q.push(s);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=g.head[u];~i;i=g.e[i].next){
            int v=g.e[i].v;
            if(vis[v]) continue;
            vis[v]=true;
            dist[v]=dist[u]+g.e[i].w;
            q.push(v);
        }
    }
}
int getfarid(int dist[]){
    int res,big=0;
    for(int i=1;i<=n;i++){
        if(big<dist[i]){
            big=dist[i];
            res=i;
        }
    }
    return res;
}
int d1[M],d2[M],a[M];
class Range_Maximum_Query{///区间最值查询离线算法init_o(nlogn),query_o(1)
    int LOG[M],dpmax[M][20],dpmin[M][20];
public:
    void init(){///使用类前调用一次即可
        LOG[0]=-1;
        for(int i=1;i<M;i++){
            LOG[i]=LOG[i>>1]+1;
        }
    }
    void Make_RMQ(int n,int a[]){///传入点的个数，下标1开始
        for(int i=1;i<=n;i++){
            dpmax[i][0]=dpmin[i][0]=a[i];
        }
        for(int j=1;j<=LOG[n];j++){
            for(int i=1;i+(1<<j)-1<=n;i++){
                dpmax[i][j]=max(dpmax[i][j-1],dpmax[i+(1<<(j-1))][j-1]);
                dpmin[i][j]=min(dpmin[i][j-1],dpmin[i+(1<<(j-1))][j-1]);
            }
        }
    }
    int get_RMQ(int a,int b,bool big){///传入1返回max，传入0返回min
        int k=LOG[b-a+1];
        if(big)
        return max(dpmax[a][k],dpmax[b-(1<<k)+1][k]);
        return min(dpmin[a][k],dpmin[b-(1<<k)+1][k]);
    }
}rmq;
int main(){
    int m,u,v,w;
    rmq.init();
    while(~scanf("%d%d",&n,&m),n|m){
        g.init();
        for(int i=0;i<n-1;i++){
            scanf("%d%d%d",&u,&v,&w);
            g.add(u,v,w);
            g.add(v,u,w);
        }
        bfs(1,d1);
        int ss=getfarid(d1);
        bfs(ss,d2);
        int tt=getfarid(d2);
        bfs(tt,d1);
        for(int i=1;i<=n;i++){
            a[i]=max(d1[i],d2[i]);
        }
        rmq.Make_RMQ(n,a);
        while(m--){
            scanf("%d",&w);
            int s=1,t=1,ans=0;
            while(true){
                if(rmq.get_RMQ(s,t,1)-rmq.get_RMQ(s,t,0)<=w){
                    ans=max(ans,t-s+1);
                    t++;
                }
                else{
                    s++;
                }
                if(t>n) break;
            }
            printf("%d
",ans);
        }
    }
    return 0;
}

end