Home PAT 1148 Werewolf - Simple Version
Post
Cancel

PAT 1148 Werewolf - Simple Version

Link

wolf[i]=0 表示这个玩家的状态不确定, wolf[i]=1 表示这个玩家是狼, wolf[i]=2 表示这个玩家是人.

最外面的两层循环枚举两个 liars, 并且保证 i<j. 首先判断这两个 liars 的言论是否相悖, 是就直接 continue. 判断方法是: 如果 liar iabs(a[j]) 是狼, 则记录 abs(a[j]) 是人, 即 wolf[abs(a[j])]=2; 如果 liar iabs(a[j]) 是人, 则记录 abs(a[j]) 是狼, 即 wolf[abs(a[j])]=1. 如果 liar jabs(a[i]) 是狼, 而此前在 i 那里已经判断 abs(a[i]) 真的是狼, 说明 j 没说谎, 这就出现了悖论, 直接 continue, 否则就记录 abs(a[i]) 不是狼, 即 wolf[abs(a[i])]=2; 另一种情况同理.

两个 liars 判定完毕之后, 再对另外 k-2 个人进行判断. 按理来说, 他们说的都是真话, 那么就按照他们说的话更新 wolf. 但是, 如果他们所说的某个人在此之前已经被判断过并且 wolf 值还和他们描述的相反, 就直接 break, 进行下一组 liars 的判断.

如果上述的一切都顺利进行了, 说明这 k 个人所说的话不包含悖论, 现在就可以判断是否符合条件了: 只有两个 liars, 并且两个狼人中只有一个人是 liar. 首先遍历一遍 wolf 数组, 如果 wolf 值是 1 就放进 ans 中. 此时, 如果 ans 中有两个元素, 就满足了有两个狼人的条件, 接下来就可以判断这两个狼人是否满足一个是 liar 而另一个不是; 如果 ans 中只有一个或零个元素, 就需要在那些状态不确定的狼人中寻找编号最小的成为狼人, 因为他们无论是不是狼人都不会出现悖论 (本来就状态不确定嘛). 在这一步中, 首先排除掉 wolf[i]==2&&wolf[j]==2 的情况, 因为他们都已经确定不是狼人了, 就不符合题目规则了. 然后再分类讨论:

  • ans 中有零个元素: 说明 wolf 要么是 0, 要么是 2. 如果 wolf[i]==0, 则果断地将 i 加入到 ans 中, 并将 wolf[i] 更改为 1, 此时 j 就不用管了 (不能是 1, 保持它原来的值就好); 如果 wolf[i]==2, 则 wolf[j] 一定是 0 (因为 wolf[i]==2&&wolf[j]==2 的情况在前面已经排除了), 因此只需要将 j 加入到 ans 中, 并将 wolf[j] 更改为 1. 这两种情况必然会发生一个, 因此现在 ans 中就一定有了一个元素. 接下来, 再在剩下的 k-2 个数中寻找编号最小的那个 wolf 值为 0 的数, 将其加入到 ans 中.
  • ans 中有一个元素: 如果 wolf[i]wolf[j] 中已经有一个是 1 了, 就去剩下的 k-2 个数中找编号最小的那个 wolf 值为 0 的数, 将其加入到 ans 中; 否则, 就将 ijwolf 值为 0 的那一个加入到 ans 中 (如果两个都为 0 就取较小的 i).

AC 代码如下:

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
#include <cmath>
using namespace std;
int n;
int a[110],wolf[110];//0-unvisited;1-is;2-not
vector<int>ans;
vector<pair<int,int>>anss;
int main() {
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%d",&a[i]);
    bool hasSolution=false;
    for(int i=1;i<n;++i){
        for(int j=i+1;j<=n;++j){
            memset(wolf,0,sizeof(wolf));
            ans.clear();
            wolf[abs(a[i])]=a[i]<0?2:1;
            if(a[j]<0){
                if(wolf[-a[j]]==1) continue;
                wolf[-a[j]]=2;
            }else{
                if(wolf[a[j]]==2) continue;
                wolf[a[j]]=1;
            }
            bool flag=true;
            for(int k=1;k<=n;++k)
                if(k!=i&&k!=j){
                    if(a[k]<0){
                        if(wolf[-a[k]]==2){
                            flag=false;
                            break;
                        }
                        wolf[-a[k]]=1;
                    }else{
                        if(wolf[a[k]]==1){
                            flag=false;
                            break;
                        }
                        wolf[a[k]]=2;
                    }
                }
            if(wolf[i]==2&&wolf[j]==2) continue;
            if(flag){
                for(int k=1;k<=n;++k)
                    if(wolf[k]==1)
                        ans.push_back(k);
                if(ans.size()==0){
                    if(wolf[i]==0){
                        wolf[i]=1;
                        ans.push_back(i);
                    }else if(wolf[j]==0){
                        wolf[j]=1;
                        ans.push_back(j);
                    }else continue;
                    for(int k=1;k<=n;++k)
                        if(k!=i&&k!=j&&wolf[k]==0){
                            wolf[k]=1;
                            ans.push_back(k);
                            break;
                        }
                }
                if(ans.size()==1){
                    if(wolf[i]==0&&wolf[j]!=1){
                        wolf[i]=1;
                        ans.push_back(i);
                    }else if(wolf[i]==2&&wolf[j]==0){
                        wolf[j]=1;
                        ans.push_back(j);
                    }else{
                        for(int k=1;k<=n;++k)
                            if(k!=i&&k!=j&&wolf[k]==0){
                                wolf[k]=1;
                                ans.push_back(k);
                                break;
                            }
                    }
                }
                if(ans.size()==2&&((wolf[i]==1&&wolf[j]!=1)||(wolf[i]!=1&&wolf[j]==1)))
                    anss.push_back({min(ans[0],ans[1]),max(ans[0],ans[1])});
            }
        }
    }
    if(anss.size()==0) printf("No Solution\n");
    else{
        sort(anss.begin(),anss.end());
        printf("%d %d\n",anss[0].first,anss[0].second);
    }
    return 0;
}
This post is licensed under CC BY 4.0 by the author.

PAT 1150 Travelling Salesman Problem

PAT 1153 Decode Registration Card of PAT