题解 P2482 【[SDOI2010]猪国杀】

_caiji_

2021-04-16 19:58:01

Personal

###### ~~想看代码的直接跳 Day 6~~ ~~这题不能发题解,所以这是做题记录~~ 做题原因:499AC,教练推荐我切这题 ~~遗言~~前言:早就听说了这个大%你,它让每一个挑战者失去梦想。打开最优解,3 4 5 KB的代码比比皆是。我今天也来整一波,锻炼码力。 [题目链接](/problem/P2482) 目标: |points|status|date| |:-:|:-:|:-:| |0|done|4/16| |10|done|4/16| |30|done|4/17| |(30,100)|done|4/30| |100|done|5/1| |最短解|done|5/8| ### Day 1 非常 naive 地写了[第一版代码](https://www.luogu.com.cn/paste/4btcwd1q),发现太难维护了,直接 `ctrl-a delete` 重构了。 整了个[真题面](https://www.luogu.com.cn/paste/5xqw3xp8)方便理解。 写了 10 分!!! 第一次[提交](https://www.luogu.com.cn/record/49583708)!!! 全 TLE 了!!! 没写闪躲杀是吧,我补!!! 又 tm 全 TLE!!! 没有跳忠跳反是吧!!! 又来 T!!! 调出来了,没取模!!! [10分](https://www.luogu.com.cn/record/49585945)啦!!! [当前代码](https://www.luogu.com.cn/paste/bscm2kd8) ### Day 2 改了一下代码,由面向过程+面向对象改成了纯面向过程。 向 30 pts 进发! 花了 114514min 写完了 F N W,调试调半天。 具体说一下错了什么吧: - 用完的牌没丢掉 - 遍历环时用 `now<user`(应该为 `now!=user`) - 主公跳了忠,导致反贼无法与主公决斗(特判就好了) [提交记录](https://www.luogu.com.cn/record/49614706) [当前代码](https://www.luogu.com.cn/paste/8q6w6jcs) 改了一下[35 pts](https://www.luogu.com.cn/record/49616919)?数据怎么了? ### Day 3 我的无懈可击: ```cpp bool wxkj(int user){//mf: MP/ZP or FP for(int now=(user+1)%n;now!=user;now=(user+1)%n){ if(lp(user)==lp(now)){ qizhi(now,J); a[now].zt=a[now].id=='F'?TF:TZ; if(a[now].id=='M') a[now].zt=ZZ; return !wxkj(now); } } } ``` 别人的无懈可击:<https://loj.ac/s/939059> ```cpp inline bool unattackable(int playerID, int targetID, int mode) { bool flag = true; for (int i = playerID; i != playerID || flag; i = a[i].nxt) { flag = false; if (mode == 1) { if ((a[i].identify == identify[targetID]) || (a[i].identify == 'Z' && identify[targetID] == 'M') || (a[i].identify == 'M' && identify[targetID] == 'Z')) { for (int j = 1; j <= a[i].count; ++j) { if (a[i].cards[j] == 'J') { a[i].cards[j] = 0; identify[i] = a[i].identify; return !unattackable(i, playerID, !mode); } } } } else { if (((a[i].identify == 'Z' || a[i].identify == 'M') && identify[playerID] == 'F') || (a[i].identify == 'F' && (identify[playerID] == 'Z' || identify[playerID] == 'M'))) { for (int j = 1; j <= a[i].count; ++j) { if (a[i].cards[j] == 'J') { a[i].cards[j] = 0; identify[i] = a[i].identify; return !unattackable(i, playerID, mode); } } } } } return false; } ``` 一看就很不对劲…… ### Day 4 我的: ```cpp //user嫌疑人,target受害者 bool wxkj(int user,int target,int mode){//mf: 献殷勤 or 表敌意 for(int now=(user+1)%n;now!=user;now=(user+1)%n){ if(lp(user)^lp(target)^mode){ qizhi(now,J); a[now].zt=a[now].id=='F'?TF:TZ; if(a[now].id=='M') a[now].zt=ZZ; return !wxkj(now,user,0); } } return 0; } ``` 有内味了...... 不过还是错的...... 这样 40 pts: ```cpp bool wxkj(int user,int target,int mode){//mode: 献殷勤 or 表敌意 if(a[target].zt==UNK) return 0; bool flg=1; for(int now=user;now!=user||flg;now=(now+1)%n){ flg=0; if(mode==1){ if(lp(now)==lp(target)){ if(!qizhi(now,J)) continue; a[now].zt=a[now].id=='F'?TF:TZ; if(a[now].id=='M') a[now].zt=ZZ; return !wxkj(now,user,0); } }else{ if(lp(now)==lp(user)){ if(!qizhi(now,J)) continue; a[now].zt=a[now].id=='F'?TF:TZ; if(a[now].id=='M') a[now].zt=ZZ; return !wxkj(now,user,0); } } } return 0; } ``` 改了什么呢? - target(还是 user?) 一定要亮明身份!!! - 要遍历到自己,可以用个 flg 标记一下是第一次还是结束。 - mode 要分类讨论 - 如果弃不了无懈就不能实行无懈(废话) [现在代码](https://loj.ac/s/1124203) 不会调了,[发帖](https://www.luogu.com.cn/discuss/show/312694)了,有人会帮我调吗...... ### Day 5 原来的代码直接丢了,来重构。整个 oop 的。 一开始只写了 `PKD` 三张牌,交上去 T 了,一看,啊还有个 `Z`。还是 T,发现读入挂了。说一下,这里一定要 ```cpp struct Getnewcard{ int lstc,gctmp; queue<char> cheap; void init(){ char ch; for(int i=1;i<=m;i++){ cin>>ch; cheap.push(ch); } lstc=ch; } operator char(){ if(cheap.empty()){ return lstc; }else{ int tmp=cheap.front(); cheap.pop(); return tmp; } } } getnewcard; ``` 这样写,偷懒一点的 ```cpp struct Getnewcard{ int ch; // ^~~ operator char(){ return cin>>ch,ch; } } getnewcard; ``` 会全 T。我也不知道为什么。 upd:T 是因为 `int`,改了就行了。 然后是锦囊牌。注意主公决斗忠臣时忠臣直接掉血,反臣直接和主公对线。其它两个都很简单。然后就能获得 30 pts 的好成绩。 接着是无懈可击。结合自己的理解,抄一下题解就好了。 ```cpp bool ccfnmsl(int user,int target,int mode){ bool flg=1; if(mode==1&&!a[target].jump) return 0; for(int now=user;now!=user||flg;now=findnxt(now)){ flg=0; if(mode==1){ bool f1=a[target].id=='F', f2=a[now].id=='F'; if(f1==f2){ for(int i=1;i<=a[now].cnt;i++){ if(a[now].cards[i]=='J'){ a[now].cards[i]='U'; a[now].jump=1,a[now].likebad=0; return !ccfnmsl(now,user,0); } } } }else{ bool f1=a[user].id=='F', f2=a[now].id=='F'; if(f1!=f2){ for(int i=1;i<=a[now].cnt;i++){ if(a[now].cards[i]=='J'){ a[now].cards[i]='U'; a[now].jump=1,a[now].likebad=0; return !ccfnmsl(now,user,0); } } } } } return 0; } ``` 加上调用,75 pts。 是细节写挂了,这 5 个点各卡一种错误写法,非常可怕。 这里来说一下怎么更加合理的 debug: 1. 先整个 `#define DEBUG` 1. 然后写一个 `fout`,用来向 `log.txt` 输出调试信息。 为了和 `#define DEBUG` 兼容(或者说,注释 `#define DEBUG` 就不会有调试信息),可以这样实现: ```cpp #ifdef DEBUG ofstream fout("log.txt",ios::out); #else struct CCF{ template<class T> CCF operator <<(T a){return (void)a,*this;} } fout; #endif ``` `//#define DEBUG` 时直接定义一个完全没用的东西,还不会报 `warning`,就是用不了 `endl` 了。 3. 然后就可以写调试信息了,比如输出手牌 ```cpp for(int i=0;i<n;i++){ fout<<a[i].id<<" "<<a[i].hp<<" "<<a[i].jump<<" "; if(a[i].dead) fout<<"DEAD"; else{ for(int j=1;j<=a[i].cnt;j++){ if(a[i].cards[j]!='U') fout<<a[i].cards[j]<<" "; } } fout<<'\n'; } fout<<"--------------------"<<'\n'; ``` 更方便 debug 了。 可以配合 [LOJ](loj.ac) 下的数据调,~~而不是自己脚造或者被洛谷次数限制卡死~~ (注:以下测试点编号是 LOJ 的) 75 pts 错的是 #7,13,14,15,20,来一个个 debug。 t#7:要特别注意主公决斗/杀类反臣的情况,类反臣一定没有跳,而我一上来就 `if(!a[j].jump) return 0;`。加个特判就好了。 还有,主公决斗忠臣时忠臣直接掉血(复读?),改完这些就过了 #7。 t#13 && #15:这两个点一起卡我的错解。 错误地方:用完杀要标记已经用过杀。(卧槽我怎么错在这种地方),还有特判开局一个反臣也没有的情况。 t#17 && #20:除了 `P` 外,每用一张牌就要从头开始遍历牌堆,具体方法是 `i=0`,因为循环后要 `i++`。 改完这些又多了个 #18 WA?! 不管了,打表。 [现在的,打表 AC 的代码](https://loj.ac/s/1128992) ### Day 6 先来封装几个小函数,顺便把无懈可击改成了这样: ```cpp //无 懈 可 击 bool Pig::ccfnmsl(int target,int mode){ fout<<user<<"->"<<target<<" "<<mode<<'\n'; if(mode==1&&!a[target].jump) return 0; bool flg=1; for(int now=user;now!=user||flg;now=findnxt(now)){ flg=0; bool f1=a[mode?target:user].id=='F', f2=a[now].id=='F'; if(f1^f2^mode&&a[now].thrcard('J')){ a[now].jump=1,a[now].likebad=0; return !a[now].ccfnmsl(user,0); } } return 0; } ``` 简单。。。。。。 找到 bug 了:在用 `K` 的时候, ```cpp int nxt = findnxt(user); if ((!usedkill || AK) && check(user, nxt)) { jump = 1, likebad = 0; cards[i] = 'U'; if (a[nxt].thrcard('D')) break;// a[nxt].hurt(user); usedkill = 1; i = 0; } ``` 如果对面闪掉了,那 `usedkill=1` 这一句就不会执行,换一下顺序即可。 真 [AC](https://loj.ac/s/1129054) 代码:包含调试+注释,5K [无注释/debug 版](https://loj.ac/s/1134828) ```cpp #include <queue> #include <cstdlib> #include <fstream> #include <iostream> using namespace std; //debug 开关,开启可以输出错误信息到 log.txt #define DEBUG #ifdef DEBUG ofstream fout("log.txt",ios::out); #else struct CCF{ template<class T> CCF operator <<(T a){return (void)a,*this;} } fout; #endif //万恶之源 int n,m,pigcnt[128]; //抽一张牌 struct Getnewcard{ char ch; operator char(){ return cin>>ch,ch; } } getnewcard; //猪的结构体,全都是 public struct Pig{ //编号 几张牌 血量 int user,cnt,hp; //有没有跳忠/反 是不是类反 死了没 有没有AK bool jump,likebad,dead,AK; //牌 身份 char cards[2010],id; //公开处刑 Pig (); void clear (); void hurt (int); bool thrcard (char); void optcards (); void getcard (); void runturn (); void godead (int); void fight (int); void AOE (char); bool ccfnmsl (int,int); bool check (int); #define usecard() cards[i]='U',i=0 #define gojump() jump=1,likebad=0 } a[15]; //输出,带个 exit(0) void print(){ cout<<(a[0].dead?"FP":"MP")<<endl; for(int i=0;i<n;i++) a[i].optcards(); exit(0); } //找下一个人 int findnxt(int i){ while(a[i=(i+1)%n].dead); return i; } //检查 i 能不能杀 j bool Pig::check(int j){ if(id=='M'&&a[j].likebad) return 1; if(!a[j].jump) return 0; switch(id){ case 'M':return a[j].id=='F'||a[j].likebad; case 'Z':return a[j].id=='F'; case 'F':return a[j].id=='M'||a[j].id=='Z'; } return 0; } //无 懈 可 击 bool Pig::ccfnmsl(int target,int mode){ fout<<user<<"->"<<target<<" "<<mode<<'\n'; if(mode==1&&!a[target].jump) return 0; bool flg=1; for(int now=user;now!=user||flg;now=findnxt(now)){ flg=0; bool f1=a[mode?target:user].id=='F', f2=a[now].id=='F'; if(f1^f2^mode&&a[now].thrcard('J')){ a[now].jump=1,a[now].likebad=0; return !a[now].ccfnmsl(user,0); } } return 0; } //猪的构造函数,清零 Pig::Pig(){ cnt=jump=likebad=dead=AK=0; hp=4; } //清除牌和 AK void Pig::clear(){ cnt=AK=0; } //扣一滴血 void Pig::hurt(int killer){ hp--; while(hp<=0){ if(thrcard('P')) hp++; else{godead(killer);break;} } } //弃一张牌 bool Pig::thrcard(char card){ for(int i=1;i<=cnt;i++){ if(cards[i]==card) return cards[i]='U',1; } return 0; } //输出手牌 void Pig::optcards(){ if(dead) return (void)(cout<<"DEAD"<<endl); for(int i=1;i<=cnt;i++){ if(cards[i]!='U') cout<<cards[i]<<" "; } cout<<endl; } //摸一张牌 void Pig::getcard(){ cards[++cnt]=getnewcard; } //决斗 void Pig::fight(int target){ if(id=='M'&&a[target].id=='Z') return a[target].hurt(user); while(1){ if(!a[target].thrcard('K')) return a[target].hurt(user ); if(!a[user ].thrcard('K')) return a[user ].hurt(target); } } //AOE void Pig::AOE(char card){ for(int now=findnxt(user);now!=user;now=findnxt(now)){ if(!ccfnmsl(now,1)&&!a[now].thrcard(card)){ a[now].hurt(user); if(!jump&&a[now].id=='M') likebad=1; } } } //跑一轮 void Pig::runturn(){ getcard(); getcard(); fout<<"getcard:"<<cards[cnt-1]<<" "<<cards[cnt]<<'\n'; bool usedkill=0; for(int i=1;i<=cnt;i++){ switch(cards[i]){ case 'P':{ if(hp<4) cards[i]='U',hp++; break; } case 'K':{ int nxt=findnxt(user); if((!usedkill||AK)&&check(nxt)){ fout<<"K "<<user<<"->"<<nxt<<'\n'; usecard(),gojump(),usedkill=1; if(!a[nxt].thrcard('D')) a[nxt].hurt(user); } break; } case 'D':{ //??? break; } case 'F':{ if(id=='F'){ usecard(),gojump(); int now=0; fout<<"JUEDOU "<<user<<"->"<<now<<'\n'; if(!ccfnmsl(now,1)) fight(now); }else{ for(int now=findnxt(user);now!=user;now=findnxt(now)){ if(check(now)){ fout<<"JUEDOU "<<user<<"->"<<now<<'\n'; usecard(),gojump(); if(!ccfnmsl(now,1)) fight(now); break; } } } break; } case 'N':{ fout<<"N "<<user<<"->"<<"all"<<'\n'; usecard(),AOE('K'); break; } case 'W':{ fout<<"W "<<user<<"->"<<"all"<<'\n'; usecard(),AOE('D'); break; } case 'J':{ //??? break; } case 'Z':{ usecard(),AK=1; break; } } } } //去世 void Pig::godead(int killer){ dead=1,clear(); pigcnt[(int)id]--; if(id=='M') print(); if(pigcnt[(int)'F']==0) print(); if(id=='F'){ a[killer].getcard(); a[killer].getcard(); a[killer].getcard(); } if(id=='Z'&&a[killer].id=='M'){ a[killer].clear(); } } int main(){ cin>>n>>m; for(int i=0;i<n;i++){string ipt; cin>>ipt; a[i].user=i,a[i].id=ipt[0]; pigcnt[(int)(ipt[0])]++; for(int j=1;j<=4;j++){ cin>>ipt; a[i].cards[++a[i].cnt]=ipt[0]; } } a[0].jump=1; if(pigcnt[(int)'F']==0) print(); int now=-1; int cnt=0; while(1){ fout<<"Round "<<++cnt<<" Pig "<<findnxt(now)<<'\n'; a[now=findnxt(now)].runturn(); for(int i=0;i<n;i++){ fout<<a[i].id<<" "<<a[i].hp<<" "<<a[i].jump<<" "<<a[i].likebad<<" "; if(a[i].dead) fout<<"DEAD"; else{ for(int j=1;j<=a[i].cnt;j++){ if(a[i].cards[j]!='U') fout<<a[i].cards[j]<<" "; } } fout<<'\n'; } fout<<"--------------------"<<'\n'; } return 0; } ``` ### Day 7 经过一个晚上的努力,我写出了 >[L O J 最 短 解](https://loj.ac/s/1135157) 下面是 2021 个字符的代码: ```cpp //cjhtxdy #include<cstdlib> #include<iostream> #define p20()p8[i]='U',i=0 #define lp(s)(a[s].p9=='F') #define Fm(s)for(I v6=p22(s);v6!=p1;v6=p22(v6)) #define Fr(i,l,r)for(I i=l;i<=r;i++) #define Rt return #define Wi while #define Bk break; #define Cs case using namespace std;typedef int I;typedef char C;typedef void V;typedef bool B;I n,m,v1[128];C ch;struct P{I p1,p2,p3;B p4,p5,p6,p7;C p8[2010],p9;V p10(){p4=1,p5=0;}V p11(){cin>>ch,p8[++p2]=ch;}V p12(I v2){p3--;if(p3<=0){if(p13('P'))p3++;else p15(v2);}}B p13(C v3){Fr(i,1,p2)if(p8[i]==v3)Rt p8[i]='U',1;Rt 0;}V p14();V p15(I);V p16(I);V p17(C);B p18(I,I);B p19(I);} a[15];I p22(I i){Wi(a[i=(i+1)%n].p6);Rt i;}V p21(){cout<<(a[0].p6?"FP":"MP")<<endl;Fr(i,0,n-1){if(a[i].p6)cout<<"DEAD";else Fr(j,1,a[i].p2)if(a[i].p8[j]!='U')cout<<a[i].p8[j]<<" ";cout<<endl;}exit(0);}B P::p19(I j){if(p9=='M'&&a[j].p5)Rt 1;if(!a[j].p4)Rt 0;switch(p9){Cs 'M':Rt lp(j)||a[j].p5;Cs 'Z':Rt lp(j);Cs 'F':Rt !lp(j);}Rt 0;}B P::p18(I v4,I v5){if(v5&&!a[v4].p4) Rt 0;if(v5&&lp(v4)==lp(p1)&&p13('J'))Rt p10(),!p18(p1,0);Fm(p1)if(lp(v5?v4:p1)^lp(v6)^v5&&a[v6].p13('J'))Rt a[v6].p10(),!a[v6].p18(p1,0);Rt 0;}V P::p16(I v4){if(p9=='M'&&a[v4].p9=='Z')Rt a[v4].p12(p1);Wi(1){if(!a[v4].p13('K'))Rt a[v4].p12(p1);if(!a[p1].p13('K'))Rt a[p1].p12(v4);}}V P::p17(C v3){Fm(p1)if(!p18(v6,1)&&!a[v6].p13(v3))a[v6].p12(p1),p5|=!p4&&a[v6].p9=='M';}V P::p14(){p11(),p11();B v7=0;Fr(i,1,p2){switch(p8[i]){Cs 'P':if(p3<4)p8[i]='U',p3++;Bk Cs 'Z':p20(),p7=1;Bk Cs 'N':p20(),p17('K');Bk Cs 'W':p20(),p17('D');Bk Cs 'K':{I v8=p22(p1);if((!v7||p7)&&p19(v8)){p20(),p10(),v7=1;if(!a[v8].p13('D'))a[v8].p12(p1);}Bk}Cs 'F':{Fm(lp(p1)?-1:p1)if(p19(v6)){p20(),p10();if(!p18(v6,1))p16(v6);Bk}Bk}}}}V P::p15(I v2){p6=1,p2=p7=0,v1[p9]--;if(p9=='M'||!v1['F'])p21();if(p9=='Z'&&a[v2].p9=='M')a[v2].p2=a[v2].p7=0;if(p9=='F')Fr(j,1,3)a[v2].p11();}I main(){cin>>n>>m;Fr(i,0,n-1){string v0;cin>>v0;a[i].p1=i,a[i].p9=v0[0],a[i].p3=4,v1[v0[0]]++;Fr(j,1,4) a[i].p11();}a[0].p4=1;I v6=-1;Wi(1)a[v6=p22(v6)].p14();Rt 0;} ``` 多优美啊。 ### Day 不想数(2021.8.5) 再次创造记录,1.88 KB。 注意,语言是 C++ 11。 我并不想把代码第一行的原文放出来,所以不挂链接了。 ```cpp //*** ***** *** *******! #include<bits/stdc++.h> #define p20()p8[i]=0,i=0 #define L(s)(a[s].p9=='F') #define F(s)for(I v6=p22(s);v6^p1;v6=p22(v6)) #define f(i,l,r)for(I i=l;i<=r;i++) #define R return #define W while #define K break; #define S case #define O if using namespace std;using I=int;using C=char;using V=void;using B=bool;I n,m,v1[128];C ch;struct P{I p1,p2,p3;B p4,p5,p6,p7;C p8[2010],p9;V p10(){p4=1,p5=0;}V p11(){cin>>ch,p8[++p2]=ch;}V p12(I v2){O(--p3<1){O(p13('P'))p3++;else p15(v2);}}B p13(C v3){f(i,1,p2)O(p8[i]==v3)R p8[i]=0,1;R 0;}V p14();V p15(I);V p16(I);V p17(C);B p18(I,I);B p19(I);}a[21];I p22(I i){W(a[(++i)%=n].p6);R i;}V p21(){cout<<(a[0].p6?"FP":"MP")<<"\n";f(i,0,n-1){O(a[i].p6)cout<<"DEAD";else f(j,1,a[i].p2)O(a[i].p8[j])cout<<a[i].p8[j]<<" ";cout<<"\n";}exit(0);}B P::p19(I j){O(p9=='M'&&a[j].p5)R 1;O(!a[j].p4)R 0;switch(p9){S'M':R L(j)||a[j].p5;S'Z':R L(j);S'F':R !L(j);}R 0;}B P::p18(I v4,I v5){O(v5&&!a[v4].p4)R 0;O(v5&&L(v4)==L(p1)&&p13('J'))R p10(),!p18(p1,0);F(p1)O(L(v5?v4:p1)^L(v6)^v5&&a[v6].p13('J'))R a[v6].p10(),!a[v6].p18(p1,0);R 0;}V P::p16(I v4){O(p9=='M'&&a[v4].p9=='Z')R a[v4].p12(p1);W(1){O(!a[v4].p13('K'))R a[v4].p12(p1);O(!a[p1].p13('K'))R a[p1].p12(v4);}}V P::p17(C v3){F(p1)O(!p18(v6,1)&&!a[v6].p13(v3))a[v6].p12(p1),p5|=!p4&&a[v6].p9=='M';}V P::p14(){p11(),p11();B v7=0;f(i,1,p2){switch(p8[i]){S'P':O(p3<4)p8[i]=0,p3++;K S'Z':p20(),p7=1;K S'N':p20(),p17('K');K S'W':p20(),p17('D');K S'K':{I v8=p22(p1);O((!v7||p7)&&p19(v8)){p20(),p10(),v7=1;O(!a[v8].p13('D'))a[v8].p12(p1);}K}S'F':{F(L(p1)?-1:p1)O(p19(v6)){p20(),p10();O(!p18(v6,1))p16(v6);K}K}}}}V P::p15(I v2){p6=1,p2=p7=0,v1[p9]--;O(p9=='M'||!v1['F'])p21();O(p9=='Z'&&a[v2].p9=='M')a[v2].p2=a[v2].p7=0;O(p9=='F')f(j,1,3)a[v2].p11();}I main(){ios::sync_with_stdio(0);cin>>n>>m;f(i,0,n-1){C v0[2];cin>>v0;a[i].p1=i,a[i].p9=v0[0],a[i].p3=4,v1[v0[0]]++;f(j,1,4)a[i].p11();}a[0].p4=1;I v6=-1;W(1)a[v6=p22(v6)].p14();R 0;} ```