专栏文章

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

P13915题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性,并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio16s2a
此快照首次捕获于
2025/12/02 11:41
3 个月前
此快照最后确认于
2025/12/02 11:41
3 个月前
查看原文

P13915 [PO Final 2024] 鬼抓人 / Tag

题目概括

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

思路

由于作弊的人也可以抓人或被抓,但永远也逃不开已经作弊的事实。
我们可以将每个人分成一下四个身份
  1. 正常的人
  2. 正常的鬼
  3. 作弊的人
  4. 作弊的鬼
于是我们可以总结每个抓捕过程中抓捕者和被抓捕者身份变化的对应关系
(这里使用上述数字描述状态,如 1 代表正常的人)
状态身份
抓捕前1234
抓捕了别人3133
被别人抓捕2244
我们只需要在抓捕前身份为 1 的人抓捕了别人时记录答案即可。

代码思路

由于我们需要记录每个人的身份,且每个人都有对应的名字,可以使用 map 容器存储。
读入的每个人添加进容器中,每次读入抓捕过程只需要按照上述规则分类讨论即可。

代码

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

评论

0 条评论,欢迎与作者交流。

正在加载评论...