题解：P13915 [PO Final 2024] 鬼抓人 / Tag

yytmcjs · 2025-09-02 20:30:50 · 题解

P13915 [PO Final 2024] 鬼抓人 / Tag

题目概括

• 有一群人玩鬼抓人，初始有一个鬼，他抓到人时被抓者会变成鬼，自己则恢复成人。
• 有些人身为人但还是抓人，被抓者还是会变成鬼，但乱抓的人会被视为作弊。
• 求有哪些作弊者。

  思路

  由于作弊的人也可以抓人或被抓，但永远也逃不开已经作弊的事实。

我们可以将每个人分成一下四个身份：

1. 正常的人
2. 正常的鬼
3. 作弊的人
4. 作弊的鬼

于是我们可以总结每个抓捕过程中抓捕者和被抓捕者身份变化的对应关系：

（这里使用上述数字描述状态，如 1 代表正常的人）

我们只需要在抓捕前身份为 1 的人抓捕了别人时记录答案即可。

代码思路

由于我们需要记录每个人的身份，且每个人都有对应的名字，可以使用 map 容器存储。

读入的每个人添加进容器中，每次读入抓捕过程只需要按照上述规则分类讨论即可。

代码

#include <bits/stdc++.h>
using namespace std;

int n,m,ans;
string a,b,c;
map<string,int> stu;        //<名字,身份> 
vector<string> cheat;

int main(){
    cin >> n >> m;
    for (int i=1;i<=n;i++){     //加入容器 
        cin >> a;
        if (i==1)
            stu.insert({a,2});
        else
            stu.insert({a,1});
    }
    for (int i=1;i<=m;i++){
        cin >> a >> b >> c;     //读入过程
        if (stu[a]==1){     //抓捕别人的 
            ans++;
            cheat.push_back(a);
            stu[a]=3;
        }
        else if (stu[a]==2)
            stu[a]=1;
        else if (stu[a]==4)
            stu[a]=3;
        if (stu[c]==1)      //被别人抓捕的 
            stu[c]=2;
        else if (stu[c]==3)
            stu[c]=4;
    }
    sort(cheat.begin(),cheat.end());        //按字典序排序
    cout << ans << endl;        //输出答案
    for (int i=0;i<cheat.size();i++)        //输出人名 
        cout << cheat[i] << " ";
    return 0;
}