[NOIP2003-提高] 侦探推理

形式化题目

有 $M$ （ $1 \leqslant M \leqslant 20$ ）个人，其中恰好 $N$ （ $1 \leqslant N \leqslant M$ ）个人始终说谎，其余人始终说真；凶手只有一人。给出 $P$ （ $1 \leqslant P \leqslant 100$ ）条证词，每条形如 说话者: 证词。

只有 5 类证词进入推理：

编号	句式	含义
①	`I am guilty.`	说话者自认是凶手
②	`I am not guilty.`	说话者否认作案
③	`<名字> is guilty.`	指认`<名字>`是凶手
④	`<名字> is not guilty.`	替`<名字>`洗清嫌疑
⑤	`Today is <星期>.`	断言今天是星期几

其余所有句子都是闲话，对推理毫无影响。要求判断：若能唯一确定凶手则输出名字；若有多人可能是凶手输出 Cannot Determine；若没有任何人可能是凶手输出 Impossible。

正解

思路

朴素想法。 谁真谁假有 $2^M$ 种可能，逐一检查每一种下证词是否自洽，效率太低。但仔细想：证词真假其实不是由"谁真谁假"决定的，而是由事实决定的——一旦知道了"凶手是谁"和"今天星期几"，每一句有效证词的真假就立即确定，说真/说谎的身份反而被证词推出来。未知事实只有两个：罪犯（ $M$ 种）和星期（ $7$ 种），所以只需枚举 $M \times 7 \leqslant 140$ 个假设。

验证一个假设。 固定假设（罪犯 = suspect，今天 = day）后，逐句扫描证词：

有效证词与假设一致（如 suspect 说的 “I am guilty.”、“Today is Monday.” 而假设正是 Monday）→ 说话者必须说真话；
有效证词与假设冲突（如别人说的 “I am guilty.”）→ 说话者必须说谎；
闲话 → 不产生任何约束。

扫描中维护两个集合：已确定说真的 honest 和已确定说假的 liars。若某句要求说话者真但他已在 liars（或反之），该假设直接作废。

名额恰好是 N。 设最终 $|\text{liars}| = t_2$ 、 $|\text{honest}| = t_1$ ，还有 $f$ 个只说过闲话的人——他们身份完全自由，想真想假都行。于是假设自洽当且仅当说谎者能恰好凑成 $N$ 个：

t_2 \leqslant N \leqslant t_2 + f

注意是"恰好"而不是"不超过"： $t_2 < N$ 时可以靠自由人补足，但 $t_2 + f < N$ 就凑不齐了。这正是本题最容易漏掉的坑——下面 logic0 样例里 GUILTY 就是靠一句闲话保住了说谎名额。

候选与输出。 每个通过验证的假设把它的 suspect 记入候选集（去重）。候选为空输出 Impossible；多于一人输出 Cannot Determine；否则输出唯一名字。

代码

cpp

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
96
97
98
99
100
101
102
103
104
105
106
107
108
109/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-10 11:30
 * update_at: 2026-10-10 11:30
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int m, n, p;
vector<string> people;
vector<pair<string, string> > statements;   // (说话者, 原句)

const char* MONDAY[7] = {"Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday", "Sunday"};

// 证词立场：0 表示与假设一致，1 表示冲突，2 表示闲话
int sentence_opinion(const string& sentence, const string& suspect, const string& speaker, const string& day) {
    if (sentence == "I am guilty." || sentence == "I am GUILTY.")
        return (speaker == suspect) ? 0 : 1;
    if (sentence == "I am not guilty.")
        return (speaker != suspect) ? 0 : 1;
    if (sentence.size() > 11 && sentence.substr(sentence.size() - 11) == " is guilty.") {
        string name = sentence.substr(0, sentence.size() - 11);
        return (name == suspect) ? 0 : 1;
    }
    if (sentence.size() > 15 && sentence.substr(sentence.size() - 15) == " is not guilty.") {
        string name = sentence.substr(0, sentence.size() - 15);
        return (name != suspect) ? 0 : 1;
    }
    if (sentence.size() > 9 && sentence.substr(0, 9) == "Today is ") {
        string d = sentence.substr(9);
        if (!d.empty() && d.back() == '.') d.pop_back();
        return (d == day) ? 0 : 1;
    }
    return 2;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string firstline;
    getline(cin, firstline);
    stringstream ss(firstline);
    ss >> m >> n >> p;
    for (int i = 0; i < m; i++) {
        string name;
        getline(cin, name);
        people.push_back(name);
    }
    for (int i = 0; i < p; i++) {
        string line;
        getline(cin, line);
        size_t pos = line.find(":");
        string speaker = line.substr(0, pos);
        string sentence = line.substr(pos + 1);
        // 去首尾空白
        int a = 0, b = (int)sentence.size();
        while (a < b && isspace((unsigned char)sentence[a])) a++;
        while (b > a && isspace((unsigned char)sentence[b - 1])) b--;
        sentence = sentence.substr(a, b - a);
        statements.push_back(make_pair(speaker, sentence));
    }

    vector<string> suspects;
    for (int si = 0; si < m; si++) {
        const string& suspect = people[si];
        bool found = false;
        for (int di = 0; di < 7 && !found; di++) {
            const string& day = MONDAY[di];
            set<string> honest, liars;
            bool ok = true;
            for (int i = 0; i < p && ok; i++) {
                int opinion = sentence_opinion(statements[i].second, suspect, statements[i].first, day);
                if (opinion == 2) continue;
                bool liar = (opinion == 1);
                if ((liars.count(statements[i].first) && !liar) ||
                    (honest.count(statements[i].first) && liar)) {
                    ok = false;
                    break;
                }
                if (liar) liars.insert(statements[i].first);
                else honest.insert(statements[i].first);
            }
            if (!ok) continue;
            set<string> speakers;
            for (int i = 0; i < p; i++) speakers.insert(statements[i].first);
            int free = 0;
            for (set<string>::iterator it = speakers.begin(); it != speakers.end(); ++it)
                if (!honest.count(*it) && !liars.count(*it)) free++;
            if ((int)liars.size() <= n && n <= (int)liars.size() + free) {
                suspects.push_back(suspect);
                found = true;
            }
        }
    }

    set<string> unique_suspects(suspects.begin(), suspects.end());
    if (suspects.empty()) {
        cout << "Impossible\n";
    } else if (unique_suspects.size() > 1) {
        cout << "Cannot Determine\n";
    } else {
        cout << suspects[0] << "\n";
    }
    return 0;
}

python

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#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-07-05 22:00
# update_at: 2026-07-05 22:00

import sys

# 枚举量：罪犯 20 种 × 星期 7 种 = 140 个假设，逐一验证，复杂度 O(140·P)
MONDAY = ("Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday", "Sunday")
JUNK, OK = None, 0              # 证词语义：JUNK = 闲话不入推理，OK = 与当前假设一致


def sentence_opinion(sentence: str, suspect: str, speaker: str, day: str) -> int | None:
    """把一句证词翻译成它在当前假设下的立场：返回 1 表示与假设冲突，None 表示闲话。"""
    if sentence in ("I am guilty.", "I am GUILTY."):      # "I am GUILTY." 是原题的经典坑
        return OK if speaker == suspect else 1            # 说话者自认罪犯
    if sentence == "I am not guilty.":
        return OK if speaker != suspect else 1            # 说话者否认作案
    if sentence.endswith(" is guilty."):
        name = sentence[:-len(" is guilty.")]
        return OK if name == suspect else 1               # 指认他人是罪犯
    if sentence.endswith(" is not guilty."):
        name = sentence[:-len(" is not guilty.")]
        return OK if name != suspect else 1               # 替他人洗清嫌疑
    if sentence.startswith("Today is "):                  # 星期断言：同一天为真，否则为假
        return OK if sentence[9:-1] == day else 1
    return JUNK                                           # 其余闲话（含相似句式）不入推理


def solve() -> None:
    raw = sys.stdin.read().splitlines()          # 证词不能按词切，整个输入按行处理
    it = iter(raw[0].split())
    m, n, p = int(next(it)), int(next(it)), int(next(it))
    people = raw[1:1 + m]

    # 证词按行读：冒号前是说话者，冒号后是原句（闲话里可能有奇怪内容，不能按词切）
    statements = [(line.split(":", 1)[0], line.split(":", 1)[1].strip())
                  for line in raw[1 + m:1 + m + p]]

    suspects = []                          # 每个通过验证的假设对应的罪犯候选
    for suspect in people:
        for day in MONDAY:
            honest: set[str] = set()       # 当前假设下已确定说真话的人
            liars: set[str] = set()        # 当前假设下已确定说谎的人
            ok = True                      # 该假设是否自洽（无身份冲突且能凑满 N）
            for speaker, sentence in statements:
                opinion = sentence_opinion(sentence, suspect, speaker, day)
                if opinion is JUNK:        # 闲话谁说都一样，不约束任何人的身份
                    continue
                liar = opinion == 1        # 立场与假设冲突的人必须说谎，否则必须说真
                if (speaker in liars and not liar) or (speaker in honest and liar):
                    ok = False             # 同一个人被同时定为既真又假，假设作废
                    break
                (liars if liar else honest).add(speaker)
            # 空闲名额：只说闲话的人身份自由，补足"说谎者恰好 N 人"
            free = len({w for w, _ in statements}) - len(honest) - len(liars)
            if ok and len(liars) <= n <= len(liars) + free:
                suspects.append(suspect)
                break                      # 该人已有自洽假设，不必再试其余星期
    if not suspects:
        print("Impossible")                # 没有任何假设自洽
    elif len(set(suspects)) > 1:
        print("Cannot Determine")          # 多人可能是罪犯
    else:
        print(suspects[0])


if __name__ == "__main__":
    solve()

复杂度

时间： $O(M \cdot 7 \cdot P \cdot L)$ ，其中 $L \leqslant 250$ 是证词长度，即约 $140 \times 100$ 次整句匹配，远在 1 秒以内。
空间： $O(P \cdot L)$ ，存下全部证词。

图示解析

单个假设的验证流程

下面展示枚举到一个假设（罪犯 = suspect，今天 = day）后的验证过程：

flowchart TD
    A["假设 suspect 是凶手，今天是 day"] --> B{"逐句扫描证词"}
    B -->|"有效且与假设一致"| C["说话者必须真：加入 honest"]
    B -->|"有效且与假设冲突"| D["说话者必须假：加入 liars"]
    B -->|"闲话"| E["跳过，不约束身份"]
    C --> F{"同一人既真又假？"}
    D --> F
    E --> F
    F -->|"是"| G["假设作废"]
    F -->|"否"| H{"t2 ≤ N ≤ t2 + 自由人数？"}
    H -->|"是"| I["自洽：suspect 进入候选集"]
    H -->|"否"| G

观察重点：闲话分支虽然"跳过"，但说闲话的人会被计入自由名额 $f$ ——闲话并非毫无作用，它给了这个人自由选择真假的权利。名额不等式在最后统一检查，而不是边扫边数。

样例推演：为什么 `GUILTY` 说谎、`HELLO` 也能凑数

以原题样例（M=3, N=1）为基础稍作变体，看 logic0 测点同款的名单分配：

人	说过的话	身份	说谎？
HELLO	`What is your name?`（闲话）、`I am not guilty.`	真话	否（假设 HELLO 是凶手，此句为真）
GUILTY	`I am GUILTY.`、`Are you guilty?`	说谎	是（自认凶手与假设冲突）

假设"凶手是 HELLO"下：honest = {HELLO}，liars = {GUILTY}（I am GUILTY. 按变体识别成"自认凶手"），自由名额 $f = 0$ ，名额检查 $1 \leqslant N \leqslant 1$ 恰好成立。反过来若把 I am GUILTY. 当成闲话，GUILTY 就变成自由人， $t_2 = 0$ 靠补足也能凑出 $N=1$ ——表面上结论相同，但换一个测点（比如再补一句 GUILTY 的闲话）名额判定就会出错；数据里专门放了这类句子来区分"识别变体"和"漏识别"两种写法。

总结

核心转换：不枚举"谁真谁假"（ $2^M$ ），枚举"事实"——凶手与星期（ $M \times 7$ ），证词真假随之确定。
验证规则：有效证词定说话者真假，闲话留自由名额；检查"无身份冲突 + $t_2 \leqslant N \leqslant t_2 + f$ "。
经典坑：说谎人数是"恰好 $N$ "；I am GUILTY. 这类大小写变体要识别；含 guilty 字样的句子未必是有效证词。