Solution - P2482 [SDOI2010]猪国杀

Posted on 2021-12-18 Edited on 2026-03-23
P2482 [SDOI2010]猪国杀

全解代码

#include <cstdio>
#include <vector>
#include <queue>
#include <stdlib.h>
//[桃]P  [杀]K  [闪]D  [决斗]F  [南猪入侵]N  [万箭齐发]W  [无懈可击]J  [猪哥连弩]Z
using namespace std;
const int N = 11, M = 2001, MAXN = 2e5 + 1;
int n, m, remainFP, ne[N];  // n猪数  m牌堆中牌数  remainFP剩余反猪数  ne[]下一只活着的猪
bool remainMP = 1, penalize = 0;  // remainMP主猪活着吗  penalize主猪要罚吗
queue<char> deskcard;             //牌堆
char E;                           //最后一张牌：因为如果牌堆拿完了那就拿最后一张牌
class List                        //不会用STL list 写了个非常拉胯的List
{
public:
    int begin;      //第一张
    int end;        //最后一张
    char v[MAXN];   //牌
    int nex[MAXN];  //下一张
    int pre[MAXN];  //上一张
    void pb(int x)  //将一张牌放到最后
    {
        if (begin == end && end == 0)
            begin = 1;
        nex[end] = end + 1;
        pre[end + 1] = end;
        v[++end] = x;
        nex[end] = 0;
    }
    void del(int x)  //删除某一张牌
    {
        if (x == begin)
            begin = nex[begin];
        if (x == end)
            end = pre[end];
        nex[pre[x]] = nex[x];
        pre[nex[x]] = pre[x];
    }
    void putcard()  //输出所有牌
    {
        for (int j = begin; j; j = nex[j]) putchar(v[j]), putchar(' ');
        puts("");
    }
};
class Pig  //猪
{
public:
    char tag;       //类型  'Z'忠猪  'F'反猪  'M'主猪
    char inZP;      //在忠猪眼里它的身份(其实是没有用的)
    char inFP;      //在反猪眼里它的身份(其实也是没有用的)
    char inMP;      //在主猪眼里它的身份(这是有用的因为,有类反猪)
    int HP;         //血量
    List handcard;  //手牌
    bool jump;      //跳了没
    bool zgln;      //有没有猪哥连弩
    bool dead;      //死了没
} A[N];
inline void Jump(int i)  //跳
{
    A[i].inZP = A[i].inMP = A[i].inFP = A[i].tag, A[i].jump = 1;  //跳了相当于所有猪眼中他都是知道的了
}
inline void getcard(int i)  //摸一张牌
{
    if (deskcard.empty())
        A[i].handcard.pb(E);  //如果摸完了就摸最后一张
    else
        A[i].handcard.pb(deskcard.front()), deskcard.pop();  //要不然正常摸
}
inline int read()  //快读一个int
{
    int num = 0;
    char ch = getchar();
    while (ch > '9' || ch < '0') ch = getchar();
    while (ch <= '9' && ch >= '0') num = (num << 1) + (num << 3) + (ch ^ 48), ch = getchar();
    return num;
}
inline char get()  //快读一个大写字母
{
    char ch = getchar();
    while (ch > 'Z' || ch < 'A') ch = getchar();
    return ch;
}
inline int getne(int x)  //找到下一个没死的并更新ne[]
{
    if (A[ne[x]].dead)
        ne[x] = getne(ne[x]);
    return ne[x];
}
inline bool Findcard(int cur, char c)  //找到一张指定的卡牌c,如果找到返回true并删掉这张牌
{
    for (int i = A[cur].handcard.begin; i; i = A[cur].handcard.nex[i]) {
        if (A[cur].handcard.v[i] == c) {
            A[cur].handcard.del(i);
            return true;
        }
    }
    return false;
}
inline void Die(int a, int b)  // a杀了b
{
    A[b].dead = 1;  // b死了
    if (A[b].tag == 'M')
        remainMP = 0;  //主猪死了
    else if (A[b].tag == 'F')
        --remainFP;  //反猪死了
    if (!remainMP || !remainFP)
        return;                        //[注意]:游戏结束了要退出
    if (A[b].dead && A[b].tag == 'F')  //杀反猪有奖:三张牌
    {
        getcard(a);
        getcard(a);
        getcard(a);
    } else if (A[b].dead && A[b].tag == 'Z' && A[a].tag == 'M')  //主猪杀忠猪有罚:全部弃置
    {
        A[a].handcard.begin = 0, A[a].handcard.end = 0;
        A[a].zgln = 0;  //[注意]:一定要把装备卸掉
        penalize = 1;
    }
}
inline void BeP(int cur)  // cur被迫用[桃]
{
    if (Findcard(cur, 'P'))
        ++A[cur].HP;
}
inline void BeD(int cur)  // cur被迫用[闪]
{
    if (Findcard(cur, 'D'))
        ++A[cur].HP;  //这里是预先扣掉了血，如果用[闪]加回去
}
inline void K(int a, int b)  // a对b用[杀]
{
    --A[b].HP;  //预先扣掉
    BeD(b);     //被迫用[闪]
    if (A[b].HP <= 0)
        BeP(b);  //没血了被迫用[桃]
    if (A[b].HP <= 0)
        Die(a, b);  //还是没血那就滚蛋
}
bool JJ(int cur)  //用[无懈可击]对付cur发起的[无懈可击]
{
    for (int i = getne(cur); cur != i && remainMP && remainFP; i = getne(i)) {
        bool sec = 0;
        if (A[i].tag == 'M' && A[cur].tag == 'F' || A[i].tag == 'Z' && A[cur].tag == 'F' ||
            A[i].tag == 'F' && A[cur].tag == 'M' ||
            A[i].tag == 'F' && A[cur].tag == 'Z')  //如果i和cur不是一队的
        {  //[注意]:由于使用过[无懈可击]的一定跳身份了，所以只需要判断tag
            if (Findcard(i, 'J'))  //如果能找到并使用[无懈可击]
            {
                Jump(i);                      //跳
                return JJ(i) ? false : true;  //往下递归,取反
            }
        }
    }
    return true;  //没人可以[无懈可击],就返回true
}
bool JF(int a, int b)  //用[无懈可击]对付a对b发起的决斗
{
    if (!A[b].jump)
        return false;  //如果b没有跳,任何人都不会帮他，包括他自己
    for (int i = getne(a); i != a && remainMP && remainFP; i = getne(i)) {
        if (A[i].tag == 'M' && A[b].tag == 'M' || A[i].tag == 'Z' && A[b].tag == 'Z' ||
            A[i].tag == 'F' && A[b].tag == 'F' || A[i].tag == 'Z' && A[b].tag == 'M' ||
            A[i].tag == 'M' && A[b].tag == 'Z')  //如果i和b是一队的
        {
            if (Findcard(i, 'J'))  //如果能找到并删除
            {
                Jump(i);       //跳
                return JJ(i);  //看看能不能被[无懈可击]搞掉
            }
        }
    }
    return false;
}
inline void F(int a, int b)  // a对b发起决斗
{
    if (JF(a, b))
        return;                              //如果可以被[无懈可击]搞掉,那就直接结束
    if (A[a].tag == 'M' && A[b].tag == 'Z')  //[注意]:如果a是主猪b是忠猪,那忠猪会选择不出[杀],直接扣血
    {                                        //[注意]:忠猪并不能跳忠
        --A[b].HP;                           //扣血
        if (A[b].HP <= 0)
            BeP(b);  //如果没血了就被动用[桃]
        if (A[b].HP <= 0)
            Die(a, b);  //如果仍然没血就滚蛋
        return;
    }
    while (remainMP && remainFP) {
        if (!Findcard(b, 'K'))  //如果b找不到[杀],那么b扣血
        {
            --A[b].HP;
            if (A[b].HP <= 0)
                BeP(b);
            if (A[b].HP <= 0)
                Die(a, b);
            return;
        }
        if (!Findcard(a, 'K'))  //如果a找不到[杀],那么a扣血
        {
            --A[a].HP;
            if (A[a].HP <= 0)
                BeP(a);
            if (A[a].HP <= 0)
                Die(b, a);  //注意如果a死了伤害来源是b
            return;
        }
    }
}
inline bool MyP(int cur)  // cur主动用[桃]
{
    if (A[cur].HP < 4)  //不满就用
    {
        ++A[cur].HP;
        return true;
    }
    return false;  //满了不用
}
inline bool MyK(int cur)  // cur主动用[杀]
{
    if (A[cur].tag == 'Z' && A[getne(cur)].inZP == 'F' || A[cur].tag == 'M' && A[getne(cur)].inMP == 'F' ||
        A[cur].tag == 'F' && A[getne(cur)].inFP == 'M' ||
        A[cur].tag == 'F' && A[getne(cur)].inFP == 'Z')  //如果下一个是敌人
    {
        Jump(cur), K(cur, getne(cur));  //[注意]:用[杀]会跳
        return true;
    }
    return false;  //如果下一个不是敌人那就不杀(废话)
}
inline bool MyZ(int cur)  // cur主动用[猪哥连弩](最良心的卡)
{
    A[cur].zgln = 1;  //装备
    return true;
}
inline bool MyF(int cur)  // cur主动用[决斗]
{
    bool used = 0;
    for (int i = getne(cur); i != cur && remainMP && remainFP; i = getne(i))  //找到下一个能决斗的
    {
        if (A[cur].tag == 'Z' && A[i].inZP == 'F' || A[cur].tag == 'M' && A[i].inMP == 'F' ||
            A[cur].tag == 'F' && A[i].inFP == 'M')  //找到目标
        {  //[注意]:反猪遇到第一个忠猪不会用[决斗]!因为他会优先考虑主猪!
            used = 1;
            Jump(cur);  //用[决斗]要跳
            F(cur, i);
            break;
        }
    }
    return used;
}
inline bool MyN(int cur)  // cur主动用[南猪入侵]
{
    for (int i = getne(cur); cur != i && remainMP && remainFP; i = getne(i))  //逆时针依次结算每一只猪
    {
        if (A[i].jump &&  //[注意]:要是i没有跳谁都不会帮他!
            (A[i].tag == 'Z' && A[cur].tag == 'Z' || A[i].tag == 'Z' && A[cur].tag == 'M' ||
             A[i].tag == 'M' && A[cur].tag == 'Z' || A[i].tag == 'M' && A[cur].tag == 'M' ||
             A[i].tag == 'F' && A[cur].tag == 'F'))  //找到队友
        {
            if (Findcard(cur, 'J')) {
                Jump(cur);  //[注意]:用了[无懈可击]一定会跳
                if (JJ(cur))
                    continue;  //如果成功了那就下一只
            }
        }
        bool sec = 0;  //是否成功
        for (int j = getne(cur); A[i].jump && j != cur && remainMP && remainFP;
             j = getne(j)) {  //从[南猪入侵]使用者开始依次得到[无懈可击]的机会
            if (A[i].jump &&  //同上,跳了才行
                (A[i].tag == 'Z' && A[j].tag == 'Z' || A[i].tag == 'Z' && A[j].tag == 'M' ||
                 A[i].tag == 'M' && A[j].tag == 'Z' || A[i].tag == 'M' && A[j].tag == 'M' ||
                 A[i].tag == 'F' && A[j].tag == 'F'))
                if (Findcard(j, 'J')) {
                    Jump(j);  //跳
                    if (JJ(j)) {
                        sec = 1;  //成功退出
                        break;
                    }
                }
        }
        if (sec || Findcard(i, 'K'))
            continue;  //如果[无懈可击]成功或者找到[杀]那就不扣血
        --A[i].HP;     //扣血
        if (A[i].tag == 'M')
            A[cur].inMP = 'F';  //[注意]:要是用[南猪入侵]伤害到主猪他会认为你是类反猪!
        if (A[i].HP <= 0)       //没血了用桃
        {
            BeP(i);
            if (A[i].HP <= 0)
                Die(cur, i);  //没桃了滚蛋
        }
    }
    return true;
}
inline bool MyW(int cur)  // cur主动用[万箭齐发]
{                         //同[南猪入侵]
    for (int i = getne(cur); cur != i && remainMP && remainFP; i = getne(i)) {
        if (A[i].jump && (A[i].tag == 'Z' && A[cur].tag == 'Z' || A[i].tag == 'Z' && A[cur].tag == 'M' ||
                          A[i].tag == 'M' && A[cur].tag == 'Z' || A[i].tag == 'M' && A[cur].tag == 'M' ||
                          A[i].tag == 'F' && A[cur].tag == 'F')) {
            if (Findcard(cur, 'J')) {
                Jump(cur);
                if (JJ(cur))
                    continue;
            }
        }
        bool sec = 0;
        for (int j = getne(cur); A[i].jump && j != cur && remainMP && remainFP; j = getne(j)) {
            if (A[i].jump && (A[i].tag == 'Z' && A[j].tag == 'Z' || A[i].tag == 'Z' && A[j].tag == 'M' ||
                              A[i].tag == 'M' && A[j].tag == 'Z' || A[i].tag == 'M' && A[j].tag == 'M' ||
                              A[i].tag == 'F' && A[j].tag == 'F'))
                if (Findcard(j, 'J')) {
                    Jump(j);
                    if (JJ(j)) {
                        sec = 1;
                        break;
                    }
                }
        }
        if (sec || Findcard(i, 'D'))
            continue;
        --A[i].HP;
        if (A[i].tag == 'M')
            A[cur].inMP = 'F';
        if (A[i].HP <= 0) {
            BeP(i);
            if (A[i].HP <= 0)
                Die(cur, i);
        }
    }
    return true;
}
inline void Go(int cur)  //轮到cur��回合
{
    bool useK = 0, sec = 0;                          // sec是否成功
    for (int i = A[cur].handcard.begin;              //从第一张牌开始
         i && !A[cur].dead && remainMP && remainFP;  //没死
         i = sec ? A[cur].handcard.begin : A[cur].handcard.nex[i],
             sec = 0) {                   //[注意]:如果成功用了一张牌切记要重新扫一遍
        char now = A[cur].handcard.v[i];  //当前的牌
        switch (now) {
            case 'P':  //[桃]
                if (MyP(cur))
                    A[cur].handcard.del(i), sec = 1;
                break;
            case 'K':  //[杀]
                if (!useK || A[cur].zgln)
                    if (MyK(cur))
                        useK = 1, A[cur].handcard.del(i), sec = 1;
                break;
            case 'Z':  //[猪哥连弩]
                MyZ(cur), A[cur].handcard.del(i);
                sec = 1;
                break;
            case 'F':  //[决斗]
                if (MyF(cur))
                    A[cur].handcard.del(i), sec = 1;
                break;
            case 'N':  //[南猪入侵]
                MyN(cur), A[cur].handcard.del(i);
                sec = 1;
                break;
            case 'W':  //[万箭齐发]
                MyW(cur), A[cur].handcard.del(i);
                sec = 1;
                break;
            default:  //其他不能主动用的
                break;
        }
        if (penalize && A[cur].tag == 'M') {  //[注意]：如果主猪被惩罚了那要赶紧结束回合
            penalize = 0;
            break;
        }
    }
}
inline void Solve()  //开始猪国杀
{
    int i = 1;
    while (remainFP && remainMP)  //游戏未结束
    {
        getcard(i);
        getcard(i);    //摸两张牌
        Go(i);         //进入i的回合
        i = getne(i);  //下一只小猪猪
    }
    return;
}
int main()  //主函数
{
    n = read(), m = read();
    for (int i = 1; i <= n; ++i) {
        ne[i] = i + 1;     //下一只没死的就是下一只
        A[i].HP = 4;       //初始血量是4
        A[i].tag = get();  //第i只猪的身份
        if (A[i].tag == 'F')
            ++remainFP;  //反猪数量记录
        if (A[i].tag == 'M')
            remainMP = 1, Jump(i);                            //主猪开局就跳
        get();                                                //读掉那个没用的'P'
        A[i].handcard.begin = 0, A[i].handcard.end = 0;       //清空卡牌
        for (int j = 0; j < 4; ++j) A[i].handcard.pb(get());  //四张初始牌
    }
    ne[n] = 1;                                         //最后一只猪的下一只是第一只
    for (int i = 1; i < m; ++i) deskcard.push(get());  //桌上的牌
    E = get();
    deskcard.push(E);  //最后一张牌
    Solve();           //开始猪国杀
    if (!remainFP)
        puts("MP");  //如果反猪没了主猪赢
    else
        puts("FP");               //如果主猪没了反猪赢
    for (int i = 1; i <= n; ++i)  //输出
    {
        if (A[i].dead)
            puts("DEAD");  //如果挂了那就挂了
        else
            A[i].handcard.putcard();  //没挂摊牌
    }
    return 0;
}