题解 P2482 【[SDOI2010]猪国杀】
学无止境
2018-02-18 16:08:38
~~这是一道无比水的模拟题%%~~
** NOI/NOI+/CTSC** 的难度标签告诉我们,模拟的路不好走啊~~
# 注意 !#
1.反猪是FP,不是AP,题目描述错误(不过样例是对的)
2.亲测,猪的数量为**2≤n≤10**,数据范围有误(现在已经更改)
3.逆时针是编号从**1,2,3...n,1...**的顺序
3.关于决斗我们要注意
(1)反猪决斗对象一直是主猪
(2)决斗不限制距离,所以查找对象时不能只找下一头
(3)主猪找忠猪决斗,忠猪一定掉血
(4)使用决斗的猪可能自己死亡,此时它的回合必须立即结束
4.无懈可击的响应顺序是**从使用这张锦囊的猪开始,按照逆时针顺序**,依次得到使用无懈可击的机会
5.使用杀,决斗,无懈可击意味着你跳了身份
6.除了桃,使用其他牌可能导致最左边可以使用的牌发生变化
(1)使用诸葛连弩,之前扫过的杀还能用
(2)使用锦囊牌,若他猪响应无懈可击,就跳了身份,可能导致之前的杀,决斗找到对象,变得可以使用
(3)综上述两条,每使用一张牌(除了桃),就要重新将下标回到最左边,再扫一次
7.类反猪一定只对主猪而言,且其未跳身份
8.把反猪杀死了(若游戏还未结束)要摸三张牌,主猪杀死了忠猪要弃掉全部牌,包括猪哥连弩
9.牌堆只剩一张牌时,就一直摸这张牌
10.一切执行的前提是**游戏尚未结束**,一旦达成胜利条件,游戏立刻结束,因此即使会摸3张牌或者还有牌可以用也不用执行了
11.对于下标要掌握好,使用一张牌后下标要自减(自减1或直接变成0),变成零意味着重新找最左边可以使用的牌
12.猪的死亡导致猪距离的改变
~~注意了这些后,就是一顿乱搞了233~~
细节十分重要,要有耐心,仔细,思考清楚后再打代码。
下面贴出我的代码,为了使结构清楚,可以多使用函数,本蒟蒻代码丑,不过应该不难理解。
当然,如果你只是部分错误,还是去检查一下我刚刚说的几点,自己查错会更好哦(上面的多看几遍)
**Code:**
```
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
struct pig
{
int shenfen;//1是主猪 2是忠猪 3是反猪
int life;//剩余体力,初始为4
int first_kill;//杀 首要攻击对象,0表示不杀或杀不到
int first_fight;//决斗 首要攻击对象
int num_kill;//杀 的数量
int num_shan;//闪 的数量
int num_peach;//桃 的数量
int num_cards;//手牌数量
int num_wuxiekeji;//无懈可击 数量
int pig_before;//前一头活着的猪
int pig_next;//下一头活着的猪
int situation;//对于全局的状态 0未知 1是跳忠 2是跳反 3是类反
bool is_it_alive;//死了吗
bool is_it_zhugeliannu;//有没有猪哥连弩
char had_cards[2010];//手牌 从 1 开始
}pigs[11];
int tot_cards,tot_pigs,tot_fanpigs;//卡牌总数,猪总数,存活的反猪数量
int now_top,u=1;
char card[2010];
int winner;//1是主猪胜利 2是反猪胜利
void faqi_kill(int,int);//发起杀
char getcard();//从stdin读入一张牌
void first_in(int);//处理初始状态
bool gameover();//游戏是否结束
void round(int);//rank 的回合
void faqi_kill(int,int);// 发起 杀
void die(int);//有猪彻底死了
char pd_getcard(); //牌堆拿牌
void printans();//输出答案
void faqi_fight(int,int);//发起决斗
void faqi_nanzhuruqin(int); // 发起南猪入侵
void faqi_wanjianqifa(int); // 发起万箭齐发
bool ask_for_wuxiekeji(int,int);//等待响应无懈可击
void find_goal_to_fight(int);//查找决斗对象(反猪不需要)
void find_goal_to_kill(int);//查找杀对象
void near_die(int,int);//濒死状态处理
void near_die(int killer,int sufferer)
{
bool have_peach=false;
if(pigs[sufferer].num_peach>0)
{
register int i;
have_peach=true;
for(i=1;pigs[sufferer].had_cards[i]!='P';i++);
for(i=i+1;i<=pigs[sufferer].num_cards;i++)
pigs[sufferer].had_cards[i-1]=pigs[sufferer].had_cards[i];
pigs[sufferer].num_peach--,pigs[sufferer].num_cards--,++pigs[sufferer].life;
}
if(have_peach==false)
{
die(sufferer);
if(killer==1&&pigs[sufferer].shenfen==2)
{
pigs[1].is_it_zhugeliannu=pigs[1].num_cards=pigs[1].num_kill=pigs[1].num_peach=pigs[1].num_shan=pigs[1].num_wuxiekeji=0;
memset(pigs[1].had_cards,0,sizeof(pigs[1].had_cards));
}
if(pigs[sufferer].shenfen==3)
{
for(register int j=1;j<=3;j++)
{
pigs[killer].had_cards[++pigs[killer].num_cards]=pd_getcard();
if(pigs[killer].had_cards[pigs[killer].num_cards]=='K')
pigs[killer].num_kill++;
else if(pigs[killer].had_cards[pigs[killer].num_cards]=='D')
pigs[killer].num_shan++;
else if(pigs[killer].had_cards[pigs[killer].num_cards]=='P')
pigs[killer].num_peach++;
else if(pigs[killer].had_cards[pigs[killer].num_cards]=='J')
pigs[killer].num_wuxiekeji++;
}
}
}
}
void printans()
{
cout<<(winner==1?"MP":"FP")<<endl;
for(register int i=1;i<=tot_pigs;i++)
{
if(pigs[i].is_it_alive==false)
{
cout<<"DEAD"<<endl;
continue;
}
else if(pigs[i].num_cards>0)
{
for(register int j=1;j<pigs[i].num_cards;j++)
cout<<pigs[i].had_cards[j]<<" ";
cout<<pigs[i].had_cards[pigs[i].num_cards]<<endl;
}
else cout<<endl;
}
}
char pd_getcard()//牌堆拿牌
{
char c=card[now_top];
if(now_top!=1)
now_top--;
return c;
}
char getcard()//从stdin读入一张牌
{
char c=getchar();
for(;c<'A'||c>'Z';c=getchar());
return c;
}
void first_in(int rank)
{
char temp[2];
scanf("%s",temp);
if(temp[0]=='M')
pigs[rank].shenfen=1,pigs[rank].situation=1;
else if(temp[0]=='Z')
pigs[rank].shenfen=2;
else if(temp[0]=='F')
pigs[rank].shenfen=3,pigs[rank].first_fight=1,tot_fanpigs++; //反猪决斗永远找主猪
for(register int i=1;i<=4;i++)
{
pigs[rank].had_cards[i]=getcard();
if(pigs[rank].had_cards[i]=='K')
pigs[rank].num_kill++;
else if(pigs[rank].had_cards[i]=='D')
pigs[rank].num_shan++;
else if(pigs[rank].had_cards[i]=='P')
pigs[rank].num_peach++;
else if(pigs[rank].had_cards[i]=='J')
pigs[rank].num_wuxiekeji++;
}
pigs[rank].num_cards=4,pigs[rank].life=4;
pigs[rank].pig_before=(rank==1?tot_pigs:rank-1);
pigs[rank].pig_next=(rank==tot_pigs?1:rank+1);
pigs[rank].is_it_alive=true;
}
bool gameover()
{
if(tot_fanpigs==0)
{
winner=1;
return true;
}
if(pigs[1].is_it_alive==false)
{
winner=2;
return true;
}
return false;
}
void die(int rank)
{
pigs[rank].is_it_alive=false;
if(rank==1)
winner=2,printans(),exit(0);
if(pigs[rank].shenfen==3)
if(--tot_fanpigs==0)
winner=1,printans(),exit(0);
pigs[pigs[rank].pig_before].pig_next=pigs[rank].pig_next;
pigs[pigs[rank].pig_next].pig_before=pigs[rank].pig_before;
}
void find_goal_to_kill(int rank) //理清打的目标
{
if(pigs[rank].shenfen==2)
pigs[rank].first_kill=(pigs[pigs[rank].pig_next].situation==2?pigs[rank].pig_next:0);
else if(pigs[rank].shenfen==1)
pigs[rank].first_kill=(pigs[pigs[rank].pig_next].situation==2||pigs[pigs[rank].pig_next].situation==3?pigs[rank].pig_next:0);
else if(pigs[rank].shenfen==3)
pigs[rank].first_kill=(pigs[pigs[rank].pig_next].situation==1?pigs[rank].pig_next:0);
}
void find_goal_to_fight(int rank)
{
for(register int i=pigs[rank].pig_next;i!=rank;i=pigs[i].pig_next)
{
if((rank==1&&(pigs[i].situation==2||pigs[i].situation==3))||(pigs[i].situation==2&&pigs[rank].shenfen==2))
{
pigs[rank].first_fight=i;
return;
}
}
pigs[rank].first_fight=0;
}
void round(int rank) //rank的回合
{
for(register int i=1;i<=2;i++)
{
pigs[rank].had_cards[++(pigs[rank].num_cards)]=pd_getcard();
if(pigs[rank].had_cards[pigs[rank].num_cards]=='K')
pigs[rank].num_kill++;
else if(pigs[rank].had_cards[pigs[rank].num_cards]=='D')
pigs[rank].num_shan++;
else if(pigs[rank].had_cards[pigs[rank].num_cards]=='P')
pigs[rank].num_peach++;
else if(pigs[rank].had_cards[pigs[rank].num_cards]=='J')
pigs[rank].num_wuxiekeji++;
}
int sum_kill=0;//没有猪哥连弩就只能杀一次
for(register int i=1;i<=pigs[rank].num_cards&&pigs[rank].num_cards>0;i++)
{
if(pigs[rank].had_cards[i]=='Z')
{
register int j;
for(j=i+1;j<=pigs[rank].num_cards;j++)
pigs[rank].had_cards[j-1]=pigs[rank].had_cards[j];
pigs[rank].num_cards--,pigs[rank].is_it_zhugeliannu=1,i=0;
}
if(pigs[rank].had_cards[i]=='F')
{
if(pigs[rank].shenfen!=3)
find_goal_to_fight(rank);
if(pigs[rank].first_fight!=0)
{
register int j;
for(j=i+1;j<=pigs[rank].num_cards;j++)
pigs[rank].had_cards[j-1]=pigs[rank].had_cards[j];
pigs[rank].num_cards--,faqi_fight(rank,pigs[rank].first_fight),i=0;
if(pigs[rank].is_it_alive==false) return; //重要,如果决斗死了就立即结束回合
}
}
if(pigs[rank].had_cards[i]=='K'&&(sum_kill==0||pigs[rank].is_it_zhugeliannu==1))
{
find_goal_to_kill(rank);
if(pigs[rank].first_kill!=0)
{
register int j;
for(j=i+1;j<=pigs[rank].num_cards;j++)
pigs[rank].had_cards[j-1]=pigs[rank].had_cards[j];
pigs[rank].num_cards--,pigs[rank].num_kill--;
faqi_kill(rank,pigs[rank].first_kill),sum_kill++,i=0;
}
}
if(pigs[rank].had_cards[i]=='P'&&pigs[rank].life<4)
{
register int j;
for(j=i+1;j<=pigs[rank].num_cards;j++)
pigs[rank].had_cards[j-1]=pigs[rank].had_cards[j];
pigs[rank].num_cards--,pigs[rank].num_peach--,pigs[rank].life++,i--;
}
if(pigs[rank].had_cards[i]=='N')
{
register int j;
for(j=i+1;j<=pigs[rank].num_cards;j++)
pigs[rank].had_cards[j-1]=pigs[rank].had_cards[j];
pigs[rank].num_cards--,faqi_nanzhuruqin(rank),i=0;
}
if(pigs[rank].had_cards[i]=='W')
{
register int j;
for(j=i+1;j<=pigs[rank].num_cards;j++)
pigs[rank].had_cards[j-1]=pigs[rank].had_cards[j];
pigs[rank].num_cards--,faqi_wanjianqifa(rank),i=0;
}
}
}
void faqi_fight(int from,int goal)
{
register int i,fi,gi;
if(pigs[from].situation==0||pigs[from].situation==3)
pigs[from].situation=(pigs[goal].situation==1?2:1);
bool can_miss=ask_for_wuxiekeji(from,pigs[goal].situation);
if(can_miss==true) return;
if(pigs[goal].shenfen==2&&from==1) //那么掉血
{
if(--pigs[goal].life<=0)
near_die(from,goal);
return;
}
i=goal;
while(pigs[i].num_kill>0)
{
for(fi=1;fi<=pigs[i].num_cards&&pigs[i].had_cards[fi]!='K';fi++);
for(register int k=fi+1;k<=pigs[i].num_cards;k++)
pigs[i].had_cards[k-1]=pigs[i].had_cards[k];
pigs[i].num_cards--,pigs[i].num_kill--;
i=(i==goal?from:goal);
}
int failer=i,winner_in=(from==failer?goal:from);
if(--pigs[failer].life<=0)
near_die(winner_in,failer);
}
bool ask_for_wuxiekeji(int rank,int situation)
{
if((situation==0)||situation==3)//未表明身份的猪与类反猪不会有猪响应无懈可击
return false;
for(register int i=rank;;i=pigs[i].pig_next)
{
if(pigs[i].num_wuxiekeji>0)
{
if(situation==1&&(pigs[i].shenfen==1||pigs[i].shenfen==2))
{
register int j;
for(j=1;j<=pigs[i].num_cards&&pigs[i].had_cards[j]!='J';j++);
for(j=j+1;j<=pigs[i].num_cards;j++)
pigs[i].had_cards[j-1]=pigs[i].had_cards[j];
pigs[i].num_cards--,pigs[i].num_wuxiekeji--;
if(pigs[i].situation==0||pigs[i].situation==3)
pigs[i].situation=1;
return !ask_for_wuxiekeji(i,2);//向相反身份求无懈可击
}
else if(situation==2&&pigs[i].shenfen==3)
{
register int j;
for(j=1;j<=pigs[i].num_cards&&pigs[i].had_cards[j]!='J';j++);
for(j=j+1;j<=pigs[i].num_cards;j++)
pigs[i].had_cards[j-1]=pigs[i].had_cards[j];
pigs[i].num_cards--,pigs[i].num_wuxiekeji--;
if(pigs[i].situation==0||pigs[i].situation==3)
pigs[i].situation=2;
return !ask_for_wuxiekeji(i,1);//向相反身份求无懈可击
}
}
if(i==pigs[rank].pig_before)//递归边界
return false;
}
}
void faqi_nanzhuruqin(int from)
{
for(register int i=pigs[from].pig_next;i!=from;i=pigs[i].pig_next)
{
bool can_miss=ask_for_wuxiekeji(from,pigs[i].situation);
if(can_miss==true) continue;
if(pigs[i].num_kill>0)
{
register int j;
for(j=1;pigs[i].had_cards[j]!='K';j++);
for(j=j+1;j<=pigs[i].num_cards;j++)
pigs[i].had_cards[j-1]=pigs[i].had_cards[j];
pigs[i].num_cards--,pigs[i].num_kill--;
can_miss=true;
}
if(can_miss==true) continue;
if(i==1&&pigs[from].situation==0)
pigs[from].situation=3;
if(--pigs[i].life<=0)
near_die(from,i);
}
}
void faqi_wanjianqifa(int from)
{
for(register int i=pigs[from].pig_next;i!=from;i=pigs[i].pig_next)
{
bool can_miss=ask_for_wuxiekeji(from,pigs[i].situation);
if(can_miss==true) continue;
if(pigs[i].num_shan>0)
{
register int j;
for(j=1;pigs[i].had_cards[j]!='D';j++);
for(j=j+1;j<=pigs[i].num_cards;j++)
pigs[i].had_cards[j-1]=pigs[i].had_cards[j];
pigs[i].num_cards--,pigs[i].num_shan--;
can_miss=true;
}
if(can_miss==true) continue;
if(i==1&&pigs[from].situation==0)
pigs[from].situation=3;
if(--pigs[i].life<=0)
near_die(from,i);
}
}
void faqi_kill(int from,int goal)//发起 杀
{
register int i;
if(pigs[from].situation==0||pigs[from].situation==3)
pigs[from].situation=(pigs[goal].situation==1?2:1);
if(pigs[goal].num_shan>0)
{
for(i=1;pigs[goal].had_cards[i]!='D';i++);
for(i=i+1;i<=pigs[goal].num_cards;i++)
pigs[goal].had_cards[i-1]=pigs[goal].had_cards[i];
pigs[goal].num_shan--,pigs[goal].num_cards--;
}
else if(--pigs[goal].life<=0)
near_die(from,goal);
}
int main()
{
cin>>tot_pigs>>tot_cards;
now_top=tot_cards;
for(register int i=1;i<=tot_pigs;i++)
pigs[i].num_kill=pigs[i].num_peach=pigs[i].num_shan=pigs[i].num_wuxiekeji=0;
for(register int i=1;i<=tot_pigs;i++)
first_in(i); //初始化每头猪
for(register int i=tot_cards;i>=1;i--)
card[i]=getcard(); //初始化牌堆
while(gameover()==false)
round(u),u=pigs[u].pig_next;
printans();
return 0;
}
```