题解：P11601 『Fwb』狼人の杀戮
WsW_
·
·
题解
更新
这是一篇已通过的题解。
思路
模拟题先确定判断的步骤。
对于一个操作，我用 opt,u,v 来记录，意思是 u 对 v 使用了 opt 技能。
我将今夜被杀称为将死，之前死亡称为已死。
先把显然的错误判掉。
接下来进行操作。
全部操作结束后判断一下，是否有猎人将死但是没用技能。
如果是合法的，那么将死状态变为已死状态，女巫将用药状态变为已用药状态。
以下是我自己代码实现的细节。
$drug$ 利用状态压缩记录女巫技能使用情况。在二进制下一共四位，分别表示毒药是否用了，解药是否用了，毒药是否将用，解药是否将用。注意每晚要清空后两位。
如果当晚操作是合法的，那么 $todead$ 要合并到 $dead$ 里面；$drug$ 的后两位要合并到前两位里面。
时间复杂度为 $O(tm+tn)$。
---
```cpp
#include<bits/stdc++.h>
using namespace std;
int t,n;
int a[23];
bool dead[23];
bool used[23];
bool todead[23];
int drug[23];
void init(){
memset(used,0,sizeof(used));
memset(todead,0,sizeof(todead));
for(int i=1;i<=n;i++)drug[i]&=3;
}
bool check(int id){
return id>n||id<1||dead[id];
}
bool uskill(int opt,int id){
if((opt==0&&id!=1)||((opt==1||opt==2)&&id!=4)||(opt==3&&id!=3))return 1;
return 0;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>t>>n;
for(int i=1;i<=n;i++)cin>>a[i];
while(t--){
init();
bool wrong=0;
int m; cin>>m;
for(int i=1;i<=m;i++){
int opt,u,v; cin>>opt>>u>>v;
if(check(u)||check(v)||used[u]||uskill(opt,a[u]))wrong=1;
if(opt==0||opt==1||opt==3){
if((opt==3)^todead[u])wrong=1;
if(todead[v]||u==v)wrong=1;
todead[v]=1;
}
if(opt==1||opt==2){
if(drug[u]&(1<<opt-1))wrong=1;
drug[u]|=(1<<opt+1);
}
if(opt==2){
if(!todead[v])wrong=1;
todead[v]=0;
if(todead[u])wrong=1;
if(a[v]==3)used[v]=0;
}
used[u]=1;
}
for(int i=1;i<=n;i++)
if(a[i]==3&&todead[i]&&!used[i])wrong=1;
if(wrong)cout<<"Wrong\n";
else{
int cnt=0;
for(int i=1;i<=n;i++){
drug[i]|=drug[i]>>2;
cnt+=todead[i];
}
if(cnt){
cout<<cnt<<' ';
for(int i=1;i<=n;i++){
if(todead[i])cout<<i<<' ';
dead[i]&=todead[i];
}
cout<<'\n';
}
else cout<<"Safe\n";
}
}
return 0;
}
```