题解：P11601 『Fwb』狼人の杀戮

_Fireflies_ · 2025-01-21 16:50:54 · 题解

题目传送门

前言：

2025.1.22：被出题人 Hack，更改代码后通过了，重审。

2025.1.23：又被 Hack，改了一下又过了，再次重审。

AK 了这场比赛，rk14，被这题折磨了近一个小时，必须写个题解泄愤。

思路：

大模拟，细节超级多：

如果当晚是不合法的，那么应当讲这晚的所有操作恢复成上一晚结束时的状态，包括：死亡全部不算，女巫用的药也不算。
判断不合法（3~11）：
id不存在，不合法。
不是某一身份的人用了那个身份的技能。
杀了已经死的人。
一晚多次用技能（包括女巫一晚同时用解药毒药）。
杀自己。
不符合技能使用条件就用技能。
女巫被杀了只能用解药，用毒药不合法。
杀多人。
女巫解药救没死的人。
每晚清空的：当夜死亡的人，当晚技能使用次数。
记得记录当晚死亡人数。
已经死亡的人用技能。
女巫死后解药只能救自己！

可以看看代码，有详细注释：

#include <bits/stdc++.h>
using namespace std;
int t,n;
int sf[105];//身份 
bool sw[105];//死亡的人 
int nwjy[105],nwdy[105];//女巫的毒药和解药 
int shnwjy[105],shnwdy[105];//上一晚时女巫毒药和解药的状态 
bool jncs[105];//当晚技能使用次数 
int flag1=0,flag2=0;//flag1：判断非法；flag2：当晚死亡人数 
bool dysw[105];//当晚死亡的人 
int a[1005],b[1005];
int main(){
    cin>>t>>n;
    for(int i=1;i<=n;i++){
        cin>>sf[i];
    }
    for(int i=1;i<=t;i++){
        memset(jncs,0,sizeof(jncs));
        memset(dysw,0,sizeof(dysw));
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        //多测清空 
        int u;
        cin>>u;
        flag1=0;
        flag2=0; 
        //重置是否合法的flag1和当夜死亡人数的flag2 
        for(int j=1;j<=u;j++){
            int c;
            cin>>a[j]>>b[j]>>c;
            if(b[j]>n||c>n) flag1=1;//id不存在 
            if(a[i]<0||a[i]>3) flag1=1;
            if(flag1==1) continue;//当夜不合法可以直接输入完就continue 
            if(a[j]==0){
                if(sf[b[j]]!=1) flag1=1;//非狼人刀人
                else if(sw[c]==true) flag1=1;//刀了已经死了的人
                else if(jncs[b[j]]==true) flag1=1;//多次刀人
                else if(b[j]==c) flag1=1;//刀自己
                else{
                    sw[c]=true;
                    dysw[c]=true;
                    jncs[b[j]]=true;
                    flag2++;
                } 
            }
            if(a[j]==1){
                if(sw[b[j]]==true) flag1=1;
                else if(nwdy[b[j]]==true) {flag1=1;}//毒药用完了
                else if(jncs[b[j]]==true) flag1=1;//多次毒人
                else if(sf[b[j]]!=4) flag1=1; //非女巫毒人
                else if(sw[c]==true) flag1=1;//毒已经死的人
                else if(b[j]==c) flag1=1;//毒自己
                else{
                    sw[c]=true;
                    dysw[c]=true;
                    jncs[b[j]]=true;
                    nwdy[b[j]]=true;
                    flag2++;
                } 
            }
            if(a[j]==2){
                if(sw[b[j]]==true&&c!=b[j]) flag1=1;//被Hack的地方1
                else if(nwjy[b[j]]==true){flag1=1;}//解药用完了
                else if(jncs[b[j]]==true) flag1=1;//多次解药救人
                else if(sf[b[j]]!=4) flag1=1; //非女巫救人
                else if(dysw[c]==false) flag1=1;//非当夜死亡
                else if(sw[c]==false) flag1=1;//救活人 
                else {
                    if(sf[c]==3){
                        jncs[c]=false;//被Hack的地方2
                    }
                    sw[c]=false;
                    dysw[c]=false;
                    jncs[b[j]]=true;
                    nwjy[b[j]]=true;
                    flag2--;
                } 
            }
            if(a[j]==3){
                if(dysw[b[j]]==false) flag1=1;//当夜没死 
                else if(jncs[b[j]]==true) flag1=1;//带走多人 
                else if(sf[b[j]]!=3) flag1=1; //非猎人带走别人 
                else if(sw[c]==true) flag1=1;//带走死人
                else if(b[j]==c) flag1=1;//杀自己 
                else {
                    sw[c]=true;
                    dysw[c]=true;
                    jncs[b[j]]=true;
                    flag2++;
                } 
            }
        }
        for(int k=1;k<=n;k++){
            if(sf[k]==3&&dysw[k]==true&&jncs[k]==false){
                flag1=1;//猎人没带走人 
                break;
            }
        }
        if(flag1==1){
            for(int k=1;k<=n;k++){
                if(dysw[k]==true) sw[k]=false;
            }//不合法，回溯死亡状态 
            for(int i=1;i<=n;i++){
                nwdy[i]=shnwdy[i];
                nwjy[i]=shnwjy[i];
            }//不合法，回溯女巫的毒药和解药 
            cout<<"Wrong\n";
        } 
        else if(flag2==0) cout<<"Safe\n" ;//平安夜 
        else{
            cout<<flag2<<" ";
            for(int l=1;l<=n;l++){
                if(dysw[l]==true) cout<<l<<" ";
            }
            cout<<endl;
        }
        for(int i=1;i<=n;i++){
            shnwdy[i]=nwdy[i];
            shnwjy[i]=nwjy[i];
        }
        //更新女巫的毒药和解药的状态 
    }
    return 0;
}