NanoApe's Blog

既是咸鱼又是辣鸡

BZOJ 1972: [SDOI2010]猪国杀

NanoApe posted @ 2015年12月20日 02:23 in 蒟蒻整天被神题虐哭 , 587 阅读

BZOJ恶心模拟题之一

做完感觉比杀蚂蚁要难得多(杀蚂蚁至少还有跟你说各个步骤的次序是怎么样的。。。

先给一份好看点的题目描述:

 

《猪国杀》是一种多猪牌类回合制游戏,一共有三种角色:主猪,忠猪,反猪。
每局游戏主猪有且只有一只,忠猪和反猪可以有多只,每只猪扮演一种角色。 


游戏目的:

主猪(MP):自己存活的情况下消灭所有的反猪。 
忠猪(ZP):不惜一切保护主猪,胜利条件与主猪相同。 
反猪(AP):杀死主猪。 


游戏过程:

游戏开始时候,每个玩家手里都会有4张牌,且体力上限和初始体力都是4。 
开始游戏时,从主猪开始,按照逆时针方向(数据中就是按照编号从1,2,3..n,1..的顺序)依次行动。
每个玩家自己的回合可以分为4个阶段: 
◎摸牌阶段:从牌堆顶部摸两张牌,依次放到手牌的最右边; 
◎出牌阶段:你可以使用0张到任意张牌,每次使用牌的时候都使用最靠左的能够使用的牌。当然,要满足如下规则:
  1. 如果没有猪哥连弩,每个出牌阶段只能使用一次“杀”来攻击;
  2. 任何牌被使用后被弃置(武器是装备上); 被弃置的牌以后都不能再用,即与游戏无关; 

各种牌介绍:

每张手牌用一个字母表示,字母代表牌的种类。 

◎基本牌: 
『桃(P)』:
在自己的回合内,如果自己的体力值不等于体力上限,那么使用一个桃可以为自己补充一点体力,否则不能使用桃;
桃只能对自己使用
在自己的回合外,如果自己的血变为0或者更低,那么也可以使用;

『杀(K)』:
在自己的回合内,对攻击范围内除自己以外的一名角色使用。
如果没有被『闪』抵消,则造成1点伤害。
无论有无武器,杀的攻击范围都是1;

『闪(D)』:
当你受到杀的攻击时,可以弃置一张闪来抵消杀的效果; 

◎锦囊牌: 
『决斗(F)』:
出牌阶段,对除自己以外任意一名角色使用,由目标角色先开始,自己和目标角色轮流弃置一张杀,首先没有杀可弃的一方受到1点伤害,另一方视为此伤害的来源;

『南猪入侵(N)』:
出牌阶段,对除你以外所有角色使用,按逆时针顺序从使用者下家开始依次结算,除非弃置一张杀,否则受到1点伤害;

『万箭齐发(W)』:
和南猪入侵类似,不过要弃置的不是杀而是闪;

『无懈可击(J)』:
在目标锦囊生效前抵消其效果。
每次有一张锦囊即将生效时,从使用这张锦囊的猪开始,按照逆时针顺序,依次得到使用无懈可击的机会;
效果:
用于决斗时,决斗无效并弃置;
用于南猪入侵或万箭齐发时,当结算到某个角色时才能使用,当前角色不需弃置牌并且不会受到伤害(仅对一个角色产生效果);
用于无懈可击时,成为目标的无懈可击被无效。 

◎装备牌: 
『猪哥连弩(Z)』:
武器,出牌阶段你可以使用任意张杀;
同一时刻最多只能装一个武器;
如果先前已经有了一把武器,那么之后再装武器的话,会弃置以前的武器来装现在的武器; 

特殊事件及概念解释

◎伤害来源:
杀、南猪入侵、万箭齐发的伤害来源均是使用该牌的猪,决斗的伤害来源如上;

距离
两只猪的距离定义为沿着逆时针方向间隔的猪数+1。
即初始时1和2的距离为1,但是2和1的距离就是n-1。
注意一个角色的死亡会导致一些猪距离的改变;

◎玩家死亡:
如果该玩家的体力降到0或者更低,并且自己手中没有足够的桃使得自己的体力值回到1,那么就死亡了,死亡后所有的牌(装备区,手牌区)被弃置;

◎奖励与惩罚:
反猪死亡时,最后一个伤害来源处(即使是反猪)立即摸三张牌。
忠猪死亡时,如果最后一个伤害来源是主猪,那么主猪所有装备牌、手牌被弃置;
 
◎注意,一旦达成胜利条件,游戏立刻结束,因此即使会摸3张牌或者还有牌可以用也不用执行了。
 
几种行为
 
◎献殷勤:
使用无懈可击挡下南猪入侵、万箭齐发、决斗;
使用无懈可击抵消表敌意;
 
 
◎表敌意:
对某个角色使用杀、决斗;
使用无懈可击抵消献殷勤;

◎跳忠:
即通过行动表示自己是忠猪。
跳忠行动就是对主猪或对某只已经跳忠的猪献殷勤,或者对某只已经跳反的猪表敌意;

◎跳反:
即通过行动表示自己是反猪。
跳反行动就是对主猪或对某只已经跳忠的猪表敌意,或者对某只已经跳反的猪献殷勤;
 
忠猪不会跳反,反猪也不会跳忠;
不管是忠猪还是反猪,能够跳必然跳;
 
行动准则
 
共性:
每个角色如果手里有桃且生命值未满,那么必然吃掉;
有南猪入侵、万箭齐发、必然使用;
有装备必然装上;
受到杀时,有闪必然弃置;
响应南猪入侵或者万箭齐发时候,有杀/闪必然弃置;
不会对未表明身份的猪献殷勤(包括自己);
 
特性:
◎主猪:
主猪会认为没有跳身份,且用南猪入侵/万箭齐发对自己造成伤害的猪是“类反猪”(没伤害到不算,注意“类反猪”并没有表明身份),如果之后跳了,那么主猪会重新认识这只猪;
对于每种表敌意的方式,对逆时针方向能够执行到的第一只“类反猪”或者已跳反猪表,如果没有,那么就不表敌意;
决斗时会不遗余力弃置杀;
如果能对已经跳忠的猪或自己献殷勤,那么一定献;
如果能够对已经跳反的猪表敌意,那么一定表; 
 
◎忠猪:
对于每种表敌意的方式,对逆时针方向能够执行到的第一只已经跳反的猪表,如果没有,那么就不表敌意;
决斗时,如果对方是主猪,那么不会弃置杀,否则,会不遗余力弃置杀;
如果有机会对主猪或者已经跳忠的猪献殷勤,那么一定献;

◎反猪:
对于每种表敌意的方式,如果有机会则对主猪表,否则,对逆时针方向能够执行到的第一只已经跳忠的猪表,如果没有,那么就不表敌意;
决斗时会不遗余力弃置杀;
如果有机会对已经跳反的猪献殷勤,那么一定献。
 
行动准则Hzw的提醒(摘取)
 

1.此题注意样例少了个J,且牌堆可能用完牌,若牌用完则不停取最后一张

3.注意弃牌要弃装备

4.注意各种操作跳过已死的人

5.如果一个人打出无懈可击,则从他开始询问是否无懈无懈可击

8.对他人决斗可能导致自己死亡,要及时终止出牌阶段

 

嗯这题数据很大,不适宜跑数据检查错,对拍算是一种不错的选择

MyCode:

#include <cstdio>
#include <queue>

#define rep(i, l, r) for(int i=l; i<=r; i++)
#define down(i, l, r) for(int i=l; i>=r; i--)
#define clr(x, c) memset(x, c, sizeof(x))
#define maxn 19
#define maxm 209

using namespace std;

int P_Num, P_Fz, C_Rest, Id[maxn], IdNow[maxn], Hp[maxn], Nx[maxn], Pr[maxn], Now, WhoKill;
int Card[maxn][maxm], Sz[maxn];
bool Dead[maxn], Gameover, Zg[maxn];
queue<int>Rest; int RestEnd;


char ch; inline void Get(){ch=0; while (ch<'A' || ch>'Z') ch=getchar(); getchar();}
inline int GetId()
{
	Get();
	if (ch=='M') return 1;
	if (ch=='Z') return 2;
	if (ch=='F') return 3;
	return -1;
}
inline int GetCard()
{
	Get();
	if (ch=='P') return 1;
	if (ch=='K') return 2;
	if (ch=='D') return 3;
	if (ch=='F') return 4;
	if (ch=='N') return 5;
	if (ch=='W') return 6;
	if (ch=='J') return 7;
	if (ch=='Z') return 8;
	return -1;
}
inline char Change(int x)
{
	if (x==1) return 'P';
	if (x==2) return 'K';
	if (x==3) return 'D';
	if (x==4) return 'F';
	if (x==5) return 'N';
	if (x==6) return 'W';
	if (x==7) return 'J';
	if (x==8) return 'Z';
	return '9';
}



inline void PutoutCard(int x)
{
	rep(i, 1, Sz[x]) printf("%d ", Card[x][i]);
	puts("");
}



inline void DelCard(int x, int Use){Sz[x]--; rep(i,Use,Sz[x])Card[x][i]=Card[x][i+1];}
inline void AddCard(int x)
{
	if (Rest.empty()) 
		Card[x][++Sz[x]]=RestEnd;
	else
		Card[x][++Sz[x]]=Rest.front(), Rest.pop(); 
}
inline void Over(int x)
{
	if (x==1) puts("FP"); else puts("MP");
	rep(o, 1, P_Num)
	{
		if (Dead[o]) {puts("DEAD"); continue;}
		rep(i, 1, Sz[o]) printf("%c%c", Change(Card[o][i]), (i==Sz[o])?'\n':' ');
		if (Sz[o]==0) puts("");
	}
	Gameover=true;
}
inline bool Save(int x)
{
	while (Hp[x]<=0)
	{
		bool Use=false;
		rep(i, 1, Sz[x]) if (Card[x][i]==1) {Hp[x]++; DelCard(x,i); Use=true; break;}
		if (!Use) break;
	}
	return Hp[x]>0;
}
inline void Die(int &x)
{
	int tmp_x=Pr[x];
	
	Dead[x]=1; if (Id[x]==3) P_Fz--;
	Nx[Pr[x]]=Nx[x];
	Pr[Nx[x]]=Pr[x];
	
	if (Id[x]==1) Over(1);
	if (P_Fz==0) Over(2);
	if (Gameover) return;
	
	if (Id[x]==3) {AddCard(WhoKill); AddCard(WhoKill); AddCard(WhoKill);}
	if (Id[x]==2 && WhoKill==1) Sz[1]=0, Zg[1]=false;
	
	x=tmp_x;
}
inline void ARedFlower(int x, int y)
{
	if (Id[x]==2 && (Id[y]==1 || IdNow[y]==2)) IdNow[x]=2;
	if (Id[x]==3 && IdNow[y]==3) IdNow[x]=3;
}
inline void DiuLeiLouMou(int x, int y)
{
	if (Id[x]==3 && (Id[y]==1 || IdNow[y]==2)) IdNow[x]=3;
	if (Id[x]==2 && IdNow[y]==3) IdNow[x]=2;
}
inline bool Will(int x, int y, int type)
{
	if (type==0 && (Id[x]==1 || Id[x]==2) && (IdNow[y]==2 || IdNow[y]==1)) return 1;
	if (type==0 && Id[x]==3 && IdNow[y]==3) return 1;
	if (type==1 && (Id[x]==1 || Id[x]==2) && IdNow[y]==3) return 1;
	if (type==1 && Id[x]==3 && (IdNow[y]==2 || IdNow[y]==1)) return 1;
	return 0;
}
bool AskCancel(int x, int y, int type)
{
	int tmp=x; while (true)
	{
		if (Will(tmp,y,type))
		{
			rep(i, 1, Sz[tmp]) if (Card[tmp][i]==7) 
			{
				DelCard(tmp,i);
				if (type==0) ARedFlower(tmp,y); else DiuLeiLouMou(tmp,y);
				if (!AskCancel(tmp,y,type^1)) 
					return true; 
				else 
					return false;
			}
		}
		tmp=Nx[tmp]; if (tmp==x) break;
	}
	return false;
}
inline void Kill(int x, int y)
{
	DiuLeiLouMou(x,y);
	
	rep(i, 1, Sz[y]) if (Card[y][i]==3) {DelCard(y,i); return;}

	Hp[y]--; WhoKill=x;
	if (Hp[y]<=0 && !Save(y)) Die(y);
}
inline void Fight(int x, int y)
{
	DiuLeiLouMou(x,y);
	if (AskCancel(x,y,0)) return;
	
	while (true)
	{
		if (Id[x]==1 && Id[y]==2) break;
		
		bool Use=false;
		rep(i, 1, Sz[y]) if (Card[y][i]==2) {DelCard(y,i); Use=true; break;}
		if (Use==false) break;
		
		swap(x,y);
	}
	
	Hp[y]--; WhoKill=x;
	if (Hp[y]<=0 && !Save(y)) Die(y);
}
inline void KingShit(int x)
{
	for(int tmp=Nx[x]; tmp!=x; tmp=Nx[tmp]) if (!AskCancel(x,tmp,0))
	{
		bool Use=false;
		rep(i, 1, Sz[tmp]) if (Card[tmp][i]==2) {DelCard(tmp,i); Use=true; break;}
		if (Use==true) continue;
		
		if (Id[tmp]==1 && IdNow[x]==0) IdNow[x]=-1;
		Hp[tmp]--; WhoKill=x;
		if (Hp[tmp]<=0 && !Save(tmp)) Die(tmp);
		if (Gameover) return;
	}
}
inline void KingTreasure(int x)
{
	for(int tmp=Nx[x]; tmp!=x; tmp=Nx[tmp]) if (!AskCancel(x,tmp,0))
	{
		bool Use=false;
		rep(i, 1, Sz[tmp]) if (Card[tmp][i]==3) {DelCard(tmp,i); Use=true; break;}
		if (Use==true) continue;
		
		if (Id[tmp]==1 && IdNow[x]==0) IdNow[x]=-1;
		Hp[tmp]--; WhoKill=x;
		if (Hp[tmp]<=0 && !Save(tmp)) Die(tmp);
		if (Gameover) return;
	}
}
inline bool WillKill(int type, int x)
{
	if (type==1) return IdNow[x]==-1 || IdNow[x]==3;
	if (type==2) return IdNow[x]==3;
	if (type==3) return IdNow[x]==1 || IdNow[x]==2;
	return false;
}



int main()
{
	scanf("%d%d", &P_Num, &C_Rest);
	rep(i, 1, P_Num) 
	{
		Id[i]=GetId(); Hp[i]=4; if (Id[i]==3) P_Fz++;
		rep(j, 1, 4) Card[i][++Sz[i]]=GetCard();
	}
	rep(i, 1, C_Rest) Rest.push(RestEnd=GetCard());
	IdNow[1]=1;
	rep(i, 1, P_Num-1) Nx[i]=i+1; Nx[P_Num]=1;
	rep(i, 2, P_Num) Pr[i]=i-1; Pr[1]=P_Num;
	
	Now=1;
	while (true)
	{
		AddCard(Now); AddCard(Now); int KillTime=0;
		
		while (true)
		{
			//PutoutCard(Now);
			
			bool Use=false; rep(i, 1, Sz[Now])
			{
				if (Card[Now][i]==1 && Hp[Now]<4) 
				{
					DelCard(Now,i); Hp[Now]++;
					Use=true; break;
				}
				if (Card[Now][i]==2 && WillKill(Id[Now],Nx[Now]) && (KillTime<1 || Zg[Now])) 
				{
					DelCard(Now,i); Kill(Now,Nx[Now]); KillTime++;
					if (Gameover) return 0;
					Use=true; break;
				}
				if (Card[Now][i]==4) 
				{
					int tmp=Nx[Now]; while (tmp!=Now && !WillKill(Id[Now],tmp)) tmp=Nx[tmp]; if (tmp==Now) continue;
					if (Id[Now]==3) tmp=1;
					DelCard(Now,i); Fight(Now,tmp);
					if (Gameover) return 0;
					if (Hp[Now]<=0) break;
					Use=true; break;
				}
				if (Card[Now][i]==5) 
				{
					DelCard(Now,i); KingShit(Now);
					if (Gameover) return 0;
					Use=true; break;
				}
				if (Card[Now][i]==6)
				{
					DelCard(Now,i); KingTreasure(Now);
					if (Gameover) return 0;
					Use=true; break;
				}
				if (Card[Now][i]==8) 
				{
					DelCard(Now,i); Zg[Now]=true; 
					Use=true; break;
				}
			}
			if (Use==0) break;
		}
		
		//弃牌阶段
		Now=Nx[Now];
	}
	return 0;
}

这题能1A的人简直是神。。。

做这道题我被vector的erase坑,被题目各种坑点坑,前前后后改了得有10次吧QwQ

妈蛋


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter