首页 > 代码库 > codeforces 500B.New Year Permutation 解题报告

codeforces 500B.New Year Permutation 解题报告

题目链接:http://codeforces.com/problemset/problem/500/B

题目意思:给出一个含有 n 个数的排列:p1, p2, ..., pn-1, pn。紧接着是一个 n * n 的矩阵A,当且仅当 Aij = 1 时,pi 与 pj 可以交换数值。现在问如何交换数值,使得最后得到的排列字典序最小。

  比赛的时候不会做,看了Tutorial 1 的解法,觉得别人做得太巧妙了,出题者也出得很好 ^_^

  可以看这个:http://codeforces.com/blog/entry/15488

    它是利用了并查集来做的。如果遇到 Aij = 1 的话,就将点 i 和 点 j 连一条边。最终会得到一些互不相交的集合。以第一组 test 来说吧~~~

  技术分享

  

  这就表示位置 1、4、7 的数是可以交换的,位置 2、5 要保持原封不动,位置 3、6 的数可以交换。由于每个集合都有一个祖先,即第一层的那个数,依次为 7、2、5、6,然后就把每个集合的数放到以该集合祖先为首的 vector 数组里面,并把每个集合内的数从小到大排序。最后遍历位置 1 ~ n,根据每个位置的数所属的集合(以哪个祖先为首),依次输出。

  只能说,解题思路真是太巧妙兼神奇!竟然可以转化成图!继续干爸爹吧 ^_^

  

 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <vector> 6 using namespace std; 7  8 const int maxn = 300 + 10; 9 int p[maxn], cnt[maxn];10 int group[maxn];11 char s[maxn];12 vector<int> vi[maxn];13 14 int find(int x)15 {16     if (x == group[x])17         return x;18     return group[x] = find(group[x]);19 }20 21 void merge(int x, int y)22 {23     int fx = find(x);24     int fy = find(y);25     if (fx != fy)26         group[fx] = fy;27 }28 29 int main()30 {31     #ifndef ONLINE_JUDGE32         freopen("in.txt", "r", stdin);33     #endif // ONLINE_JUDGE34     int n;35     while (scanf("%d", &n) != EOF)36     {37         vi[n].clear();38         for (int i = 1; i <= n; i++) {39             scanf("%d", &p[i]);40             group[i] = i;41         }42         for (int i = 1; i <= n; i++) {43             scanf("%s", s+1);44             for (int j = 1; j <= n; j++) {45                 if (s[j] == 1) {46                     merge(i, j);47                 }48             }49         }50         for (int i = 1; i <= n; i++) {51             vi[find(i)].push_back(p[i]);  // 千万不要写成 vi[group[i]].push_back(p[i]);52         }53         for (int i = 1; i <= n; i++) {54             sort(vi[i].begin(), vi[i].end());55         }56         memset(cnt, 0, sizeof(cnt));57         for (int i = 1; i <= n; i++) {58             int g = group[i];59             printf("%d%c", vi[g][cnt[g]++], i == n ? \n :  );60         }61     }62     return 0;63 }

 

  注意,代码中的 51 行的部分,如果写成 vi[group[i]].push_back(p[i]) 是错的!以第二个 test 为例,group[1] = 3,find[1] = 5。find[i] 才会找到最终的祖先!!!

codeforces 500B.New Year Permutation 解题报告