题解 P2482 【[SDOI2010]猪国杀】
由于最近比较颓，逼自己刷一道大模拟。（其实个人认为这个方法海上挺有用的）
看了这道大模拟后，脑子比较混乱。
先列了一下有用信息（建议认真读，至少读个5遍）：
section 1:
主猪（MP）：自己存活的情况下消灭所有的反猪。
忠猪（ZP）：不惜一切保护主猪，胜利条件与主猪相同。
反猪（AP）：杀死主猪。
section 2:
游戏开始时候，每个玩家手里都会有4张牌，且体力上限和初始体力都是4。
开始游戏时，从主猪开始，按照逆时针方向（数据中就是按照编号从1,2,3..n,1..的顺序）依次行动。
摸牌阶段：从牌堆顶部摸两张牌，依次放到手牌的最右边；
出牌阶段：你可以使用0张到任意张牌，每次使用牌的时候都使用最靠左的能够使用的牌。
当然，要满足如下规则：
1.如果没有猪哥连弩，每个出牌阶段只能使用一次“杀”来攻击；
2.任何牌被使用后被弃置（武器是装备上）；
被弃置的牌以后都不能再用，即与游戏无关；
section 3:
『桃(P)』：在自己的回合内，如果自己的体力值不等于体力上限，那么使用一个桃可以为自己补充一点体力，否则不能使用桃；桃只能对自己使用；在自己的回合外，如果自己的血变为0或者更低，那么也可以使用；
『杀(K)』：在自己的回合内，对攻击范围内除自己以外的一名角色使用。如果没有被『闪』抵消，则造成1点伤害。无论有无武器，杀的攻击范围都是1；
『闪(D)』：当你受到杀的攻击时，可以弃置一张闪来抵消杀的效果；
『决斗(F)』：出牌阶段，对除自己以外任意一名角色使用，由目标角色先开始，自己和目标角色轮流弃置一张杀，首先没有杀可弃的一方受到1点伤害，另一方视为此伤害的来源；
『南猪入侵(N)』：出牌阶段，对除你以外所有角色使用，按逆时针顺序从使用者下家开始依次结算，除非弃置一张杀，否则受到1点伤害；
『万箭齐发(W)』：和南猪入侵类似，不过要弃置的不是杀而是闪；
『无懈可击(J)』：在目标锦囊生效前抵消其效果。每次有一张锦囊即将生效时，从使用这张锦囊的猪开始，按照逆时针顺序，依次得到使用无懈可击的机会；
效果：用于决斗时，决斗无效并弃置；用于南猪入侵或万箭齐发时，当结算到某个角色时才能使用，当前角色不需弃置牌并且不会受到伤害（仅对一个角色产生效果）；用于无懈可击时，成为目标的无懈可击被无效。
『猪哥连弩(Z)』：武器，攻击范围1，出牌阶段你可以使用任意张杀；
同一时刻最多只能装一个武器；如果先前已经有了一把武器，那么之后再装武器的话，会弃置以前的武器来装现在的武器；
section 4:
伤害来源：杀、南猪入侵、万箭齐发的伤害来源均是使用该牌的猪，决斗的伤害来源如上；
距离：两只猪的距离定义为沿着逆时针方向间隔的猪数＋1。即初始时1和2的距离为1，但是2和1的距离就是n-1。注意一个角色的死亡会导致一些猪距离的改变；
玩家死亡：如果该玩家的体力降到0或者更低，并且自己手中没有足够的桃使得自己的体力值回到1，那么就死亡了，死亡后所有的牌（装备区，手牌区）被弃置；
奖励与惩罚：反猪死亡时，最后一个伤害来源处（即使是反猪）立即摸三张牌。忠猪死亡时，如果最后一个伤害来源是主猪，那么主猪所有装备牌、手牌被弃置；
注意，一旦达成胜利条件，游戏立刻结束，因此即使会摸3张牌或者还有牌可以用也不用执行了。
section 5:
已经知道每只猪的角色、手牌，还有牌堆初始情况，并且假设每个角色会按照如下的行为准则进行游戏。
section 6:
献殷勤：使用无懈可击挡下南猪入侵、万箭齐发、决斗；使用无懈可击抵消表敌意；
表敌意：对某个角色使用杀、决斗；使用无懈可击抵消献殷勤；
跳忠：即通过行动表示自己是忠猪。跳忠行动就是对主猪或对某只已经跳忠的猪献殷勤，或者对某只已经跳反的猪表敌意；
跳反：即通过行动表示自己是反猪。跳反行动就是对主猪或对某只已经跳忠的猪表敌意，或者对某只已经跳反的猪献殷勤；
忠猪不会跳反，反猪也不会跳忠；不管是忠猪还是反猪，能够跳必然跳；
section 7:
行动准则（共性）：每个角色如果手里有桃且生命值未满，那么必然吃掉；有南猪入侵、万箭齐发、必然使用；有装备必然装上；受到杀时，有闪必然弃置；响应南猪入侵或者万箭齐发时候，有杀/闪必然弃置；不会对未表明身份的猪献殷勤（包括自己）；
section 8:
主猪：主猪会认为，没有跳身份且用南猪入侵/万箭齐发对自己造成伤害的猪是“类反猪”（没伤害到不算，注意“类反猪”并没有表明身份），如果之后跳了，那么主猪会重新认识这只猪；对于每种表敌意的方式，对逆时针方向能够执行到的第一只“类反猪”或者已跳反猪表；如果没有，那么就不表敌意；决斗时会不遗余力弃置杀；如果能对已经跳忠的猪或自己献殷勤，那么一定献；如果能够对已经跳反的猪表敌意，那么一定表；
忠猪：对于每种表敌意的方式，对逆时针方向能够执行到的第一只已经跳反的猪表，如果没有，那么就不表敌意；决斗时，如果对方是主猪，那么不会弃置杀，否则，会不遗余力弃置杀；如果有机会对主猪或者已经跳忠的猪献殷勤，那么一定献；
反猪：对于每种表敌意的方式，如果有机会则对主猪表，否则，对逆时针方向能够执行到的第一只已经跳忠的猪表，如果没有，那么就不表敌意；决斗时会不遗余力弃置杀；如果有机会对已经跳反的猪献殷勤，那么一定献；
好吧，其实都是挺有用的，即使已经玩过（甚至熟知）三国杀，也需要非常仔细的看懂，看清题目。
我还是一步一步来考虑的。
先看没有锦囊牌的情况。
在自己回合内，有武器当然是装上。闪一定是在非自己回合出的。桃的话血没有满就吃，杀的话能杀就杀，但是要找清目标（必须距离为1）。
所谓找清目标，就是——反贼找主公或表明身份的忠臣，忠臣找已经表明身份的反贼，主公找已经表明身份的反贼或类反贼。
这应该是最简单的部分了。但是我WA了一两次才拿到10分。
错因有：
1.没有完全找清目标；
2.装上诸葛连弩后，没有发现前面的杀也能用；
那么继续，向30分发起冲击。
30分的要求是——有锦囊牌，但是没有无懈可击。好吧，我得承认，没有无懈可击也要写很久。
首先，决斗。还是要找清目标——反贼决斗目标一定是主公，忠臣决斗目标一定是表明身份的反贼，主公决斗目标是表明身份的反贼或类反贼。
然后是万箭齐发和南蛮入侵。这是个多重目标攻击，所以要对每一个存活的非攻击发起者发起一次单向进攻。
这个部分需要注意很多：
3.决斗时，进攻发起者可以要使用多张杀，所以要处理好决斗后，手牌剩余部分；
4.决斗时，可能进攻发起者会GG（不知道他怎么想的，不愧是pig），此时要停止他的回合；
5.万箭齐发（南蛮入侵）时，可能会有多人GG，可能会摸多次牌；
6.万箭齐发（南蛮入侵）时，可能会有多人GG，同时发动者是主公，不仅杀死了忠臣，也杀死了反贼，此时也要考虑弃掉所有手牌和摸三张牌的顺序；
7.决斗时，主公认为对面是类反贼，实际上是忠臣，忠臣要牺牲一滴血；
8.在决斗时，发起者会明确身份；在万箭齐发（南蛮入侵）时，可能并不会，但有可能成为类反贼；
30分的段也WA个不停，但总算还是达到了。
剩下就是无懈可击了。
这是一个难点，但我认为，要突破它，首先要搞清无懈在不同情况下了作用，还有——它一定在锦囊牌生效之前使用。
题目中定义，如果某人使用了一张锦囊牌，那么从他后面的猪开始，依次有出无懈的机会（当然对于一张锦囊牌，最多只有1张无懈针对他本身）。
那么，假如A对B出了一张锦囊牌，首先，需要保证B的身份已经亮明（否则没有人会帮他，包括他自己）
然后，和B一派的，一定想方设法使初始锦囊牌无效；和B不一派的，一定想方设法使初始锦囊牌生效。
那么，这可以写个简易的dfs（顺便在过程中，如果能且有必要出无懈，就直接出掉了）。
然后，无懈不可能当做第一张锦囊牌打出（相当于永远是后手）。
对于无懈而言，需要注意的地方：
9.无懈不可能先手打出，并不代表在自己回合内就不用出无懈；
10.无懈的优先级很高（比一般锦囊牌都高）；
11.当一个人使用了无懈，他的身份就完全表明了；
12.无懈看似是最复杂，但是实际上相当于一个补丁（尽管有挺多的细节）；
以上是大致的做法，从10pts->30pts->100pts，而实际上，我爆出了形形色色的部分分（等下会展示）
下面还有一些全局的注意点：
13.主公杀死忠臣，一定要把装备给弃了；
14.关于一轮能否出多次杀，要注意判断；
15.一张牌，你出了，就相当于弃置了，不管最后是否生效；
16.最形象的方法存手牌显然是链表，但考虑到实际需要，一般直接开数组；
17.要分清在自己的回合出牌和在别人的回合出牌，最好用不同方法处理，但处理也有很多细节（因人而异）；
18.注意主公也会对类反贼表敌意；
19.杀，桃，无懈都是有可能在自己回合打出的“响应牌”（就是回击别人的牌），要注意处理方法（要看清是自己回合还是他人回合出的牌）；
20.严格意义上，除了“桃”，在自己回合出了每一张牌后，可能会激活这张牌前面的牌；
21.注意这里的距离是单向的，而不是双向的，而且恒为1；
22.存在用无懈无懈掉自己的锦囊牌的情况；
23.阵亡的人已经没有任何价值，直接跳过他；
24.一旦出现胜利局面，就要停止一切操作，但是需要把没有整理好的手牌整理好；
25.对于一个人，要是把手牌扫了一遍，没有出任何牌，就结束出牌；
26.一个人死了后，即使更新上一个玩家的下一个玩家nxt（不必o1求）；
27.注意一个人处于濒死状态的处理，没当有一个人死了，都要判断一下游戏是否结束了；
28.题目有一个小bug，当牌堆没有牌时，要一直摸最后一张牌。
这是我认为这题存在的细节（可能还有我数不过来了），这些细节有些是比较重要的，有些是要看写法的。
对于这一题我也有一些自己的看法——
这题其实很好，大量的代码，条件和情况能锻炼一个人的代码水平和思维能力。尽管有些方面不是特别好（比如出在了省选里面，估计没有什么人能打完并AC）。
然后我发现在luogu里面，这题的分类有一个AOE。为什么标AOE？有些人说因为南蛮和万箭是群体攻击。
我并不是这样认为的（当然也有可能我理解错了）——
因为这个题目依赖于主公亮明了身份。这个条件不是必要的，而是极其必要的。
因为，除主公外任意一个人要表明身份，必须要攻击一个以表明身份的人，这就构成了一个DAG（其实也是一颗树）。
这个DAG就是AOE网。
还有，我只是写了“三国杀”里的很小的一部分就出了这么多bug，如果是真正的三国杀，那真是无法可想。。
code:
#include<bits/stdc++.h>
using namespace std;
const bool diff[3][3]={{0,0,1},{0,0,1},{1,1,0}};
const int M=2005;
int n,m,fanzhu,deadfan,rounds,tmp[M],used[M]; char ch,cu;
struct PIGS {int iden,bloods,perfo,dead,nxt,equip,cnt; char cards[M];}a[15];
deque <char> cards_pile;
void _file() {
freopen("pigs.in","r",stdin);
freopen("pigs.out","w",stdout);
}
inline char read() {
ch=getchar();
while (ch<'A'||ch>'Z') ch=getchar();
return ch;
}
void _init() {
scanf("%d%d",&n,&m),fanzhu=deadfan=0;
for (int i=1,las=0; i<=n; i++) {
a[i].bloods=a[i].cnt=4,a[i].dead=a[i].perfo=a[i].equip=0,a[i].nxt=i%n+1;
cu=read(),fanzhu+=(cu=='F'),a[i].iden=(cu!='F')?((cu!='Z')?0:1):2,cu=read();
for (int j=1; j<=4; j++) a[i].cards[j]=read();
}
a[1].perfo=1;
for (int i=1; i<=m; i++) cards_pile.push_back(read());
}
void get_cards(int cur) {
a[cur].cards[++a[cur].cnt]=cards_pile.front();
if (cards_pile.size()>1) cards_pile.pop_front();
}
bool ought(int cur) {
int nxt=a[cur].nxt;
if (a[nxt].perfo==0) return 0; else
if (a[nxt].perfo==1) return diff[a[cur].iden][a[nxt].iden];
else return a[cur].iden==0;
}
int atk(int cur) {
if (a[cur].iden==2) return 1;
for (int nxt=a[cur].nxt; nxt!=cur; nxt=a[nxt].nxt) if (!a[nxt].dead)
if ((a[nxt].iden==2&&a[nxt].perfo==1)||(a[cur].iden==0&&a[nxt].perfo==-1)) return nxt;
return -1;
}
void pend(int x,int y) {
if (a[x].iden==0&&a[y].iden==1) {
for (int i=1; i<=a[x].cnt; i++) used[i]=rounds; a[x].equip=0;
}
else if (a[y].iden==2) get_cards(x),get_cards(x),get_cards(x);
}
int find(int cur,char aim) {
for (int i=1; i<=a[cur].cnt; i++) if (a[cur].cards[i]==aim) return i;
return 0;
}
void adjust(int cur,int s,int t) {
for (int i=s; i<t; i++) a[cur].cards[i]=a[cur].cards[i+1];
}
void respond_peach(int cur,int user) {
int re=find(cur,'P');
if (cur==user) {
re=0;
for (int i=1; i<=a[cur].cnt; i++) if (used[i]!=rounds&&a[cur].cards[i]=='P') {re=i; break;}
if (re) used[re]=rounds,a[cur].bloods++;
return;
}
if (re) a[cur].bloods++,adjust(cur,re,a[cur].cnt),a[cur].cnt--;
}
bool respond_dodge(int cur) {
int re=find(cur,'D');
if (re) adjust(cur,re,a[cur].cnt),a[cur].cnt--;
return re;
}
bool respond_kill(int cur,int user) {
int re=find(cur,'K');
if (cur==user) {
re=0;
for (int i=1; i<=a[cur].cnt; i++) if (used[i]!=rounds&&a[cur].cards[i]=='K') {re=i; break;}
if (re) used[re]=rounds;
return re;
}
if (re) adjust(cur,re,a[cur].cnt),a[cur].cnt--;
return re;
}
bool respond_wuxie(int cur,int user) {
int re=find(cur,'J');
if (cur==user) {
re=0;
for (int i=1; i<=a[cur].cnt; i++) if (used[i]!=rounds&&a[cur].cards[i]=='J') {re=i; break;}
if (re) used[re]=rounds;
return re;
}
if (re) adjust(cur,re,a[cur].cnt),a[cur].cnt--;
return re;
}
void lose_blood(int cur,int user) {
a[cur].bloods--; if (a[cur].bloods<1) respond_peach(cur,user);
}
void change_link(int cur) {
for (int pre=1; pre<=n; pre++)
if (!a[pre].dead&&a[pre].nxt==cur) {a[pre].nxt=a[cur].nxt; break;}
}
void do_peach(int cur) {
a[cur].bloods++;
}
void do_kill(int cur) {
int nxt=a[cur].nxt;
a[cur].perfo=1;
if (!respond_dodge(nxt)) {
lose_blood(nxt,cur);
if (a[nxt].bloods<1) deadfan+=(a[nxt].iden==2),a[nxt].dead=1,a[cur].nxt=a[nxt].nxt;
if (fanzhu==deadfan||a[1].dead) return;
if (a[nxt].bloods<1) pend(cur,nxt);
}
}
bool do_wuxie(int user,int cur,int aim,int now) {
bool ret=now;
for (int nxt=cur; ; ) if (!a[nxt].dead) {
if (!now) {
if (!diff[a[nxt].iden][a[aim].iden])
if (respond_wuxie(nxt,user)) {a[nxt].perfo=1; return do_wuxie(user,nxt,aim,1-now);}
}else {
if (diff[a[nxt].iden][a[aim].iden])
if (respond_wuxie(nxt,user)) {a[nxt].perfo=1; return do_wuxie(user,nxt,aim,1-now);}
}
nxt=a[nxt].nxt; if (nxt==cur) break;
}
return ret;
}
void do_fight(int cur,int aim,int user) {
a[cur].perfo=1;
if (a[aim].perfo==1) {
if (do_wuxie(cur,cur,aim,0)) return;
}
for (; ;) {
if (a[cur].iden==0&&a[aim].iden==1) {
lose_blood(aim,user);
if (a[aim].bloods<1) deadfan+=(a[aim].iden==2),a[aim].dead=1,change_link(aim);
if (fanzhu==deadfan||a[1].dead) return;
if (a[aim].bloods<1) pend(cur,aim);
return;
}else
if (!respond_kill(aim,user)) {
lose_blood(aim,user);
if (a[aim].bloods<1) deadfan+=(a[aim].iden==2),a[aim].dead=1,change_link(aim);
if (fanzhu==deadfan||a[1].dead) return;
if (a[aim].bloods<1) pend(cur,aim);
return;
}
if (!respond_kill(cur,user)) {
lose_blood(cur,user);
if (a[cur].bloods<1) deadfan+=(a[cur].iden==2),a[cur].dead=1,change_link(cur);
if (fanzhu==deadfan||a[1].dead) return;
if (a[cur].bloods<1) pend(aim,cur);
return;
}
}
}
void do_nanzhu(int cur) {
for (int nxt=a[cur].nxt; nxt!=cur; nxt=a[nxt].nxt) if (!a[nxt].dead) {
if (a[nxt].perfo==1) {
if (do_wuxie(cur,cur,nxt,0)) continue;
}
if (!respond_kill(nxt,cur)) {
lose_blood(nxt,cur); if (nxt==1&&a[cur].perfo==0) a[cur].perfo=-1;
if (a[nxt].bloods<1) deadfan+=(a[nxt].iden==2),a[nxt].dead=1,change_link(nxt);
if (fanzhu==deadfan||a[1].dead) return;
if (a[nxt].bloods<1) pend(cur,nxt);
}
}
}
void do_wanjian(int cur) {
for (int nxt=a[cur].nxt; nxt!=cur; nxt=a[nxt].nxt) if (!a[nxt].dead) {
if (a[nxt].perfo==1) {
if (do_wuxie(cur,cur,nxt,0)) continue;
}
if (!respond_dodge(nxt)) {
lose_blood(nxt,cur); if (nxt==1&&a[cur].perfo==0) a[cur].perfo=-1;
if (a[nxt].bloods<1) deadfan+=(a[nxt].iden==2),a[nxt].dead=1,change_link(nxt);
if (fanzhu==deadfan||a[1].dead) return;
if (a[nxt].bloods<1) pend(cur,nxt);
}
}
}
void do_zhuge(int cur) {
a[cur].equip=1;
}
bool dis_cards(int cur) {
memset(used,0,sizeof used);
int i,cntused,totkill=0,counts,ret=-1,aim; char now;
for (rounds=1; ; rounds++) {
cntused=counts=0;
for (i=1; i<=a[cur].cnt; i++) if (used[i]!=rounds) {
now=a[cur].cards[i];
switch (now) {
case 'P':
if (a[cur].bloods<4) do_peach(cur),used[i]=rounds,cntused++,i=a[cur].cnt;
break;
case 'K':
if ((!totkill||a[cur].equip)&&ought(cur)) do_kill(cur),used[i]=rounds,cntused++,totkill++,i=a[cur].cnt;
break;
case 'F':
aim=atk(cur); if (aim!=-1) do_fight(cur,aim,cur),used[i]=rounds,cntused++,i=a[cur].cnt;
break;
case 'N':
do_nanzhu(cur),used[i]=rounds,cntused++,i=a[cur].cnt;
break;
case 'W':
do_wanjian(cur),used[i]=rounds,cntused++,i=a[cur].cnt;
break;
case 'Z':
do_zhuge(cur),used[i]=rounds,cntused++,i=a[cur].cnt;
break;
default:
break;
}
if (fanzhu==deadfan||a[1].dead) {ret=1; break;}
if (a[cur].dead) {ret=0; break;}
}
for (int i=1; i<=a[cur].cnt; i++) if (used[i]!=rounds) tmp[++counts]=a[cur].cards[i];
for (int i=1; i<=counts; i++) a[cur].cards[i]=tmp[i]; a[cur].cnt=counts;
if (!cntused&&ret!=1) ret=0;
if (ret>-1) return ret;
}
}
bool playing(int cur) {
get_cards(cur),get_cards(cur);
return dis_cards(cur);
}
void _duel() {
for (int i=1,event=0; !event&&fanzhu>0; i=a[i].nxt) if (!a[i].dead) event=playing(i);
}
void _print() {
printf("%s\n",a[1].dead?"FP":"MP");
for (int i=1; i<=n; i++) {
if (a[i].dead) printf("%s","DEAD"); else {
if (a[i].cnt>0) printf("%c",a[i].cards[1]);
for (int j=2; j<=a[i].cnt; j++) printf(" %c",a[i].cards[j]);
}
puts("");
}
}
int main() {
_init();
_duel();
_print();
return 0;
}