ACM/ICPC 2010 天津现场赛 I’m Telling the Truth 题解
这道题的题意是，一些学生说出他们各自的排名范围（不存在并列），然后有的学生说谎了，结果就产生了矛盾。比如有 3 个学生分别都说自己的排名是 1 ~ 2 名，那么肯定至少有一个学生说谎。题目要求计算出最多有几个学生说了真话，并且把那些说真话的学生序号输出。如果有多种情况，输出字典序最高的那种。
数据范围，最多有 100 cases, 学生最多 60 名。排名的话，以区间 [x, y] 表示，其中 1 ≤ x ≤ y ≤ 100000.
开始看这个数据，想起队友 WH 说的，如果有那些 30 啊 60 啊之类的东西，就想想是不是动规，因为那些 30 或者 60 刚好是 32 位整型和 64 位整型能表示的东西。
然后我看到区间，而且范围还挺大，就不禁想到线段树。
后来还是没有想法。Google 了一下，发现前人居然是用二分图匹配来写的。感觉这还是有点勉强啊，而且出题者设计的数据也太容易让人想歪了。
源代码如下：
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 <set> #include <vector> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef vector<vector<int> > graph_t; typedef vector<int> int_array; typedef set<int> int_set; const int N = 111111; // Max rank. const int M = 100; // Students. graph_t graph; int match_student[N]; int_set rank_occupied; bool hungarian(int student) { for (int i = 0; i < graph[student].size(); ++i) { int rank = graph[student][i]; if (rank_occupied.find(rank) != rank_occupied.end()) continue; // If rank occupied this time. rank_occupied.insert(rank); if (match_student[rank] == -1 || // If the rank is not assigned. hungarian(match_student[rank])) // Or someone can go elsewhere. { match_student[rank] = student; return true; } } return false; } inline void init(int student_count) { graph.clear(); graph.resize(student_count + 1); memset(match_student, -1, sizeof match_student); } int main() { // freopen("input.txt", "r", stdin); int T, n; scanf("%d", &T); while (T--) { scanf("%d", &n); init(n); for (int i = 0; i < n; ++i) { int x, y; scanf("%d %d", &x, &y); for ( ; x <= y; ++x) graph[i].push_back(x); } int result = 0; for (int i = n - 1; i >= 0; --i) { rank_occupied.clear(); if (hungarian(i)) ++result; } int_array scheme; scheme.reserve(M); for (int i = 0; i < N; ++i) if (match_student[i] != -1) scheme.push_back(match_student[i]); sort(scheme.begin(), scheme.end()); printf("%d\n", result); if (!scheme.empty()) printf("%d", scheme[0] + 1); for (int i = 1; i < scheme.size(); ++i) printf(" %d", scheme[i] + 1); printf("\n"); } return 0; } |
