并不对劲的bzoj1972:loj2885:p2482[SDOI2010]猪国杀

Dear 丶 2023-08-17 16:46 75阅读 0赞

##### 题目大意 #####

只能放[链接][Link 1]了。

题目中有一点没说：并不是保证牌够用，而是在牌不够用时反复抽最后一张牌。

##### 题解 #####

发现玩家的数量比较少，所以可以不太在意时间够不够用。

考虑三件事：1.基本操作，如摸牌、出牌、玩家死亡、牌的效果；2.游戏流程；3.出牌对象。

1.  摸牌、出牌：  
    发现对于“某玩家的牌”的操作是从左往右扫第一张可用的，然后删掉（出牌），或者往最右放两张（摸牌），这两个操作用链表很好维护。建议把“判断从玩家\\(x\\)手牌里有没有值为\\(k\\)的，如果能，就把最左的\\(k\\)删去”和“在玩家\\(x\\)手牌最右放两张牌”这两个操作写成两个函数。建议记\\(a\_i\\)表示玩家\\(i\\)是否装武器。  
    玩家死亡：  
    用链表维护每个玩家前后存活的玩家。玩家死亡时，先判手里有没有P，如果有，把血量改为1并复活（因为所有能造成伤害的牌，都只能造成1的伤害，所以不会降到0以下）；如果没有，该玩家死亡，如果该玩家是MP或最后一个FP，则游戏结束，否则是FP的话伤害来源摸3张牌，是ZP且伤害来源是MP的话MP的手牌链表清空且令\\(a\_1=0\\)。  
    牌的效果：  
    \\(x\\)对\\(y\\)出K：\\(x\\)身份暴露，判断\\(y\\)是否有D，若有则无事发生，若没有则\\(y\\)血量减少，判断\\(y\\)是否死亡。  
    \\(x\\)出P：血量+1。  
    \\(x\\)出Z：令\\(a\_x=1\\)。  
    \\(x\\)出J：\\(x\\)身份暴露，从\\(x\\)开始依次判断是否有玩家成功出J，若有，则J被抵消；若没有，\\(x\\)出的J生效。建议用递归函数实现。  
    \\(x\\)出N或W：从\\(x\\)右边的玩家开始依次判断每个玩家是否会受伤，对于每个玩家，从\\(x\\)开始依次判断是否有玩家出J，若有则该玩家无事发生，若没有则判断该玩家能不能出K或D，若能则该玩家无事发生，否则该玩家掉血、判断死亡。这两个AOE几乎一样，建议一块写。需要注意的是，自己的AOE打到表明身份的队友时，可能会自己对自己的AOE出J。  
    \\(x\\)对\\(y\\)出F：\\(x\\)身份暴露，判J，判是否\\(x\\)为MP且\\(y\\)为ZP。维护两个指针，分别表示当前考虑到\\(x 、 y\\)的第几张牌。轮流移动指针至下一个K，如果一方没有K，则该方掉血、判断死亡。
2.  记当前玩家为\\(x\\)，用链表维护每个玩家前后存活的玩家。如果有人死亡则更新死亡者前后的玩家的链表。对于\\(x\\)的回合，先摸两张牌，再从左往右扫，如果无牌可出则回合结束，否则出牌，然后重新判断是否有牌可出（因为F、AOE出完后可能会有玩家出J，暴露身份，可能导致\\(x\\)有的牌变得可出）。需要注意\\(x\\)的回合可能因为\\(x\\)死亡而中断（\\(x\\)出F使自己死亡），要记\\(x\\)该回合是否出过K。
3.  K：对在自己右边相邻的，且已经表明身份，且是敌人的玩家。  
    F：MP对逆时针方向第一个表明身份的FP或类反猪；ZP对逆时针方向第一个表明身份的FP；FP只会对MP。  
    J：记\\(f(x,y,z)\\space z\\in\\\{0,1\\\}\\)表示上一张牌是\\(x\\)对\\(y\\)的\\(z\\)行为（\\(z=1\\)表示献殷勤，\\(z=0\\)表示表敌意），是否被抵消。若\\(z=1\\)且\\(k\\)认为\\(x\\)是敌人且\\(k\\)有J，则\\(k\\)出J，然后\\(f(k,x,0)\\)判断该J是否生效；若\\(z=0\\)且\\(k\\)认为\\(y\\)是友军且\\(k\\)有J，则\\(k\\)出J，然后\\(f(k,y,1)\\)判断该J是否生效。注意要在出牌瞬间更改出牌者的“表面身份”，不然会影响到别的玩家是否出J。

想完这些后，下一步就是写了。好像模拟的内容和题目描述稍有不同就会WA一大片……

##### 代码 #####

#include<algorithm>
    #include<cmath>
    #include<cstdio>
    #include<cstdlib>
    #include<cstring>
    #include<ctime>
    #include<iomanip>
    #include<iostream>
    #include<map>
    #include<queue>
    #include<set>
    #include<stack>
    #include<vector>
    #define rep(i,x,y) for(register int i=(x);i<=(y);++i)
    #define dwn(i,x,y) for(register int i=(x);i>=(y);--i)
    #define viewcd(u,k) for(int k=nxt[u];k;k=nxt[k])
    #define LL long long
    #define maxn 17
    #define maxm 2007
    using namespace std;
    int read()
    {
        int x=0,f=1;char ch=getchar();
        while(!isdigit(ch)&&ch!='-')ch=getchar();
        if(ch=='-')f=-1,ch=getchar();
        while(isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
        return x*f;
    }
    void write(int x)
    {
        if(x==0){putchar('0'),putchar('\n');return;}
        int f=0;char ch[20];
        if(x<0)putchar('-'),x=-x;
        while(x)ch[++f]=x%10+'0',x/=10;
        while(f)putchar(ch[f--]);
        putchar('\n');
        return;
    }
    int numpg,numcd,cf,stp;
    int h[maxn],w[maxn],p[maxn],n[maxn],fake[maxn],real[maxn];
    int nxt[maxm<<1],pre[maxm<<1],cntcd,chg;
    char c[maxm<<1],C[maxm],s[10];
    void addcd(int x,int k)
    {
        rep(i,1,k)
        {
            c[++cntcd]=C[numcd--];if(!numcd)numcd=1;
            nxt[pre[x]]=cntcd,pre[cntcd]=pre[x],pre[x]=cntcd,nxt[cntcd]=x;
        }
    }//x gets k cards.
    void del(int x,int k)
    {
        int nk=nxt[k],pk=pre[k];
        pre[nk]=pk,nxt[pk]=nk;
    }//x lose card k
    void clear(){nxt[1]=pre[1]=1;w[1]=0;return;}//x lose its cards.
    void kil(int x,int y)
    {
        if(real[y]==1&&x==1){clear();}
        else if(real[y]==3){cf--;if(!cf)stp=1;if(!stp)addcd(x,3);}
        else if(y==1)stp=1;
        if(stp)return;
        int ny=n[y],py=p[y];p[ny]=py,n[py]=ny;
    }//x kill y.
    int getcd(int x,char tp)
    {
        for(int k=nxt[x];k!=x;k=nxt[k])
            if(tp==c[k]){del(x,k);return 1;}
        return 0;
    }//get card tp of x.
    int reborn(int x){if(!getcd(x,'P'))return 0;h[x]=1;return 1;}//x is going to die.
    int enemy(int x,int y){if(((fake[y]&1)&&fake[y]!=real[x])||(x==1&&fake[y]==2))return 1;return 0;}//x wants to kill y.
    int nedJ(int x,int y,int f)
    {
        for(int k=n[x];k!=x;k=n[k])
        {
            if(!f&&fake[y]==real[k])
            {
                if(getcd(k,'J'))
                {
                    fake[k]=real[k];
                    if(!nedJ(k,y,1))return 1;
                }
            }
            if(f&&enemy(k,x))
            {
                if(getcd(k,'J'))
                {
                    fake[k]=real[k];
                    if(!nedJ(k,x,0))return 1;
                }
            }
        }
        return 0;
    }///x use ... on y
    //0:enemy;1:friend
    int prot(int x,int y)
    {
        if(fake[y]==real[x]){if(getcd(x,'J')){fake[x]=real[x];if(!nedJ(x,y,1))return 1;}}
        for(int k=n[x];k!=x;k=n[k])if(fake[y]==real[k])
        {
            if(getcd(k,'J'))
            {
                fake[k]=real[k];
                if(!nedJ(k,y,1))return 1;
            }
        }
        return 0;
    }//x use ... on y
    void K(int x,int y)
    {
        fake[x]=real[x];
        if(!getcd(y,'D')){h[y]--;if(h[y]==0&&!reborn(y))kil(x,y);}
    }//
    void F(int x,int y)
    {
        int kx=nxt[x],ky=nxt[y];
        fake[x]=real[x];
        if(prot(x,y))return;
        if(real[y]!=1||x!=1)
        {
            while(ky!=y)
            {
                for(;ky!=y;ky=nxt[ky])if(c[ky]=='K')break;
                if(c[ky]!='K')break;
                del(y,ky),ky=nxt[ky],swap(x,y),swap(kx,ky);
            }
        }
        if((real[y]==1&&x==1)||c[ky]!='K'){h[y]--;if(h[y]==0&&!reborn(y))kil(x,y);}
    }//
    void AOE(int x,char tp)//tp=='N':'K', tp=='W':'D'
    {
        char ned=(tp=='N')?'K':'D';
        for(int y=n[x];y!=x;y=n[y])if(!prot(x,y))
        {
            if(!getcd(y,ned))
            {
                h[y]--;
                if(!h[y]&&!reborn(y))kil(x,y);
                if(stp)return;
                if(y==1&&!fake[x])fake[x]=2;
            }
        }
    }
    int main()
    {
        numpg=read(),numcd=read();cntcd=numpg;
        rep(i,1,numpg)
        {
            scanf("%s",s);pre[i]=nxt[i]=i;
            real[i]=(s[0]=='M'||s[0]=='Z')?1:3;fake[i]=(i==1)?1:0;
            rep(j,1,4)
            {
                scanf("%s",s);
                c[++cntcd]=s[0];
                nxt[pre[i]]=cntcd,pre[cntcd]=pre[i],pre[i]=cntcd,nxt[cntcd]=i;
            }p[i]=(i-1)==0?numpg:i-1,n[i]=i==numpg?1:i+1,h[i]=4;
            if(real[i]==3) cf++;
        }
        rep(i,1,numcd){scanf("%s",s);C[numcd-i+1]=s[0];}
        if(cf==0)stp=1;
        for(int x=1;!stp;x=n[x]) 
        {
            addcd(x,2);int mk=0,k;
            usecd:
            chg=0;
            for(k=nxt[x];k!=x;k=nxt[k])
            {
                if(c[k]=='K'&&(!mk||w[x])&&enemy(x,n[x]))
                {
                    mk=1;del(x,k),K(x,n[x]);chg=1;break;
                }
                else if(c[k]=='F')
                {
                    int y;
                    if(real[x]==3){del(x,k),F(x,1);}
                    else 
                    {
                        for(y=n[x];y!=x;y=n[y])if(enemy(x,y)){break;}
                        if(!enemy(x,y))continue;
                        del(x,k),F(x,y);
                    }
                    chg=1;break;
                }
                else if(c[k]=='N'||c[k]=='W'){del(x,k),AOE(x,c[k]);chg=1;break;}
                else if(c[k]=='Z'){del(x,k),w[x]=1;chg=1;break;}
                else if(c[k]=='P'&&h[x]<4){del(x,k),h[x]++;}
            }
            if(chg&&!stp&&h[x]){goto usecd;}
            if(stp)break;
        }
        puts(h[1]>0?"MP":"FP");
        rep(i,1,numpg)
        {
            if(h[i]<=0){printf("DEAD");}
            else {for(int k=nxt[i];k!=i;k=nxt[k]){printf("%c ",c[k]);}}
            puts("");
        }
        return 0;
    }

##### 一些感想 #####

终于可以肆无忌惮地玩梗了！

转载于:https://www.cnblogs.com/xzyf/p/11276120.html

[Link 1]: https://loj.ac/problem/2885