PAT甲级1148Werewolf - Simple Version

Posted on | | Visitors:
Words count in article: 502 字 | Reading time ≈ 2 分

题目链接

https://pintia.cn/problem-sets/994805342720868352/problems/1038429808099098624

题解

题目要求

N（5到100）个玩家，其中2个狼人，只有1个狼人在撒谎（题目里说至少有1个狼人在撒谎但不是所有狼人都在撒谎……直接讲只有1个狼人在撒谎不行吗……），共有2人撒谎，请找出两个狼人

描述中+则是人类，-则是狼人

如果有解，请按增序输出狼人

如果多个解，则输出最小的

没有讲解则输出”No Solution”

思路

刚看完题时没啥思路……特别是有多个解的情况，让我以为要求出所有解，我似乎还想过枚举是谁在撒谎（得到谁在撒谎并不能很有效地得到答案……）

可以枚举狼人是谁的情况，如果与题目和输入相符（1个狼人和1个人在撒谎），则直接输出狼人（如果有多个解，从小到大枚举狼人求得的第一个解就是多个解中最小的解）

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
37
38
39
// Problem: PAT Advanced 1148
// URL: https://pintia.cn/problem-sets/994805342720868352/problems/1038429808099098624
// Tags: Math

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int main()
{
    // 获取输入
    int n;
    cin >> n;
    vector<int> statements(n+1);
    for (int i = 1; i <= n; i++)
        cin >> statements[i];
    
    for (int i = 1; i < n; i++){
        for(int j = i+1; j <= n; j++){
            // 枚举2个狼人是i和j
            vector<int> identities(n+1, 1); // 玩家身份：1代表人类，-1代表狼人
            identities[i] = identities[j] = -1; // i和j是狼人
            // 寻找撒谎的玩家
            vector<int> liars;
            for (int k = 1; k < statements.size(); k++){
                if (statements[k] * identities[abs(statements[k])] < 0)
                    liars.push_back(k);
            }
            // 判断当前枚举的狼人i和j是否符合题目要求和输入
            if (liars.size() == 2 && identities[liars[0]] + identities[liars[1]] == 0){
                cout << i << " " << j;
                return 0;
            }
        }
    }
    cout << "No Solution";
    return 0;
}

作者：@臭咸鱼

转载请注明出处：https://www.cnblogs.com/chouxianyu/

欢迎讨论和交流!