HDU6370 Werewolf(2018HDU多校联赛第六场,思路,dfs)

2023-10-05 23:00

本文主要是介绍HDU6370 Werewolf(2018HDU多校联赛第六场,思路,dfs),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Problem Description

“The Werewolves” is a popular card game among young people.In the basic game, there are 2 different groups: the werewolves and the villagers.
Each player will debate a player they think is a werewolf or not.
Their words are like “Player x is a werewolf.” or “Player x is a villager.”.
What we know is :
\1. Villager won’t lie.
\2. Werewolf may lie.
Of cause we only consider those situations which obey the two rules above.
It is guaranteed that input data exist at least one situation which obey the two rules above.
Now we can judge every player into 3 types :
\1. A player which can only be villager among all situations,
\2. A player which can only be werewolf among all situations.
\3. A player which can be villager among some situations, while can be werewolf in others situations.
You just need to print out the number of type-1 players and the number of type-2 players.
No player will talk about himself.

Input

The first line of the input gives the number of test cases T.Then T test cases follow.
The first line of each test case contains an integer N,indicating the number of players.
Then follows N lines,i-th line contains an integer x and a string S,indicating the i-th players tell you,”Player x is a S.”
limits:
1≤T≤10
1≤N≤100,000
1≤x≤N
S∈ {“villager”.”werewolf”}

Output

For each test case,print the number of type-1 players and the number of type-2 players in one line, separated by white space.

Sample Input

1
2
2 werewolf
1 werewolf

Sample Output

0 0

思路

先说题意,在狼人杀游戏中,有两种角色,一种是狼人另一种是村民,他们的特征是:

  • 村民不会说谎
  • 狼人可能说谎

然后玩家有三种类型:

  1. 玩家在所有的情况下只能当村民
  2. 玩家在所有的情况下只能当狼人
  3. 玩家既可以当狼人也可以当村民

题目给出 n n <script type="math/tex" id="MathJax-Element-1">n</script>个玩家,然后给出若干条信息,例如”xxx说xxx是狼人”或者”xxx说xxx是村民”,现在题目想请你确定,第一种类型和第二中类型的玩家数量

首先我们知道,因为狼人可以说谎,所以假设所有的玩家全部是狼人,不论谁说谁是什么,游戏一定成立,他们都可以当狼人,也就证明了不存在“玩家在所有的情况下只能当村民”这种情况.

那么,我们可以做一个假设,假设全部的玩家都是狼人,那么第二种玩家类型的数量为总的玩家数量减去狼人中可以当村民的玩家数量。

那么问题就转化成了在所有的玩家都是狼人的时候,有多少人可以当村名。

我们可以先对题目给出的数据进行记录,记录一下每个人谁说他是狼人谁说他是村民的玩家数量。

我们首先对每一个玩家进行处理,比如,当玩家2说玩家1是狼人的时候,假设玩家1就是狼人,那么当玩家1是狼人的时候他不管说什么,都可以使游戏成立.这个时候我们就可以确定,玩家2可以当村民,那么玩家2当了村民,那么谁说玩家2是村民,那么这个人也可以当村民,这是一个递归的过程,在过程中用vis数组标记当前玩家已经有了确定的身份。但是在这个递归的过程中要注意,当递归出现环的时候,假设到了玩家5,玩家1说玩家5是村民,这个时候因为玩家1的身份是我们确定了的狼,所以玩家1不能被标记为村民,而且要把所有说玩家1是村民的玩家都标记一下。

最后我们就知道了这些狼人中哪些玩家可以做村民,然后用总数减去,再把所有玩家遍历一遍,减去没有被标记过的玩家,就是答案。

代码

#include <bits/stdc++.h>
using namespace std;
#define mem(a, b) memset(a, b, sizeof(a))
typedef long long ll;
const int N = 1e5 + 100;
/*
v1[i]:说第i个人是狼人的集合
v2[i]:说第i个人是村民的集合
*/
vector<int> v1[N], v2[N];
int vis[N];
void init()
{mem(v1, 0);mem(v2, 0);mem(vis, 0);
}
void dfs2(int u)
{for (auto num : v2[u]){vis[num] = 1;dfs2(num);}
}
int dfs(int u, int i)
{int ans = 0;for (auto num : v2[u]){vis[num] = 1;if (num != i)ans += dfs(num, i);elsedfs2(num);}return ans + 1;
}
void solve()
{int n, x;char s[10];scanf("%d", &n);init();for (int i = 1; i <= n; i++){scanf("%d%s", &x, s);if (s[0] == 'w')v1[x].push_back(i);elsev2[x].push_back(i);}int ans = 0;for (int i = 1; i <= n; i++){for (auto num : v1[i]){vis[num] = 1;ans += dfs(num, i);}}ans = n - ans;for (int i = 1; i <= n; i++){if (!vis[i])ans--;}printf("0 %d\n", ans);
}
int main()
{// freopen("in.txt", "r", stdin);int t;scanf("%d", &t);while (t--)solve();return 0;
}

这篇关于HDU6370 Werewolf(2018HDU多校联赛第六场,思路,dfs)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/152231

相关文章

透彻!驯服大型语言模型(LLMs)的五种方法,及具体方法选择思路

引言 随着时间的发展,大型语言模型不再停留在演示阶段而是逐步面向生产系统的应用,随着人们期望的不断增加,目标也发生了巨大的变化。在短短的几个月的时间里,人们对大模型的认识已经从对其zero-shot能力感到惊讶,转变为考虑改进模型质量、提高模型可用性。 「大语言模型(LLMs)其实就是利用高容量的模型架构(例如Transformer)对海量的、多种多样的数据分布进行建模得到,它包含了大量的先验

hdu 2489 (dfs枚举 + prim)

题意: 对于一棵顶点和边都有权值的树,使用下面的等式来计算Ratio 给定一个n 个顶点的完全图及它所有顶点和边的权值,找到一个该图含有m 个顶点的子图,并且让这个子图的Ratio 值在所有m 个顶点的树中最小。 解析: 因为数据量不大,先用dfs枚举搭配出m个子节点,算出点和,然后套个prim算出边和,每次比较大小即可。 dfs没有写好,A的老泪纵横。 错在把index在d

poj 3050 dfs + set的妙用

题意: 给一个5x5的矩阵,求由多少个由连续6个元素组成的不一样的字符的个数。 解析: dfs + set去重搞定。 代码: #include <iostream>#include <cstdio>#include <set>#include <cstdlib>#include <algorithm>#include <cstring>#include <cm

ural 1149. Sinus Dances dfs

1149. Sinus Dances Time limit: 1.0 second Memory limit: 64 MB Let  An = sin(1–sin(2+sin(3–sin(4+…sin( n))…) Let  Sn = (…( A 1+ n) A 2+ n–1) A 3+…+2) An+1 For given  N print  SN Input One

hdu 6198 dfs枚举找规律+矩阵乘法

number number number Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Problem Description We define a sequence  F : ⋅   F0=0,F1=1 ; ⋅   Fn=Fn

三相直流无刷电机(BLDC)控制算法实现:BLDC有感启动算法思路分析

一枚从事路径规划算法、运动控制算法、BLDC/FOC电机控制算法、工控、物联网工程师,爱吃土豆。如有需要技术交流或者需要方案帮助、需求:以下为联系方式—V 方案1:通过霍尔传感器IO中断触发换相 1.1 整体执行思路 霍尔传感器U、V、W三相通过IO+EXIT中断的方式进行霍尔传感器数据的读取。将IO口配置为上升沿+下降沿中断触发的方式。当霍尔传感器信号发生发生信号的变化就会触发中断在中断

Jenkins 插件 地址证书报错问题解决思路

问题提示摘要: SunCertPathBuilderException: unable to find valid certification path to requested target...... 网上很多的解决方式是更新站点的地址,我这里修改了一个日本的地址(清华镜像也好),其实发现是解决不了上述的报错问题的,其实,最终拉去插件的时候,会提示证书的问题,几经周折找到了其中一遍博文

深度优先(DFS)和广度优先(BFS)——算法

深度优先 深度优先搜索算法(英语:Depth-First-Search,DFS)是一种用于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点,尽可能深的搜索树的分支,当节点v的所在边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访

文章解读与仿真程序复现思路——电力自动化设备EI\CSCD\北大核心《考虑燃料电池和电解槽虚拟惯量支撑的电力系统优化调度方法》

本专栏栏目提供文章与程序复现思路,具体已有的论文与论文源程序可翻阅本博主免费的专栏栏目《论文与完整程序》 论文与完整源程序_电网论文源程序的博客-CSDN博客https://blog.csdn.net/liang674027206/category_12531414.html 电网论文源程序-CSDN博客电网论文源程序擅长文章解读,论文与完整源程序,等方面的知识,电网论文源程序关注python

如何打造个性化大学生线上聊天交友系统?Java SpringBoot Vue教程,2025最新设计思路

✍✍计算机编程指导师 ⭐⭐个人介绍:自己非常喜欢研究技术问题!专业做Java、Python、微信小程序、安卓、大数据、爬虫、Golang、大屏等实战项目。 ⛽⛽实战项目:有源码或者技术上的问题欢迎在评论区一起讨论交流! ⚡⚡ Java实战 | SpringBoot/SSM Python实战项目 | Django 微信小程序/安卓实战项目 大数据实战项目 ⚡⚡文末获取源码 文章目录