自动搬运

查看原文

来自洛谷，原作者为

	All_Wrong_Answer 不拿蓝钩不改签

搬运于2025-08-24 23:08:45，当前版本为作者最后更新于2025-01-21 16:50:54，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

前言：

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

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

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

思路：

大模拟，细节超级多：

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

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

#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;
}