首页 > 代码库 > codeforces 490B.Queue 解题报告
codeforces 490B.Queue 解题报告
题目链接：http://codeforces.com/problemset/problem/490/B
题目意思：给出每个人 i 站在他前面的人的编号 ai 和后面的人的编号 bi。注意，排在第一个位置的人他前面是无人的！于是 a1 = 0。最后那个人的后面是木有人的，即 bn = 0。然后根据这些条件求出整个序列是如何排的，输出答案。
这条题卡了好久.........啊........啊........啊
首先很容易知道第二个位置的人的编号 和 倒数第二个人的位置编号。用一个aft[]数组记录，aft[ai] = bi。表示 bi 在 ai 后面。然后从第 2 个位置开始，4、6，...n-2, n 就可以根据aft[] 数组来填出奇数位置的具体id number了。然后就开始卡在如何确定第 1 个位置应该填的id number了。然后好不容易用一个 bef[] 数组来求 (bef[bi] = ai)，即从倒数第2个位置推回去直到第1个位置。赛后才发现这样只能处理 n 为偶数的情况。
这就表示一定要知道第 1 个位置具体填哪个 id number！知道之后 bef[] 数组就没必要使用了。
用一个cnt[] 数组来保存 ai 和 bi 的出现次数，通过观察可以发现，除了第 1 个和最后 1 个位置的人的 id number 的次数是 1 之外，其他位置都会出现 2 次。那么问题就是如何正确选出填在第 1 个位置的人的 id number 了。发现最后 1 个位置的人的 aft[] 是没有值的，那么如果有值，这个人就是排在第 1 个位置啦～～～～然后就可以根据 aft[] 数组来填1， 3， 5， ...， n-1 位置的数了。
想到 头 都快爆炸了 .............= =
不知道为什么题目类型归为 graphs，我觉得像想法题多点
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 using namespace std; 6 7 const int N = 1e6 + 5; 8 const int maxn = 2e5 + 5; 9 10 int aft[N], cnt[N];11 int res[maxn];12 13 int main()14 {15 #ifndef ONLINE_JUDGE16 freopen("in.txt", "r", stdin);17 #endif // ONLINE_JUDGE18 int n, a, b, fst;19 while (scanf("%d", &n) != EOF)20 {21 memset(aft, 0, sizeof(aft));22 memset(cnt, 0, sizeof(cnt));23 24 for (int i = 1; i <= n; i++)25 {26 scanf("%d%d", &a, &b);27 if (a == 0 && b != 0)28 res[2] = b;29 else if (a != 0 && b == 0)30 {31 fst = a; // 这个很重要，因为有可能整个序列只有两个元素32 res[n-1] = a;33 }34 aft[a] = b;35 cnt[a]++;36 cnt[b]++;37 }38 for (int i = 0; i <= N; i++)39 {40 if (cnt[i] == 1 && aft[i] != 0)41 {42 fst = i;43 break;44 }45 }46 int tt = res[2];47 for (int i = 4; i <= n; i += 2) // 填偶数位置48 {49 if (aft[tt])50 {51 res[i] = aft[tt];52 tt = res[i];53 }54 }55 res[1] = fst;56 tt = fst;57 for (int i = 3; i <= n; i += 2) // 填奇数位置58 {59 if (aft[tt])60 {61 res[i] = aft[tt];62 tt = res[i];63 }64 }65 for (int i = 1; i <= n; i++)66 printf("%d ", res[i]);67 puts("");68 }69 return 0;70 }
codeforces 490B.Queue 解题报告