题解 P2482 【[SDOI2010]猪国杀】

opened · 2018-10-15 08:24:22 · 题解

题解:大模拟、字符串

这道题模拟即可、坑点过多，也不知道考场上有没有人能写出来

盘点一下坑点，程序中有体现（前人填坑利后人）

1. 桃濒死时吃完记得回血,不要磕完桃还是0血状态

2. 用牌之前就要标记好不能再用了

3. 主公（猪）弃牌要弃装备（猪哥连弩）

4. 对于锦囊牌先用懈再判定，因为出锦囊的人（猪）是有可能无懈掉这个锦囊的（这个是真滴皮）

5.有人（猪）死亡的时候要重新更新第一目标

6.出决斗的人（猪）可能死在自己回合里，这时候立即终止他（它）的出牌阶段

7.（坑的极致）当牌堆的最后一张牌没了的时候，你需要一直摸最后一张牌（所以叫猪国杀是吧）

·大佬的样例来一波（都是主猪获胜，反猪全部死亡情况【亲测】，建议调试时输出主猪与忠猪的血量）（都是套路）:

1. 1

   5 10 MP W D F K ZP N N D D FP F W W K ZP K K N D FP K D P W J K W K D N N K J N

2. 2

   3 4 MP J J K N ZP J D K W FP P N P K J J K W

3. 3

   3 10 MP W D J W ZP J P D N FP N D F F J D N N F J J D K W

4. 4

   3 1 MP D N F K ZP F W F N FP D N N D K

Talk is cheap, show me the code.

#include<iostream>
#include<cstdio>
#define N 5010
using namespace std;
int n,m, L[N],R[N],cnt,/*双向链表*/ realID[11],Fpig_alive/*反猪数量*/,GameOver,NowRound;
char kind[N],card_unused[3010]/*牌堆*/;int top;
inline char Card(){return top==m?card_unused[top]:card_unused[++top];}
inline void judge(int &t,int &w,int &p,int &f){
    kind[++cnt]=Card();L[cnt]=t;
    if(kind[cnt]=='J')w++; if(kind[cnt]=='P')p++; if(kind[cnt]=='D')f++;
}
void Sha(int,int);void Fight(int,int);void Nanpig(int);void Wanjian(int);
struct Pig{
    int showingID, head,tail,now,pos, blood, wuxie,peach,flash, first_attack, Lpig,Rpig, dead,weapon,num;
    void S_card(){//无懈可击、桃、闪——特判
        judge(tail,wuxie,peach,flash);
        if(head==0) head=tail=cnt;
        else R[tail]=cnt,tail=cnt;
        judge(tail,wuxie,peach,flash),R[tail]=cnt,tail=cnt;
        judge(tail,wuxie,peach,flash),R[tail]=cnt,tail=cnt;
    }
    void Punish(){//清空手牌
        head=tail=now=wuxie=peach=flash=weapon=0;
    }
    void CardStage(){//摸牌函数
        judge(tail,wuxie,peach,flash);
        if(head==0) head=tail=cnt;
        else R[tail]=cnt,tail=cnt;
        judge(tail,wuxie,peach,flash),R[tail]=cnt,tail=cnt;
    }
    void Use(int x){//出牌
        if(kind[x]=='J')wuxie--; if(kind[x]=='P')peach--; if(kind[x]=='D')flash--;
        if(x==head&&x==tail) head=0,tail=0;//核心操作:重铸链表
        else if(x==head) head=R[x],L[R[x]]=0;
        else if(x==tail) tail=L[x],R[L[x]]=0;
        else L[R[x]]=L[x],R[L[x]]=R[x];
    }
    char GetNext(){//下一头猪
        if(!now) return 0;
        pos=now,now=R[now];
        return kind[pos];
    }
    void Output(){//输出函数
        if(dead) puts("DEAD");
        else {
            while(head!=0){
                cout<<kind[head];
                if(head!=tail) printf(" ");
                head=R[head];
            }
            printf("\n");
        }
    }
    int find1(){now=head; for(char i;i!='D';i=GetNext()); return pos;}
    int find2(){now=head; for(char i;i!='P';i=GetNext()); return pos;}
    int find3(){now=head; for(char i;i!='J';i=GetNext()); return pos;}
    bool Q_K(){//杀
        now=head;char i;
        while(i=GetNext())
            if(i=='K'){ Use(pos);return 1;}
        return 0;
    }
    bool Q_F(){if(flash){ Use(find1());return 1;} return 0;}
    bool Q_P(){if(peach){ Use(find2());return 1;} return 0;}
    bool Q_W(){if(wuxie){ Use(find3());return 1;} return 0;}
    void Round(){//回合函数
        CardStage();
        now=head;char i;bool useKill=0;
        while((i=GetNext())&&!GameOver){
            switch(i){//出牌效果
                case 'D': continue;
                case 'J': continue;
                case 'P':if(blood!=4) blood++,Use(pos); continue;
                case 'K':{
                    if(first_attack==Rpig&&(!useKill||weapon)){
                        Use(pos),Sha(num,first_attack),now=head,useKill=1;
                        if(GameOver) return;
                    } continue;
                }
                case 'F':{
                    if(!first_attack) continue; Use(pos);
                    if(realID[num]==3) Fight(num,1);
                    else Fight(num,first_attack); now=head;
                    if(GameOver||dead) return;
                     continue;
                }
                case 'N':Use(pos),Nanpig(num),now=head;if(GameOver) return; continue;
                case 'W':Use(pos),Wanjian(num),now=head;if(GameOver) return; continue;
                case 'Z':Use(pos),weapon=1,now=head; continue;
            }
        }
    }
}pig[11];
void Update(int x){//更新态度
    int i=pig[x].Rpig;
    if(realID[x]==1){
        while(i!=x){
            if(pig[i].showingID==1||pig[i].showingID==3){
                pig[x].first_attack=i;
                return;
            }
            i=pig[i].Rpig;
        }
        pig[x].first_attack=0;
    }
    else if(realID[x]==2){
        while(i!=x){
            if(pig[i].showingID==3){
                pig[x].first_attack=i;
                return;
            }
            i=pig[i].Rpig;
        }
        pig[x].first_attack=0;
    }
    else{
        while(i!=x){
            if(pig[i].showingID==2||realID[i]==1){
                pig[x].first_attack=i;
                return;
            }
            i=pig[i].Rpig;
        }
        pig[x].first_attack=0;
    }
}
void Update_all(){//重视每头猪
    int r=pig[1].Rpig;
    Update(1);
    while(r!=1) Update(r),r=pig[r].Rpig;
}
void Kill(int x,int y){//击杀
    pig[y].dead=true;
    if(realID[y]==1){GameOver=true;return;}
    if(realID[y]==3){
        Fpig_alive--;
        if(!Fpig_alive){GameOver=true;return;}
        pig[x].S_card();
    }
    if(realID[y]==2&&realID[x]==1) pig[x].Punish();
    int l=pig[y].Lpig,r=pig[y].Rpig;//更新链表
    pig[l].Rpig=r,pig[r].Lpig=l;
    Update_all();
}
void Hurt(int x,int y){//掉血、加血
    pig[y].blood--;
    if(!pig[y].blood){
        if(pig[y].Q_P()) pig[y].blood++;
        else Kill(x,y);
    }
}
void Sha(int x,int y){//杀
    if(realID[x]!=1&&pig[x].showingID<2){
        if(realID[y]==3) pig[x].showingID=2;
        else pig[x].showingID=3;
        Update_all();
    }
    if(pig[y].Q_F()) return;
    Hurt(x,y);
}
bool WX_cycling(int x,bool vis){//核心操作:无懈循环
    int viss=vis,pos=x,i=x;
    if(vis==(realID[i]==3)){
        if(pig[i].Q_W()){
            pos=i,vis^=1;
            if(pig[i].showingID<=2) pig[i].showingID=3-vis,Update_all();
        }
    }
    for(i=pig[i].Rpig;i!=pos;i=pig[i].Rpig)if(vis==(realID[i]==3)){
            if(pig[i].Q_W()){
                pos=i,vis^=1;
                if(pig[i].showingID<=2) pig[i].showingID=3-vis,Update_all();
            }
        }
    return viss!=vis;
}
void Fight(int x,int y){//决斗
    if(realID[x]!=1&&pig[x].showingID<2){
        if(realID[y]==3) pig[x].showingID=2;
        else pig[x].showingID=3;
        Update_all();
    }
    if(realID[y]==1||pig[y].showingID>=2){
        if(realID[y]==1||pig[y].showingID==2){
            if(WX_cycling(x,0)) return;
        }
        else {if(WX_cycling(x,1)) return;}
    }
    if(realID[x]==1&&realID[y]==2) Hurt(x,y);
    else {
        while(1){
            if(!pig[y].Q_K()) {Hurt(x,y);return;}
            if(!pig[x].Q_K()) {Hurt(y,x);return;}
        }
    }
}
void Nanpig(int x){//南猪入侵
    int i=pig[x].Rpig;
    while(i!=x){
        if(realID[i]==1||pig[i].showingID>=2){
            if(realID[i]==1||pig[i].showingID==2){
                if(WX_cycling(x,0)){i=pig[i].Rpig; continue;}
            }
            else {
                if(WX_cycling(x,1)){i=pig[i].Rpig; continue;}
            }
        }
        if(!pig[i].Q_K()){
            Hurt(x,i);
            if(GameOver) return;
            if(i==1&&!pig[x].showingID) pig[x].showingID=1,Update_all();
        }
        i=pig[i].Rpig;
    }
}
void Wanjian(int x){//万箭齐发
    int i=pig[x].Rpig;
    while(i!=x){
        if(realID[i]==1||pig[i].showingID>=2){
            if(realID[i]==1||pig[i].showingID==2){
                if(WX_cycling(x,0)){i=pig[i].Rpig; continue;}
            }
            else {
                if(WX_cycling(x,1)){i=pig[i].Rpig; continue;}
            }
        }
        if(!pig[i].Q_F()){
            Hurt(x,i);
            if(GameOver) return;
            if(i==1&&!pig[x].showingID) pig[x].showingID=1,Update_all();
        }
        i=pig[i].Rpig;
    }
}
void addcard(int &pos){char s[10];scanf("%s",s),card_unused[++pos]=s[0];}//添牌
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) pig[i].Rpig=i+1,pig[i].Lpig=i-1;//双向链表
    pig[n].Rpig=1,pig[1].Lpig=n;
    int pos=0;
    for(int i=1;i<=n;i++){//读牌
        char s[10];scanf("%s",s);
        if(s[0]=='M') realID[i]=1;
        else if(s[0]=='Z') realID[i]=2;
        else if(s[0]=='F') realID[i]=3,Fpig_alive++;
        for(int i=1;i<=4;i++) addcard(pos);
    }
    for(int i=1;i<=m;i++) addcard(pos);
    m+=4*n;
    for(int i=1;i<=n;i++){
        pig[i].CardStage(),pig[i].CardStage();//摸牌
        pig[i].num=i,pig[i].blood=4;//初始化
    }
    Update_all();
    for(int i=1;!GameOver;i=pig[i].Rpig) NowRound=i,pig[i].Round();//回合
    if(pig[1].dead) puts("FP");
    else puts("MP");
    for(int i=1;i<=n;i++) pig[i].Output();//出牌
}