18年秋季第一题 PAT甲级 1148 Werewolf - Simple Version (20分) 剪不断理还乱的逻辑

谁践踏了优雅 2023-07-04 11:04 14阅读 0赞

# 题目 #

Werewolf（狼人杀） is a game in which the players are partitioned into two parties: the werewolves and the human beings. Suppose that in a game,

*  player \#1 said: "Player \#2 is a werewolf.";
 *  player \#2 said: "Player \#3 is a human.";
 *  player \#3 said: "Player \#4 is a werewolf.";
 *  player \#4 said: "Player \#5 is a human."; and
 *  player \#5 said: "Player \#4 is a human.".

Given that there were 2 werewolves among them, at least one but not all the werewolves were lying, and there were exactly 2 liars. Can you point out the werewolves?

Now you are asked to solve a harder version of this problem: given that there were N players, with 2 werewolves among them, at least one but not all the werewolves were lying, and there were exactly 2 liars. You are supposed to point out the werewolves.

### Input Specification: ###

Each input file contains one test case. For each case, the first line gives a positive integer N (5≤N≤100). Then N lines follow and the i-th line gives the statement of the i-th player (1≤i≤N), which is represented by the index of the player with a positive sign for a human and a negative sign for a werewolf.

### Output Specification: ###

If a solution exists, print in a line in ascending order the indices of the two werewolves. The numbers must be separated by exactly one space with no extra spaces at the beginning or the end of the line. If there are more than one solution, you must output the smallest solution sequence -- that is, for two sequences A=a\[1\],...,a\[M\] and B=b\[1\],...,b\[M\], if there exists 0≤k<M such that a\[i\]=b\[i\] (i≤k) and a\[k+1\]<b\[k+1\], then A is said to be smaller than B. In case there is no solution, simply print `No Solution`.

### Sample Input 1: ###

5
    -2
    +3
    -4
    +5
    +4

### Sample Output 1: ###

1 4

### Sample Input 2: ###

6
    +6
    +3
    +1
    -5
    -2
    +4

### Sample Output 2 (the solution is not unique): ###

1 5

### Sample Input 3: ###

5
    -2
    -3
    -4
    -5
    -1

### Sample Output 3: ###

No Solution

# 难点 #

一眼看上去逻辑可能会有点复杂，但是你得知道第一题一般来说就是思路为王的，不会用到特别难的知识（不会有树、图、搜索算法等，那都是第三第四题的考点了）。 只要你能顺利写出伪代码，那离AC就很近了！

## 伪代码可以这么想： ##

这道题的输入当作一个大小为n的数组，如果我们从小到大枚举两个狼人的编号，他们其中有个人说谎，然后再这个基础上遍历整个数组，根据数组的内容来计算说谎的人数，如果符合“只有一个人说谎”，那这两个狼人的编号就是合适的。

## 对应的伪代码就是： ##

//如果x、y是狼人的返回真
    bool f(x,y){//假设x,y为狼人的编号，其中x是说谎的
        int liar=0;//说谎的人数
        for(i){
            if(i是狼人x){
                if(i说的人是狼人){
                    if(说是狼人)返回假;
                }else if(i说的人是平民){
                    if(说是平民)返回假;
                }
            }else if(i是狼人y){
                if(i说的人是狼人){
                    if(说是平民)返回假;
                }else if(i说的人是平民){
                    if(说是狼人)返回假;
                }
            }else{//i是平民
                if(i说的人是狼人){
                    if(说是平民)liar++;
                    if(liar>=2)返回假;
                }else if(i说的人是平民){
                    if(说是狼人)liar++;
                    if(liar>=2)返回假;
                }
            }   
        }
        返回真;
    }
    
    
    //main()内语句
    for(i){
        for(j){
            生成两个狼人的编号i,j;
            如果f(i,j)或者f(j,i)成立，那么输出这组解并返回;
        }
    }
    输出无解;

# 满分代码： #

#include<iostream>
    int a[105],n;
    bool f(int x,int y){
        int liar = 0;
        for(int i = 1;i <= n;i++){
            int z = abs(a[i]);
            if(i == x){
                if(z != x && z != y){
                    if(a[i] > 0)return false;
                }else if(z == x || z == y){
                    if(a[i] < 0)return false;
                }
            }else if(i == y){
                if(z != x && z != y){
                    if(a[i] < 0)return false;
                }else if(z ==x || z == y){
                    if(a[i] > 0)return false;
                }
            }else{
                if(z != x && z != y){
                    if(liar < 2 && a[i] < 0)liar++;
                    if(liar >= 2)return false;
                }else if(z == x || z == y){
                    if(liar < 2 && a[i] > 0)liar++;
                    if(liar >= 2)return false;
                }
            }
        }
        return true;
    }
    
    int main(){
        scanf("%d\n",&n);
        for(int i = 1;i <= n;i++){
            scanf("%d",&a[i]);
        }
        for(int i = 1;i <= n-1;i++){
            for(int j = i+1;j <= n;j++){
                if(f(i,j) || f(j,i)){
                    printf("%d %d",i,j);
                    return 0;
                }
            }
        }
        printf("No Solution");
        return 0;
    }

喜欢我的文章请给我点个赞哦，谢谢！

题目地址：[https://pintia.cn/problem-sets/994805342720868352/problems/1038429808099098624][https_pintia.cn_problem-sets_994805342720868352_problems_1038429808099098624]

[https_pintia.cn_problem-sets_994805342720868352_problems_1038429808099098624]: https://pintia.cn/problem-sets/994805342720868352/problems/1038429808099098624