[NOIP 2003 提高组] 侦探推理

题意

给出若干同学的证词。

已知：

恰好有 N 个人始终说假话
其余人始终说真话

要求根据这些证词判断谁可能是罪犯。

如果唯一确定，就输出名字；如果有多个可能，输出 Cannot Determine；如果一个都不可能，输出 Impossible。

思路

先看最直接的暴力：

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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168#include <bits/stdc++.h>
using namespace std;

const int MAXM = 25;
const int MAXP = 105;

int m, n, p;
string name_list[MAXM];
map<string, int> name_id;
string week_name[7] = {
    "Monday", "Tuesday", "Wednesday", "Thursday",
    "Friday", "Saturday", "Sunday"
};

struct Statement {
    int speaker;
    int type;   // 0: 无关, 1: 某人有罪, 2: 某人无罪, 3: 今天是某星期
    int who;
    int week;
};

Statement st[MAXP];

bool ends_with(const string &s, const string &suffix) {
    int n1 = (int)s.size();
    int n2 = (int)suffix.size();
    if (n1 < n2) {
        return false;
    }
    return s.substr(n1 - n2) == suffix;
}

Statement parse_statement(const string &line) {
    Statement cur;
    cur.speaker = -1;
    cur.type = 0;
    cur.who = -1;
    cur.week = -1;

    int pos = line.find(':');
    string speaker = line.substr(0, pos);
    string content = line.substr(pos + 2);

    cur.speaker = name_id[speaker];

    if (content == "I am guilty.") {
        cur.type = 1;
        cur.who = cur.speaker;
        return cur;
    }
    if (content == "I am not guilty.") {
        cur.type = 2;
        cur.who = cur.speaker;
        return cur;
    }

    if (ends_with(content, " is guilty.")) {
        string who = content.substr(0, (int)content.size() - 11);
        if (name_id.count(who)) {
            cur.type = 1;
            cur.who = name_id[who];
            return cur;
        }
    }

    if (ends_with(content, " is not guilty.")) {
        string who = content.substr(0, (int)content.size() - 15);
        if (name_id.count(who)) {
            cur.type = 2;
            cur.who = name_id[who];
            return cur;
        }
    }

    if (content.substr(0, 9) == "Today is " && content.back() == '.') {
        string day = content.substr(9, (int)content.size() - 10);
        for (int i = 0; i < 7; i++) {
            if (day == week_name[i]) {
                cur.type = 3;
                cur.week = i;
                return cur;
            }
        }
    }

    return cur;
}

bool statement_value(const Statement &s, int guilty, int today) {
    if (s.type == 1) {
        return s.who == guilty;
    }
    if (s.type == 2) {
        return s.who != guilty;
    }
    if (s.type == 3) {
        return s.week == today;
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> m >> n >> p;
    for (int i = 0; i < m; i++) {
        cin >> name_list[i];
        name_id[name_list[i]] = i;
    }

    string line;
    getline(cin, line);
    for (int i = 0; i < p; i++) {
        getline(cin, line);
        st[i] = parse_statement(line);
    }

    vector<int> answer;

    for (int guilty = 0; guilty < m; guilty++) {
        bool ok = false;

        for (int today = 0; today < 7; today++) {
            for (int mask = 0; mask < (1 << m); mask++) {
                if (__builtin_popcount((unsigned)mask) != n) {
                    continue;
                }

                bool good = true;
                for (int i = 0; i < p; i++) {
                    if (st[i].type == 0) {
                        continue;
                    }
                    bool is_liar = ((mask >> st[i].speaker) & 1);
                    bool val = statement_value(st[i], guilty, today);
                    if (is_liar == val) {
                        good = false;
                        break;
                    }
                }

                if (good) {
                    ok = true;
                    break;
                }
            }

            if (ok) {
                break;
            }
        }

        if (ok) {
            answer.push_back(guilty);
        }
    }

    if ((int)answer.size() == 0) {
        cout << "Impossible\n";
    } else if ((int)answer.size() >= 2) {
        cout << "Cannot Determine\n";
    } else {
        cout << name_list[answer[0]] << '\n';
    }

    return 0;
}

brute.cpp 会同时枚举：

谁是罪犯
今天是星期几
哪些人说谎

然后逐句检查是否满足。

这个思路肯定正确，但第三步显式枚举说谎者集合，复杂度会带一个 2^M。

正式解可以把这一层省掉。

关键观察是：

如果我们已经假设好了：

罪犯是谁
今天是星期几

那么每句“有效证词”的真假就都能直接算出来。

于是对每个人，只会出现三种状态：

他说过的有效证词全为真：这个人必须诚实
他说过的有效证词全为假：这个人必须说谎
同一个人既说真话又说假话：当前假设直接矛盾

还有一些人可能没有提供任何有效信息，他们既可以算诚实，也可以算说谎。

因此，在固定“罪犯 + 星期”的情况下，我们只需要统计：

已经确定说谎的人数 liar_cnt
已经确定诚实的人数 honest_cnt

然后判断：

text

1liar_cnt <= N <= M - honest_cnt

是否成立。

如果成立，说明可以把剩余“未定”的人适当分配到说谎组里，从而凑出恰好 N 个说谎者。

所以整体做法就是：

解析每句证词
枚举罪犯
对每个罪犯再枚举星期
检查当前假设是否可行
统计有多少个罪犯候选可行

代码

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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188#include <bits/stdc++.h>
using namespace std;

const int MAXM = 25;
const int MAXP = 105;
const int UNKNOWN = -1;
const int ALWAYS_TRUE = 1;
const int ALWAYS_FALSE = 0;

int m, n, p;
string name_list[MAXM];
map<string, int> name_id;

string week_name[7] = {
    "Monday", "Tuesday", "Wednesday", "Thursday",
    "Friday", "Saturday", "Sunday"
};

struct Statement {
    int speaker;
    int type;   // 0: 无关, 1: 某人有罪, 2: 某人无罪, 3: 今天是某星期
    int who;
    int week;
};

Statement st[MAXP];

bool ends_with(const string &s, const string &suffix) {
    int n1 = (int)s.size();
    int n2 = (int)suffix.size();
    if (n1 < n2) {
        return false;
    }
    return s.substr(n1 - n2) == suffix;
}

Statement parse_statement(const string &line) {
    Statement cur;
    cur.speaker = -1;
    cur.type = 0;
    cur.who = -1;
    cur.week = -1;

    int pos = line.find(':');
    string speaker = line.substr(0, pos);
    string content = line.substr(pos + 2);

    cur.speaker = name_id[speaker];

    if (content == "I am guilty.") {
        cur.type = 1;
        cur.who = cur.speaker;
        return cur;
    }
    if (content == "I am not guilty.") {
        cur.type = 2;
        cur.who = cur.speaker;
        return cur;
    }

    if (ends_with(content, " is guilty.")) {
        string who = content.substr(0, (int)content.size() - 11);
        if (name_id.count(who)) {
            cur.type = 1;
            cur.who = name_id[who];
            return cur;
        }
    }

    if (ends_with(content, " is not guilty.")) {
        string who = content.substr(0, (int)content.size() - 15);
        if (name_id.count(who)) {
            cur.type = 2;
            cur.who = name_id[who];
            return cur;
        }
    }

    if (content.substr(0, 9) == "Today is " && content.back() == '.') {
        string day = content.substr(9, (int)content.size() - 10);
        for (int i = 0; i < 7; i++) {
            if (day == week_name[i]) {
                cur.type = 3;
                cur.week = i;
                return cur;
            }
        }
    }

    return cur;
}

// 返回这句话在当前“罪犯 + 星期”假设下是真还是假。
bool statement_value(const Statement &s, int guilty, int today) {
    if (s.type == 1) {
        return s.who == guilty;
    }
    if (s.type == 2) {
        return s.who != guilty;
    }
    if (s.type == 3) {
        return s.week == today;
    }
    return true;
}

bool check_candidate(int guilty) {
    for (int today = 0; today < 7; today++) {
        int person_state[MAXM];
        for (int i = 0; i < m; i++) {
            person_state[i] = UNKNOWN;
        }

        bool bad = false;

        for (int i = 0; i < p; i++) {
            if (st[i].type == 0) {
                continue;
            }

            bool val = statement_value(st[i], guilty, today);
            int want = val ? ALWAYS_TRUE : ALWAYS_FALSE;
            int sp = st[i].speaker;

            if (person_state[sp] == UNKNOWN) {
                person_state[sp] = want;
            } else if (person_state[sp] != want) {
                bad = true;
                break;
            }
        }

        if (bad) {
            continue;
        }

        int liar_cnt = 0;
        int honest_cnt = 0;
        for (int i = 0; i < m; i++) {
            if (person_state[i] == ALWAYS_FALSE) {
                liar_cnt++;
            } else if (person_state[i] == ALWAYS_TRUE) {
                honest_cnt++;
            }
        }

        if (liar_cnt <= n && n <= m - honest_cnt) {
            return true;
        }
    }

    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> m >> n >> p;
    for (int i = 0; i < m; i++) {
        cin >> name_list[i];
        name_id[name_list[i]] = i;
    }

    string line;
    getline(cin, line);
    for (int i = 0; i < p; i++) {
        getline(cin, line);
        st[i] = parse_statement(line);
    }

    vector<int> candidates;
    for (int guilty = 0; guilty < m; guilty++) {
        if (check_candidate(guilty)) {
            candidates.push_back(guilty);
        }
    }

    if ((int)candidates.size() == 0) {
        cout << "Impossible\n";
    } else if ((int)candidates.size() >= 2) {
        cout << "Cannot Determine\n";
    } else {
        cout << name_list[candidates[0]] << '\n';
    }

    return 0;
}

复杂度

枚举 M 个罪犯，7 个星期，每次线性扫描 P 句证词。

所以时间复杂度是：

text

1O(M * 7 * P)

空间复杂度是 $O(M + P)$ 。

总结

这题的关键不是去枚举“谁说谎”，而是先枚举较小的外层假设：

罪犯是谁
今天是星期几

然后让每句证词自动去约束说话人的身份。

这样就把指数级枚举压成了线性检查。

[NOIP 2003 提高组] 侦探推理

目录

题意

思路

代码

复杂度

总结