BZOJ1972：[SDOI2010]猪国杀

我对模拟的理解：https://www.cnblogs.com/AKMer/p/9064018.html

题目传送门：https://www.lydsy.com/JudgeOnline/problem.php?id=1972

一个好看的题面传送门：https://mubu.com/doc/2707815814591da4

因为这两个月比较忙（其实是颓得太多了……），所以猪国杀昨晚\(0\)点左右才A掉。

总用时，不超过24小时吧。

总结了以下坑点，其余的按题面模拟就对了：

\(1、决斗导致自己死亡马上终止出牌阶段\)

\(2、牌堆用完了不停地去抓最后一张牌\)

\(3、主猪杀忠猪记得弃掉猪哥连弩\)

\(4、最后一张牌杀了反猪结果新摸进来3张牌，不要直接就结束了，3张牌也是可以打天下的！！！\)

\(5、如果你不是非常无聊或者非常神，那么最好不要碰这道题，这比杀蚂蚁和灭鼠行动坑多了\)

这题写得我累了，所以不能像之前那样扯皮了，也不想详细讲解了

还是杀蚂蚁好玩儿

还有很多细节，具体看代码注解吧

还有，我的模拟之路就到此为止了

时间复杂度：\(O(n)\)

空间复杂度：\(O(n)\)

代码如下：

#include <cstdio>

#include <algorithm>

using namespace std;

const int maxm=2005;

//最多2000张牌

int card[maxm];//存手牌

int n,m,cnt,now_card,now_pig,fz_cnt;

//n是猪的头数，m是牌的张数，cnt用于记录手牌编号

//now_card用于记录牌堆里的牌摸到了第几张，now_pig记录当前轮到哪一头猪，fz(反猪)_cnt记录反猪头数

int read() {

    int x=0,f=1;char ch=getchar();

    for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;

    for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<1)+(x<<3)+ch-'0';

    return x*f;

}//快读

struct CARD {

    int fake;//fake记录手牌内容

    int nxt,lst;//nxt记录当前牌右边的牌的编号，lst记录左边的

}hand_card[maxm*10];//因为牌抓完了会不断抓最后一张，所以保险起见开了十倍

void del_card(int &now,int id);

//因为PIG结构体里要用到del_card，然后del_card要用到PIG里的东西，所以在这里声明一下，写在main后面

struct PIG {

    bool equi;//equi记录是否有诸葛连弩

    int iden,hp,sta;//iden记录身份，hp记录血量，sta记录跳忠跳反状态

    int tail,head,nxt,lst;//head是自己的id，也是手牌开始的编号，tail是手里最后一张牌的编号，nxt记录自己的下家的猪的编号，lst记录上家

    void build(int id) {//初始化每头猪

        char s[10];hp=4;//hp赋成4

        scanf("%s",s+1);

        if(s[1]=='M')iden=1,sta=1;//主猪iden为1，状态为已跳

        if(s[1]=='Z')iden=2,sta=0;//忠猪iden为2，状态为未知身份

        if(s[1]=='F')iden=3,sta=0,fz_cnt++;//反猪iden为3，状态也是未知身份

        nxt=id+1,lst=id-1;//先简单的安排好上家下家

        if(id==n)nxt=1;//n号猪的下家是1号猪

        if(id==1)lst=n;//1号猪的上家是n号猪

        head=tail=id;//初始化手牌链表

        for(int i=1;i<=4;i++) {

            scanf("%s",s+1);

            hand_card[++cnt].fake=s[1]-'A';

            hand_card[cnt].lst=tail;

            hand_card[tail].nxt=cnt;

            tail=cnt;//摸初始的四张牌

        }

    }

    void show_hand_card() {//输出手牌

        if(!hp) {puts("DEAD");return;}//生命值为0就输出DEAD

        int now=hand_card[head].nxt;//因为head不存东西，所以手牌是从head的下一张开始的

        while(now) {

            printf("%c ",'A'+hand_card[now].fake);

            now=hand_card[now].nxt;

        }puts("");//记得换行

    }

    void get_card(int num) {//摸num张牌

        for(int i=1;i<=num;i++) {

            hand_card[++cnt].fake=card[now_card];

            if(now_card!=m)now_card++;//如果还没有摸到最后一张牌就使下一张牌为下一次摸牌对象

            hand_card[cnt].lst=tail;

            hand_card[tail].nxt=cnt;

            tail=cnt;//同build里的抓牌

        }

    }

    bool eat_peach() {//濒死吃桃

        int now=hand_card[head].nxt;

        while(now) {

            if(hand_card[now].fake=='P'-'A') {hp++;del_card(now,head);return 1;}//记得HP++;别光吃桃不加血

            now=hand_card[now].nxt;

        }

        if(iden==3)fz_cnt--;//没有桃可以吃就死掉，如果是反猪就减一头反猪

        return 0;

    }

    bool find_hand_card(int v) {//打1张v牌

        int now=hand_card[head].nxt;

        while(now) {

            if(hand_card[now].fake==v) {

                del_card(now,head);

				return 1;

            }

            now=hand_card[now].nxt;

        }

        if(v!='J'-'A')hp--;//如果不是要打无懈可击就扣血

        if(!hp)eat_peach();//如果濒死就吃桃

        return 0;

    }

}pig[15];

bool be_enemy(int x,int y,int limit) {//判断x与y是否是敌人（limit=1是，limit=0否，满足返回1，否则返回0）

    if(!pig[y].sta)return 0;//如果y的身份未知就不算

    if(pig[y].sta==-1) {

        if(x==1&&limit)return 1;//如果是主猪对类反并且limit=1就对了

        else return 0;

    }

    return ((pig[x].iden<3)!=(pig[y].iden<3))==limit;//否则直接判断

}

int find_tar(int id) {//帮id号猪找决斗对象

    int now=pig[id].nxt;

    while(now!=id) {

        if(be_enemy(id,now,1))return now;//如果找到就return

        now=pig[now].nxt;

    }

    return 0;

}

bool check_satu(int id,int tar) {//检查局面

    if(!fz_cnt)return 1;

    if(!pig[1].hp)return 1;//如果满足游戏结束条件就return

    if(pig[tar].iden==3)pig[id].get_card(3);//如果死的是反猪则奖励牌

    if(pig[tar].iden==2&&id==1)pig[1].equi=0,pig[1].tail=1,hand_card[1].nxt=0;//如果主猪误杀忠猪则弃牌

    int a=pig[tar].lst,b=pig[tar].nxt;

    pig[a].nxt=b;pig[b].lst=a;//在链表上抹去tar号猪

    return 0;

}

bool WXKJ(int st,int id,bool limit) {//从st开始出无懈，需要和id的关系为limit（为1表示敌对，0表示同类）

    if(pig[id].sta<=0)return 0;//不能对没有跳身份的猪表敌意献殷勤

    int now=st;

    while(1) {

        if((be_enemy(now,id,limit)&&pig[now].find_hand_card('J'-'A')) ){

            pig[now].sta=1;//出无懈会跳身份

            if(WXKJ(now,now,1))return 0;//如果没有猪无懈这张无懈就无懈成功

            return 1;//否则失败

        }

        now=pig[now].nxt;

        if(now==st)break;//一圈绕完break

    }

    return 0;//没人无懈，此锦囊牌有效

}

void fight(int x,int y) {

    if(WXKJ(x,y,0))return;//从x开始，帮y无懈，成功就return

    if(x==1&&pig[y].iden==2)pig[y].hp--;//如果是主猪对忠猪那么忠猪直接扣血

    else {

        while(pig[x].hp&&pig[y].hp&&pig[y].find_hand_card('K'-'A')&&pig[x].find_hand_card('K'-'A'));//不然轮流出杀，find_hand_card里写好了扣血的程序，因为被动出牌的话出不出来肯定扣血，所以直接写在find_hand_card里了

    }

}

bool AOE(int id,int card) {//需要用card来挡AOE

    int pos=pig[id].nxt;

    while(pos!=id) {

        if(WXKJ(id,pos,0)) {pos=pig[pos].nxt;continue;}//从使用这张锦囊的猪开始，看有没有人愿意帮pos无懈掉

        if(pig[pos].find_hand_card(card)) {pos=pig[pos].nxt;continue;}//或者说pos自己可以挡下来，挡不下来就扣血

        if(!pig[pos].hp&&check_satu(id,pos))return 1;//检查局面

        pos=pig[pos].nxt;

    }

    return 0;//没有造成游戏结束

}

void work(int id) {

    pig[id].get_card(2);int nxt=pig[id].nxt;//id号猪摸牌

    int now=hand_card[id].nxt;

    bool kill=1;//表示可以出杀

    while(now) {

        bool  bo=0;

        if(pig[id].hp<4&&hand_card[now].fake=='P'-'A')

            pig[id].hp++,del_card(now,id),bo=1;//如果可以吃桃就吃

        if(hand_card[now].fake=='K'-'A'&&be_enemy(id,nxt,1)&&(kill||pig[id].equi)) {//如果和下家是敌对关系并且可以出杀或者有诸葛连弩

            pig[nxt].find_hand_card('D'-'A'),del_card(now,id);pig[id].sta=1;kill=0;//下家出不出闪就扣血，id跳身份

            if(!pig[nxt].hp) {//如果杀死了，濒死在find_hand_card里判了的

                if(check_satu(id,nxt))return;//如果游戏结束就return

                nxt=pig[id].nxt;//更新下家编号

            }

            now=hand_card[id].nxt;bo=1;//牌回到最左边

        }

        if(hand_card[now].fake=='Z'-'A')

            pig[id].equi=1,del_card(now,id),now=hand_card[id].nxt,bo=1;//装上诸葛连弩，牌回到最左边

        if(hand_card[now].fake=='F'-'A') {

            int target=0;

            if(pig[id].iden==3)target=1;//反猪的决斗全部留给主猪

			else target=find_tar(id);//找决斗目标

            if(target) {

                bo=1;pig[id].sta=1;

                fight(id,target);

                del_card(now,id);//决斗

                if(!pig[target].hp&&check_satu(id,target))return;//如果干死别人使得游戏结束就退出

                if(!pig[id].hp) {check_satu(target,id);return;}//如果自己挂了肯定要结束出牌阶段了，顺便判判局面

                now=hand_card[id].nxt;

            }

        }

        if(hand_card[now].fake=='N'-'A') {

            int MP_HP=pig[1].hp;bo=1;//南猪入侵

            del_card(now,id);

            if(AOE(id,'K'-'A'))return;

            if(pig[1].hp<MP_HP&&!pig[id].sta)

                pig[id].sta=-1;//如果伤害了主猪并且身份未知就变类反

            now=hand_card[id].nxt;

        }

        if(hand_card[now].fake=='W'-'A') {

            int MP_HP=pig[1].hp;bo=1;

            del_card(now,id);

            if(AOE(id,'D'-'A'))return;

            if(pig[1].hp<MP_HP&&!pig[id].sta)

                pig[id].sta=-1;

            now=hand_card[id].nxt;//同南猪入侵,不过改成出闪

        }

        if(!bo)now=hand_card[now].nxt;//如果now没打出去，那么就跳到下一张牌去

		//之所以把now=hand_card[id].nxt放在最后，是因为很可能会有用手里的最后一张牌杀掉反猪的情况，如果写在前面，那么就不会去使用奖励的三张牌了

    }

}

int main() {

    cnt=n=read(),m=read();

    for(int i=1;i<=n;i++)

        pig[i].build(i);

    char s[10];

    for(int i=1;i<=m;i++) {

        scanf("%s",s+1);

        card[i]=s[1]-'A';

    }now_pig=now_card=1;//读入猪和手牌

    while(pig[1].hp&&fz_cnt) {

        work(now_pig);

        now_pig=pig[now_pig].nxt;

    }//模拟游戏过程

    if(pig[1].hp)puts("MP");//主猪有血说明主猪赢了

    else puts("FP");//否则反猪赢了

    for(int i=1;i<=n;i++)

        pig[i].show_hand_card();//输出最后局面

    return 0;

}

void del_card(int &now,int id) {

    int a=hand_card[now].lst,b=hand_card[now].nxt;

    hand_card[a].nxt=b;hand_card[b].lst=a;

    if(pig[id].tail==now)pig[id].tail=a;//假如删掉的是最右边的牌记得更新tail，否则下次摸牌可能就接不上来了哦

    now=b;

}