PAT 甲级 刷题日记|A 1148 Werewolf - Si

思路

这道题还是非常不错的，主要考虑几个关键点

1. 核心思想是暴力枚举。我们正常人脑的思考是去一步步从现有条件推理，找到矛盾，进而发现答案，但这对写程序是不现实的。
2. 即使是暴力枚举，也是讲究方法和技巧的。我们假设现实情况是什么（狼人分别是哪几位），再根据已有条件（每个人的发言）去推出结论（谁是撒谎者），看结论是否符合题目预设（只有一人一狼撒谎）。
3. 标号问题也很烦人，从0开始还是从1开始全篇统一，最好和题目一致， 能省去很多麻烦

代码

#include <bits/stdc++.h>
using namespace std;

const int maxn = 10000;
int slo[maxn];
int ans[maxn];
int n;

int main() {
    cin>>n;
    for (int i = 1; i <= n; i++) {
        cin>>slo[i];
    }
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            vector<int> lie, a(n + 1, 1);
            a[i] = a[j] = -1; // 假设 i和 j是狼人 
            for (int k = 1; k <= n; k++) {
                if (slo[k] * a[abs(slo[k])] < 0 ) lie.push_back(k);
                // slo k的发言 a 现实情况 <0说明发言与现实不符合，撒谎了
            }
            if (lie.size() == 2 && a[lie[0]] + a[lie[1]] == 0) {
                // 撒谎人数为2 且 一个是狼人一个是平民 
                cout<<i<<" "<<j;
                return 0;
            }
        }
    }
    cout<<"No Solution"<<endl;
}