PAT 真题 | 1148 Werewolf - Simple version

这道题既然要我们找出两个狼人。那么最直达中心的求解法就是设i和j为狼人,使用二重循环遍历。 如果根据假设能推出恰好有两个说谎者(liars),那么说明满足条件,i和j就是要找的狼人。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;

const int maxn = 102;
int say[maxn];

int main()
{
int N;
scanf("%d", &N);
for(int i=1;i<=N;++i){
scanf("%d", say+i);
}
for(int i=1;i<=N;++i){
for(int j=i+1;j<=N;++j){ // suppose i,j are wolvies
vector<int> liar;
int flag[maxn];
fill(flag, flag+maxn, 1);
flag[i] = flag[j] = -1;
for(int k=1;k<=N;++k){
int wolf = abs(say[k]);
if (say[k] * flag[wolf] < 0){ // if k is liar
liar.push_back(k);
}
}
if (liar.size()==2 && flag[liar[0]]+flag[liar[1]]==0){
printf("%d %d\n", i, j);
return 0;
}
}
}
puts("No Solution");
return 0;
}

PS: 不敢再用C语言的 <math.h> 头文件了. 因为我使用 abs 函数的时候提示 error: ‘abs’ was not declared in this scope. 而我再Linux 下的 /usr/include/math.h 头文件下搜索 abs 的时候,发现真的没有这个函数!于是改用 <cmath> 或者 <algorithm> 了。从此写算法题对于c语言的头文件都不用 .h 写法了。

区块链学习笔记 Shellchain experiment

评论

You forgot to set the shortname for Disqus. Please set it in _config.yml.
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×