题解 P2482 【[SDOI2010]猪国杀】
ecnerwaIa
·
·
题解
此题居然没有<=100行代码的题解？我来发一波
（注：码风仅供娱乐向，请勿学习这种码风！！！）
（另注：之前貌似因为AFO所以导致有些错误没能处理，请谅解）
首先此题坑点很多，而我本人语文不好，多次理解错题意，导致交了一面才AC（理清思路后还是能做到300行内的）
-
首先关于题目说的什么牌够用？哪里够用了...明明会RE两个点，所以不够用的时候一直拿最后一张牌（反人类）
-
巨吓人的递归无懈...A无懈掉B对C无懈掉D无懈掉E对....这里其实判断也很好判断，假设一开始我们x的锦囊生效前,我们需要帮他无懈,此时默认x是受害者，那么y帮x，y和x就是一边的,z无懈y,z和x就是敌人，那么我们只需要知道三个信息：是谁的锦囊牌,最一开始的目标是谁,我是献殷勤，还是表敌意。每次递归的时候，表敌意--->献殷勤,献殷勤--->表敌意 即可 （因为此时无懈的人是 x的朋友，敌人轮换来的）
-
决斗把自己打死了？这里我没判断TLE25分好气啊！一定注意决斗后判断自己是否die
-
南蛮入侵 和 万箭齐发 是在x出\ 杀/闪\ 前别人帮出无懈,我硬是认为是自己没有才出（因为我玩三国杀的时候经常这样子，滑稽）
-
注意了,因为每次是找到最左边的可以使用的牌，然而你的杀只能对右边一个使用,你的决斗要和明确身份的人决斗，你的桃要你扣血才能用，你的杀只能用一次！所以会发现，当你\ \ 南蛮\ \ 或者\ \ 万箭 \ \ 时可能击杀了你右边和你同阵营的（无脑杀队友）,然后如果你的右边别成了你的敌人，你就可以对他使用左边没用的杀，而之前是不能用的因为你不能杀你队友,还有可能就是 南蛮/万箭 暴露了某些人的身份，你就可以对他们使用决斗，或者在右边的敌人使用杀，然后就是决斗，你可能会让自己扣血，那么如果你之前是满血，就因为强制不让吃桃子，而存了起来，而扣血后又要返回左边去吃桃子， 亦或者是你装了一个诸葛连弩，发现左边还有杀可用。所以为了简化代码，可以当你用了除桃以外的牌时就要令i=0从头再扫一遍（请注意！此题绝对不卡时间，请放心大胆的暴力）
-
如果反贼决斗，一定是找主pig，无论是否已经暴露身份，都会找主pig!
PS:因为我的代码比较的简洁明了，所以没那么多要注意的~~~
（但是我被第3点卡了3次,第5点卡了2次,第6点卡了2次... (>﹏<)）
接下来对代码核心部位进行讲解
其实不难发现很多地方要判断 x对y是献殷勤还是表敌意亦或者是不轻举妄动
那我这里做了个f(x,y)函数（核心部分）
-
-
-
-
-
代码里面，pig，手牌都是用链表写的,感觉这样好写多了nxt[i]为下一张牌,pre[i]为上一张,nxt[0]为第一张牌
$0:$ 使用无懈,杀，决斗（可以明确身份）
$1:$使用南蛮入侵，万箭齐发（已经造成了伤害）（只能变为类反pig）
首先如果$x$身份已经明确（$0<=id<=2$）返回
否则$id=pid$即可（pid为初始身份,id为当前暴露出的身份）
其余的什么摸牌，弃置，回和开始摸牌，判定是否结束，结束函数，奖励$/$惩罚函数，判断是奖励还是惩罚函数,吃桃函数,濒死函数,攻击函数,无懈函数（递归），南蛮$/$万箭函数（我没归到一起，但事实上可以）,回合函数,和主函数 就没什么可说了，分开写就很容易写出来的，之后只用调用即可
下面上代码（93行！)
这里有两个版本，第一个是我觉得看上去更舒服，更清爽的（其实就是强行压行...当然也可能会使有的人来说十分窒息），第二个是我以前的码风（准确来说是以前的码风格式化后的，250多行）
first:
```cpp
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;//任何锦囊牌对x生效前,判断和x一边的是否有无懈,判断和x不是一边的是否有无懈无懈掉无懈,dfs判断
int n,m,L,len;
const int N=15,M=2010;
char s[M];//id=-1未表明 ,(id=0主pig) (id=1 忠pig) (id=2 反pig) (id=3类反pid)(表明身份)
//pid:给定身份 ,nt下一个,pr上一个pig,cnt:牌数 zgln:诸葛连弩 s:牌
//nxt:下一张牌,pre上一张牌 ,end:最后一张牌
struct Pig{int HP,id,pid,nt,pr,cnt;bool zgln;char s[M];int nxt[M],pre[M],end;}a[N];
int Pig[3];//p[0]:主pig p[1]:忠pig p[2]:反pig
inline void ins(int x,char c){int p=++a[x].cnt;a[x].nxt[a[x].end]=p;a[x].pre[p]=a[x].end;a[x].end=p;a[x].s[p]=c;}//摸牌
inline char get(){if(L<=m)return s[L++];return s[m];}//得到牌
inline void start(int x){ins(x,get());ins(x,get());}//回合开始摸两张
inline void del(int x,int pos){a[x].nxt[a[x].pre[pos]]=a[x].nxt[pos];a[x].pre[a[x].nxt[pos]]=a[x].pre[pos];if(a[x].end==pos)a[x].end=a[x].pre[pos];}//弃置
inline void clear(){a[1].end=0;a[1].nxt[0]=0;a[1].zgln=0;}//主猪误杀 ,弃掉所有牌和zgln
inline void end(){//结束
if(!Pig[0])printf("FP\n");else if(!Pig[2])printf("MP\n");
for(int i=1;i<=n;++i){if(a[i].HP<=0)printf("DEAD");else {for(int j=a[i].nxt[0];j;j=a[i].nxt[j])printf("%c ",a[i].s[j]);}printf("\n");}
exit(0);
}
inline int f(int x,int y){//x-->y献殷勤或者表敌意,0敌意,1殷勤,核心代码
if(a[y].id==-1)return -1;//y未明确身份,x不轻举妄动
if(a[y].id==3){if(a[x].pid==0)return 0;else return -1;}//主pig对类反pig也是敌意,其余对类反pid不轻举妄动
if(a[x].pid==0){if(a[y].id==1||a[y].id==0)return 1;else return 0;}
if(a[x].pid==1){if(a[y].id==0||a[y].id==1)return 1;else return 0;}
if(a[x].pid==2){if(a[y].id==0||a[y].id==1)return 0;else return 1;}
return -1;
}
inline void is_end(){if(Pig[0]&&Pig[2])return;end();}//是否结束,主pig,或者反pig死亡就算结束
inline void jl(int x){ins(x,get());ins(x,get());ins(x,get());}//奖励
inline void pd(int dead,int killer){if(a[dead].pid==2)jl(killer);if(a[dead].pid==1&&a[killer].pid==0)clear();}
inline void P(int x,int pos){if(a[x].HP==4)return;a[x].HP++;del(x,pos);}//吃桃,自己的回合能吃就吃
inline void is_dead(int x,int y){//濒死,可以吃桃
if(a[x].HP>0)return;
for(int i=a[x].nxt[0];i;i=a[x].nxt[i]){if(a[x].s[i]=='P')P(x,i);if(a[x].HP>0)break;}
if(a[x].HP<=0){a[a[x].nt].pr=a[x].pr;a[a[x].pr].nt=a[x].nt;Pig[a[x].pid]--;is_end();pd(x,y);}//死亡就去掉这个人,先判断是否结束
}
inline void upd(int x,int y,int v){if(a[x].id>=0&&a[x].id<=2)return;//已经跳了,就返回
if(v==1){if(a[y].pid==0)a[x].id=3;return;}//对主pig造成伤害变为类反pig
a[x].id=a[x].pid;
}//x对y:v=0:使用无懈,杀,决斗,: v=1使用南蛮,万箭
inline void attack(int x,int y){a[y].HP--;is_dead(y,x);}//x攻击y,判断y是否死亡,攻击来源是x,濒死可以吃桃
inline bool have(int x,char c){for(int i=a[x].nxt[0];i;i=a[x].nxt[i])if(a[x].s[i]==c){del(x,i);return 1;}return 0;}//是否有c这张牌,有则丢
inline bool K(int x,int pos){//决定是否对下一个打杀取决于献殷勤还是表敌意
int y=a[x].nt;int p=f(x,y);if(p==-1)return 0;//未使用
if(p==0){del(x,pos);upd(x,y,0);if(!have(y,'D'))attack(x,y);return 1;}//表敌意,杀一下,对面没有闪则造成伤害
return 0; //无论是否造成伤害都要更新他的身份id
}
inline bool J(int x,int y,int v){
if(f(x,y)==v&&have(x,'J')){upd(x,y,0);if(!J(x,y,v^1))return 1;}
for(int i=a[x].nt;i!=x;i=a[i].nt){if(f(i,y)==v&&have(i,'J')){upd(i,y,0);if(!J(i,y,v^1))return 1;}}
return 0;
}//从x开始,需要给y出什么,v=0表示我是他敌人,我要无懈他的无懈,v=1表示我和他是一边的,我要帮他无懈
inline void F(int x,int y){//x对y用决斗,y先出
if(J(x,y,1))return;
while(1){swap(x,y);if((a[x].pid==1&&a[y].pid==0)||(!have(x,'K'))){attack(y,x);return;}}//x没杀,或者x是忠pig,y是主pig
}inline void Nmrq(int x,int y){//x对y使用
if(!J(x,y,1)&&!have(y,'K')){attack(x,y);upd(x,y,1);}
}inline void Wjqf(int x,int y){
if(!J(x,y,1)&&!have(y,'D')){attack(x,y);upd(x,y,1);}
}
inline void work(int x){
start(x);int is_K=0;
for(int i=a[x].nxt[0];i;i=a[x].nxt[i]){
if(a[x].s[i]=='P')P(x,i);
if(a[x].s[i]=='K'&&(!is_K||a[x].zgln))if(K(x,i)){is_K++;i=0;}
if(a[x].s[i]=='F'){
if(a[x].pid==2){del(x,i);upd(x,1,0);F(x,1);i=0;}
else for(int j=a[x].nt;j!=x;j=a[j].nt){int p=f(x,j);if(p==0){del(x,i);upd(x,j,0);F(x,j);i=0;break;}
}if(a[x].HP<=0)return;
}
if(a[x].s[i]=='N'){del(x,i);for(int j=a[x].nt;j!=x;j=a[j].nt)Nmrq(x,j);i=0;}
if(a[x].s[i]=='W'){del(x,i);for(int j=a[x].nt;j!=x;j=a[j].nt)Wjqf(x,j);i=0;}
if(a[x].s[i]=='Z'){a[x].zgln=1;del(x,i);i=0;}
}
}
inline void slove(){
scanf("%d%d",&n,&m);
char S[5];int kase;
for(int i=1;i<=n;++i){
scanf("%s",S+1);kase=0;
if(S[1]=='M')a[i].pid=0;else if(S[1]=='Z')a[i].pid=1;else a[i].pid=2;
Pig[a[i].pid]++;
while(++kase<=4){scanf("%s",S+1);ins(i,S[1]);}
}for(int i=1;i<=m;++i){scanf("%s",S+1);s[i]=S[1];}
for(int i=1;i<=n;++i){a[i].nt=(i==n?1:i+1);a[i].pr=(i==1?n:i-1);a[i].HP=4;a[i].id=-1;}
L=1;a[1].id=0;is_end();
for(int i=1;;i=a[i].nt)work(i);
}
int main(){slove();return 0;}
```
second:
```cpp
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;//任何锦囊牌对x生效前,判断和x一边的是否有无懈,判断和x不是一边的是否有无懈无懈掉无懈,dfs判断
int n,m,L,len;
const int N=15,M=2010;
char s[M];//id=-1未表明 ,(id=0主pig) (id=1 忠pig) (id=2 反pig) (id=3类反pid)(表明身份)
//pid:给定身份 ,nt下一个,pr上一个pig,cnt:牌数 zgln:诸葛连弩 s:牌
//nxt:下一张牌,pre上一张牌 ,end:最后一张牌
struct Pig {
int HP,id,pid,nt,pr,cnt;
bool zgln;
char s[M];
int nxt[M],pre[M],end;
} a[N];
int Pig[3];//p[0]:主pig p[1]:忠pig p[2]:反pig
inline void ins(int x,char c) {
int p=++a[x].cnt; //摸牌
a[x].nxt[a[x].end]=p;
a[x].pre[p]=a[x].end;
a[x].end=p;
a[x].s[p]=c;
}
inline char get() {
if(L<=m)return s[L++]; //得到牌
return s[m];
}
inline void start(int x) {
ins(x,get()); //回合开始摸两张
ins(x,get());
}
inline void del(int x,int pos) {
a[x].nxt[a[x].pre[pos]]=a[x].nxt[pos]; //弃置
a[x].pre[a[x].nxt[pos]]=a[x].pre[pos];
if(a[x].end==pos)a[x].end=a[x].pre[pos];
}
inline void clear() {
a[1].end=0; //主猪误杀 ,弃掉所有牌和zgln
a[1].nxt[0]=0;
a[1].zgln=0;
}
inline void end() { //结束
if(!Pig[0])printf("FP\n");
else if(!Pig[2])printf("MP\n");
for(int i=1; i<=n; ++i) {
if(a[i].HP<=0)printf("DEAD");
else {
for(int j=a[i].nxt[0]; j; j=a[i].nxt[j])printf("%c ",a[i].s[j]);
}
printf("\n");
}
exit(0);
}
inline int f(int x,int y) { //x-->y献殷勤或者表敌意,0敌意,1殷勤,核心代码
if(a[y].id==-1)return -1;//y未明确身份,x不轻举妄动
if(a[y].id==3) {
if(a[x].pid==0)return 0; //主pig对类反pig也是敌意,其余对类反pid不轻举妄动
else return -1;
}
if(a[x].pid==0) {
if(a[y].id==1||a[y].id==0)return 1;
else return 0;
}
if(a[x].pid==1) {
if(a[y].id==0||a[y].id==1)return 1;
else return 0;
}
if(a[x].pid==2) {
if(a[y].id==0||a[y].id==1)return 0;
else return 1;
}
return -1;
}
inline void is_end() {
if(Pig[0]&&Pig[2])return; //是否结束,主pig,或者反pig死亡就算结束
end();
}
inline void jl(int x) {
ins(x,get()); //奖励
ins(x,get());
ins(x,get());
}
inline void pd(int dead,int killer) {
if(a[dead].pid==2)jl(killer);
if(a[dead].pid==1&&a[killer].pid==0)clear();
}
inline void P(int x,int pos) {
if(a[x].HP==4)return; //吃桃,自己的回合能吃就吃
a[x].HP++;
del(x,pos);
}
inline void is_dead(int x,int y) { //濒死,可以吃桃
if(a[x].HP>0)return;
for(int i=a[x].nxt[0]; i; i=a[x].nxt[i]) {
if(a[x].s[i]=='P')P(x,i);
if(a[x].HP>0)break;
}
if(a[x].HP<=0) {
a[a[x].nt].pr=a[x].pr; //死亡就去掉这个人,先判断是否结束
a[a[x].pr].nt=a[x].nt;
Pig[a[x].pid]--;
is_end();
pd(x,y);
}
}
inline void upd(int x,int y,int v) {
if(a[x].id>=0&&a[x].id<=2)return;//已经跳了,就返回
if(v==1) {
if(a[y].pid==0)a[x].id=3; //对主pig造成伤害变为类反pig
return;
}
a[x].id=a[x].pid;
}//x对y:v=0:使用无懈,杀,决斗,: v=1使用南蛮,万箭
inline void attack(int x,int y) {
a[y].HP--; //x攻击y,判断y是否死亡,攻击来源是x,濒死可以吃桃
is_dead(y,x);
}
inline bool have(int x,char c) {
for(int i=a[x].nxt[0]; i; i=a[x].nxt[i])if(a[x].s[i]==c) {
del(x,i); //是否有c这张牌,有则丢
return 1;
}
return 0;
}
inline bool K(int x,int pos) { //决定是否对下一个打杀取决于献殷勤还是表敌意
int y=a[x].nt;
int p=f(x,y);
if(p==-1)return 0;//未使用
if(p==0) {
del(x,pos); //表敌意,杀一下,对面没有闪则造成伤害
upd(x,y,0);
if(!have(y,'D'))attack(x,y);
return 1;
}
return 0; //无论是否造成伤害都要更新他的身份id
}
inline bool J(int x,int y,int v) {
if(f(x,y)==v&&have(x,'J')) {
upd(x,y,0);
if(!J(x,y,v^1))return 1;
}
for(int i=a[x].nt; i!=x; i=a[i].nt) {
if(f(i,y)==v&&have(i,'J')) {
upd(i,y,0);
if(!J(i,y,v^1))return 1;
}
}
return 0;
}//从x开始,需要给y出什么,v=0表示我是他敌人,我要无懈他的无懈,v=1表示我和他是一边的,我要帮他无懈
inline void F(int x,int y) { //x对y用决斗,y先出
if(J(x,y,1))return;
while(1) {
swap(x,y); //x没杀,或者x是忠pig,y是主pig
if((a[x].pid==1&&a[y].pid==0)||(!have(x,'K'))) {
attack(y,x);
return;
}
}
}
inline void Nmrq(int x,int y) { //x对y使用
if(!J(x,y,1)&&!have(y,'K')) {
attack(x,y);
upd(x,y,1);
}
}
inline void Wjqf(int x,int y) {
if(!J(x,y,1)&&!have(y,'D')) {
attack(x,y);
upd(x,y,1);
}
}
inline void work(int x) {
start(x);
int is_K=0;
for(int i=a[x].nxt[0]; i; i=a[x].nxt[i]) {
if(a[x].s[i]=='P')P(x,i);
if(a[x].s[i]=='K'&&(!is_K||a[x].zgln))if(K(x,i)) {
is_K++;
i=0;
}
if(a[x].s[i]=='F') {
if(a[x].pid==2) {
del(x,i);
upd(x,1,0);
F(x,1);
i=0;
} else for(int j=a[x].nt; j!=x; j=a[j].nt) {
int p=f(x,j);
if(p==0) {
del(x,i);
upd(x,j,0);
F(x,j);
i=0;
break;
}
}
if(a[x].HP<=0)return;
}
if(a[x].s[i]=='N') {
del(x,i);
for(int j=a[x].nt; j!=x; j=a[j].nt)Nmrq(x,j);
i=0;
}
if(a[x].s[i]=='W') {
del(x,i);
for(int j=a[x].nt; j!=x; j=a[j].nt)Wjqf(x,j);
i=0;
}
if(a[x].s[i]=='Z') {
a[x].zgln=1;
del(x,i);
i=0;
}
}
}
inline void slove() {
scanf("%d%d",&n,&m);
char S[5];
int kase;
for(int i=1; i<=n; ++i) {
scanf("%s",S+1);
kase=0;
if(S[1]=='M')a[i].pid=0;
else if(S[1]=='Z')a[i].pid=1;
else a[i].pid=2;
Pig[a[i].pid]++;
while(++kase<=4) {
scanf("%s",S+1);
ins(i,S[1]);
}
}
for(int i=1; i<=m; ++i) {
scanf("%s",S+1);
s[i]=S[1];
}
for(int i=1; i<=n; ++i) {
a[i].nt=(i==n?1:i+1);
a[i].pr=(i==1?n:i-1);
a[i].HP=4;
a[i].id=-1;
}
L=1;
a[1].id=0;
is_end();
for(int i=1;; i=a[i].nt)work(i);
}
int main() {
slove();
return 0;
}
```