P1039 侦探推理

骑猪看日落 2021-12-22 15:56 196阅读 0赞

刚学OI的时候觉得难得要死。现在看……

因为我们不知道谁是罪犯和今天是星期几，所以我们全都枚举一下，然后判定答案。

这样思路是不是就很显然了？

先处理下证词那些字符串。然后对每个答案进行判定。判定出说谎人数不符合或又说真话又说假话等情况，就直接判false。

然后对于每一个人，只需要有一天满足是凶手，就说明这个人是凶手。

所以思路讲到这里就完了。

--------------------

接下来是最难的实现环节：

首先面对的是所有的证词。应该认识到有的人会划水，有的人会提供有用的信息。

划水的方式有很多种：

1.  说些什么`I AK IOI.`
2.  说些什么`I love you.`
3.  说些什么`I am guity.`
4.  说些什么`I am not guilty. Am I?????`
5.  说些什么`Today is Christmas-Day.`

甚至还有人的名字叫做`I`。所以还需要区分`I is guilty.`和`I am guilty.`。

这里最好用`std::stringstream`读一整行，并且可以用`ss >> str`的返回值来判断是否后面已经没有字符可读。

说到底就是细心点实现了吧。

然后面对的是判定部分。

注意到每个人，最初都无法判断，根据一些话可以判断是说谎还是不说谎。

同样，每个人从一而终，如果又说谎又诚实就return false。

并且，那些无法判断的人，是可以认为说谎，也可以认为不说谎的。即我们最后求出的说谎人数是个区间来的。如果最后人数满足区间就可以return true了。

下数据调这种模拟的代码是很锻炼码力的，做这道题的时候一定会经历到的。

代码：

#include<bits/stdc++.h>
    using std::cin;
    using std::cout;
    using std::endl;
    using std::string;
    using std::stringstream;
    const int maxn = 25, maxm = 105;
    int m, n, p;
    string name[maxn];
    std::map<string,int> mmp;
    std::vector<std::pair<int,int> > proof[maxn];
    int fake[maxn];
    bool check(int who, int now) {
        memset(fake, -1, sizeof fake);
        for(int i = 1; i <= m; i++) {
            for(auto it: proof[i]) {
                if(it.first == 1) {
                    if(who == i) {
                        if(fake[i] == -1) fake[i] = 0;
                        else if(fake[i] == 1) return false;
                    } else {
                        if(fake[i] == -1) fake[i] = 1;
                        else if(fake[i] == 0) return false;
                    }
                } else if(it.first == 2) {
                    if(who != i) {
                        if(fake[i] == -1) fake[i] = 0;
                        else if(fake[i] == 1) return false;
                    } else {
                        if(fake[i] == -1) fake[i] = 1;
                        else if(fake[i] == 0) return false;
                    }
                } else if(it.first == 3) {
                    if(who == it.second) {
                        if(fake[i] == -1) fake[i] = 0;
                        else if(fake[i] == 1) return false;
                    } else {
                        if(fake[i] == -1) fake[i] = 1;
                        else if(fake[i] == 0) return false;
                    }
                } else if(it.first == 4) {
                    if(who != it.second) {
                        if(fake[i] == -1) fake[i] = 0;
                        else if(fake[i] == 1) return false;
                    } else {
                        if(fake[i] == -1) fake[i] = 1;
                        else if(fake[i] == 0) return false;
                    }
                } else if(it.first == 5) {
                    if(it.second == now) {
                        if(fake[i] == -1) fake[i] = 0;
                        else if(fake[i] == 1) return false;
                    } else {
                        if(fake[i] == -1) fake[i] = 1;
                        else if(fake[i] == 0) return false;
                    }
                }
            }
        }
        int cnt = 0, help = 0;
        for(int i = 1; i <= m; i++) {
            if(fake[i] == 1) cnt++;
            else if(fake[i] == -1) help++;
        }
        //cout << cnt << ' ' << help << endl;
        if(cnt <= n && n <= cnt + help) return true;
        return false;
    }
    void solve() {
        int cnt = 0, id = -1;
        for(int i = 1; i <= m; i++) {
            bool flag = false;
            for(int j = 0; j >= -6; j--) {
                int temp = check(i, j);
                //printf("(%d %d): %d\n", i, j, temp);
                flag |= temp;
            }
            if(flag) {
                cnt++; id = i;
            }
        }
        if(cnt == 1) {
            cout << name[id] << endl;
        } else if(cnt == 0) {
            cout << "Impossible" << endl;
        } else {
            cout << "Cannot Determine" << endl;
        }
    }
    void init() {
        cin >> m >> n >> p;
        string temp;
        for(int i = 1; i <= m; i++) {
            cin >> name[i]; mmp[name[i]] = i;
        }
        mmp["Sunday"] = 0;
        mmp["Monday"] = -1; mmp["Tuesday"] = -2;
        mmp["Wednesday"] = -3; mmp["Thursday"] = -4;
        mmp["Friday"] = -5; mmp["Saturday"] = -6;
        getline(cin, temp);
        for(int i = 1; i <= p; i++) {
            getline(cin, temp);
            stringstream ss(temp);
            ss >> temp; temp.pop_back();
            int idx = mmp[temp];
            ss >> temp;
            if(temp == "I") {
                ss >> temp;
                if(temp == "am") {
                    ss >> temp;
                    if(temp == "guilty.") {
                        if(ss >> temp) continue;
                        proof[idx].push_back(std::make_pair(1, 0));
                    } else if(temp == "not") {
                        ss >> temp;
                        if(temp != "guilty.") continue;
                        if(ss >> temp) continue;
                        proof[idx].push_back(std::make_pair(2, 0));
                    } else continue;
                } else if(temp == "is") {
                    if(!mmp.count("I")) continue;
                    int id = mmp["I"];
                    ss >> temp;
                    if(temp == "guilty.") {
                        if(ss >> temp) continue;
                        proof[idx].push_back(std::make_pair(3, id));
                    } else if(temp == "not") {
                        ss >> temp;
                        if(temp != "guilty.") continue;
                        if(ss >> temp) continue;
                        proof[idx].push_back(std::make_pair(4, id));
                    } else continue;
                } else continue;
            } else if(temp == "Today") {
                ss >> temp; ss >> temp; temp.pop_back();
                int id = mmp[temp];
                if(ss >> temp) {
                    //cout << "GG" << endl;
                    continue;
                }
                proof[idx].push_back(std::make_pair(5, id));
                //cout << 5 << ' ' << id << endl;
            } else {
                if(!mmp.count(temp)) continue;
                int id = mmp[temp];
                ss >> temp;
                if(temp != "is") continue;
                ss >> temp;
                if(temp == "guilty.") {
                    if(ss >> temp) {
                        //cout << "GG" << endl;
                        continue;
                    }
                    proof[idx].push_back(std::make_pair(3, id));
                    //cout << 3 << ' ' << id << endl;
                } else if(temp == "not") {
                    ss >> temp;
                    if(ss >> temp) {
                        //cout << "GG" << endl;
                        continue;
                    }
                    proof[idx].push_back(std::make_pair(4, id));
                    //cout << 4 << ' ' << id << endl;
                }
            }
        }
    }
    int main() {
        init();
        solve();
        return 0;
    }

转载于:https://www.cnblogs.com/Garen-Wang/p/10959556.html