BZOJ1972:[SDOI2010]猪国杀

时间:2024-06-28 23:33:26

我对模拟的理解: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;
}