1 条题解

  • 0
    @ 2021-6-15 14:28:40

    C++ :

    #include<cstdio>
    using namespace std;
    struct ANT{
        int x,y,time,blo,blo_up,lv,lx,ly,next;
        bool cake;
    };
    struct Tour{
        int x,y;
    };
    ANT ant[200010];
    int tot,many,target,top=0;
    Tour tour[22];
    int n,m,s,d,r,t;
    int ma_su[10][10];
    int ma_th[10][10];
    int xx[4]={0,1,0,-1};
    int yy[4]={1,0,-1,0};
    void Init();
    void work();
    void born();
    double Sqr(int );
    void put_su();
    void run();
    void hurt();
    bool cmp(int ,int ,int ,int ,int ,int );
    bool check();
    void print();
    int main()
    {
        Init();
        work();
    }
    void Init(){
        int i,j,k;
        scanf("%d%d",&n,&m);
        scanf("%d%d%d",&s,&d,&r);
        for(i=1;i<=s;i++){
            scanf("%d%d",&tour[i].x,&tour[i].y);
            ma_th[tour[i].x][tour[i].y]=-1;
        }
        scanf("%d",&t);
        tot=many=target=0;
        return ;
    }
    void work(){
        int i,j,T=0;
        while(++T<=t){
            born();
            put_su();
            run();
            hurt();
            if(check()){
                printf("Game over after %d seconds\n",T);
                print();
                return;
            }
            for(i=0;i<=n;i++)
                for(j=0;j<=m;j++)
                    ma_su[i][j]-=(ma_su[i][j]!=0?1:0);
            for(i=1;i<=tot;i++)
                ant[i].time++;
        }
        printf("The game is going on\n");
        print();
        return;
    }
    void born(){
        if(!ma_th[0][0]&&many<6){
            ant[top].next=++tot;
            ant[tot].lv=(tot-1)/6+1;
            ant[tot].blo=ant[tot].blo_up=int(4*Sqr(ant[tot].lv));
            ant[tot].time=0;
            ant[tot].x=ant[tot].y=0;ant[tot].lx=ant[tot].ly=-1;
            ma_th[0][0]=tot;
            many++;
            top=tot;
        }
    }
    double Sqr(int m){
        double ans=1,x=1.1;
        while(m){
            if(m&1)
                ans*=x;
            m>>=1;
            x*=x;
        }
        return ans;
    }
    void put_su(){
        int i;
        for(i=1;i<=tot;i++)
            if(ant[i].blo>=0)
                ma_su[ant[i].x][ant[i].y]+=(ant[i].cake?5:2);
    }
    void run(){
        int i,j,k,fx,X,Y,max;
        for(i=ant[0].next;i;i=ant[i].next){
            fx=-1;max=-1;
            for(j=0;j<=3;j++){
                X=ant[i].x+xx[j];
                Y=ant[i].y+yy[j];
                if(X<=n&&X>=0&&Y<=m&&Y>=0&&(X!=ant[i].lx||Y!=ant[i].ly)&&(!ma_th[X][Y])&&ma_su[X][Y]>max){
                    max=ma_su[X][Y];
                    fx=j;
                }
            }
            if(fx!=-1){
                   if(!((ant[i].time+1)%5))
                       for(j=1;j<=4;j++){
                           fx=(fx+4-1)%4;
                           X=ant[i].x+xx[fx];
                        Y=ant[i].y+yy[fx];
                           if(X<=n&&X>=0&&Y<=m&&Y>=0&&(X!=ant[i].lx||Y!=ant[i].ly)&&(!ma_th[X][Y]))
                               break;
                       }
                   ma_th[ant[i].x][ant[i].y]=0;
                   ant[i].lx=ant[i].x;ant[i].ly=ant[i].y;
                   ant[i].x+=xx[fx];ant[i].y+=yy[fx];
               }
               else{
                   ant[i].lx=-1;
                   ant[i].ly=-1;
            }
            if(ant[i].x==n&&ant[i].y==m&&!target){
                target=i;
                ant[i].cake=true;
                ant[i].blo=ant[i].blo+ant[i].blo_up/2<ant[i].blo_up?ant[i].blo+ant[i].blo_up/2:ant[i].blo_up;
            }
            ma_th[ant[i].x][ant[i].y]=i;
        }
    }
    void hurt(){
        int i,j,k,len,targ=-1,X,Y;
        for(i=1;i<=s;i++){
            X=ant[target].x-tour[i].x;Y=ant[target].y-tour[i].y;
            if(!target||X*X+Y*Y>r*r){
                len=10010;
                for(j=ant[0].next;j;j=ant[j].next)
                    if((tour[i].x-ant[j].x)*(tour[i].x-ant[j].x)+(tour[i].y-ant[j].y)*(tour[i].y-ant[j].y)<len){
                        targ=j;len=(tour[i].x-ant[j].x)*(tour[i].x-ant[j].x)+(tour[i].y-ant[j].y)*(tour[i].y-ant[j].y);
                    }
            }
            else
                targ=target;
            X=ant[targ].x-tour[i].x;Y=ant[targ].y-tour[i].y;
            if(X*X+Y*Y<=r*r)
            for(j=ant[0].next;j;j=ant[j].next)
                if(cmp(ant[j].x,ant[j].y,tour[i].x,tour[i].y,ant[targ].x,ant[targ].y))
                    ant[j].blo-=d;
        }
        j=0;
        for(i=ant[j].next;i;i=ant[i].next)
                if(ant[i].blo<0){
                    ma_th[ant[i].x][ant[i].y]=0;many--;
                    ant[j].next=ant[i].next;
                    if(i==target)
                        ant[i].cake=false;
                    if(i==top)
                        top=j;
                }
                else
                    j=i;
        if(!ant[target].cake)
            target=0;
    }
    bool cmp(int ax,int ay,int tx,int ty,int targx,int targy){
        double t_ax=ax-tx,t_ay=ay-ty,targ_ax=ax-targx,targ_ay=ay-targy,t_targx=targx-tx,t_targy=targy-ty;
        double R=(t_ax*t_targx+t_ay*t_targy)/(t_targx*t_targx+t_targy*t_targy);
        if(R<=0)return (t_ax*t_ax+t_ay*t_ay)<=0.25; 
        if(R>=1)return (targ_ax*targ_ax+targ_ay*targ_ay)<=0.25;
        double px=tx+(targx-tx)*R;
        double py=ty+(targy-ty)*R;
        return (ax-px)*(ax-px)+(ay-py)*(ay-py)<=0.25;
    }
    bool check(){
        return (target&&!ant[target].x&&!ant[target].y);
    }
    void print(){
        int i;
        printf("%d\n",many);
        for(i=ant[0].next;i;i=ant[i].next)
            printf("%d %d %d %d %d\n",ant[i].time,ant[i].lv,ant[i].blo,ant[i].x,ant[i].y);
    }
    
    • 1

    信息

    ID
    1003
    时间
    3000ms
    内存
    128MiB
    难度
    (无)
    标签
    递交数
    0
    已通过
    0
    上传者