（第七场）A Minimum Cost Perfect Matching 【位运算】

题目链接：https://www.nowcoder.com/acm/contest/145/A

A、Minimum Cost Perfect Matching

You have a complete bipartite graph where each part contains exactly n nodes,numbered from 0 to n - 1 inclusive.
The weight of the edge connecting two vertices with numbers x and y is x^y? (bitwise AND).
Your task is to find a minimum cost perfect matching of the graph,i.e. each vertex on the left side matches with exactly one vertex on the right side and vice versa. The cost of a matching is the sum of cost of the edges in the matching.
denotes the bitwise AND operator. If you‘re not familiar with it,see {https://en.wikipedia.org/wiki/Bitwise_operation#AND}.

输入描述：

The input contains a single integer n (1 ≤ n ≤ 5e5).

输出描述：

Output n space-separated integers,where the i-th integer denotes p i (0 ≤ pi ≤ n - 1,the number of the vertex in the right part that is matched with the vertex numbered i in the left part. All pi should be distinct.
Your answer is correct if and only if it is a perfect matching of the graph with minimal cost. If there are multiple solutions,you may output any of them.

示例1:

输入

3

输出

0 2 1

说明 For n = 3,p0 = 0,p1 = 2,p2 = 1 works. You can check that the total cost of this matching is 0,which is obviously minimal.

?

题意概括：

求0~N-1的一个排列 p， 使得p[ i ] ^ i 的总和最小。

官方题解：

? 最优解的和一定是0。
? 当n是2的次幂的时候，非常简单p[i]=n-1-i即可。
? 否则，设b为<=n最大的2的次幂，
? 对于b <= x < n，交换x和x-b。
? 分别求两边的最优解。

举例
Minimum Cost Perfect Matching
? n = 11，初始为 0,1,2,3,4,5,6,7,8,9,10
? 取b为8，开始交换 8,10,7 / 0,2
? 取b为2，开始交换 8,7 / 2,1 / 0
? 翻转每段得到
? 7,8 / 1,2 / 0

解题思路：

题解给的是常识和构造。

最优和为 0 毋庸置疑。结合这道题思考，有按位与运算，我们可以从大到小把 i 取反（则相与的结果肯定为0），然后求该数 i 的最高位，保证取反的情况下不超过N的范围。

?

AC code：

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <algorithm>
 4 #include <cstring>
 5 #include <cmath>
 6 #include <bitset>
 7 #define INF 0x3f3f3f3f
 8 using namespace std;
 9 
10 const int MAXN = 5e5+10;
11 int num[MAXN],a;
12 int N;
13 int hb(int k)
14 {
15     int n = 0;
16     while(k > 0)
17     {
18         n++;
19         k>>=1;
20     }
21     return n;
22 }
23 int main()
24 {
25     scanf("%d",&N);
26     bitset<32> b;
27     memset(num,-1,sizeof(num));
28     for(int i = N-1; i >= 0; i--)
29         {
30             if(num[i] == -1)
31             {
32                 b = ~i;
33                 int len = hb(i);
34                 int t = 1;
35                 int sum = 0;
36                 for(int k = 0; k < len; k++)
37                 {
38                     sum+=b[k]*t;
39                     t*=2;
40                 }
41                 num[i] = sum;
42                 num[sum] = i;
43             }
44         }
45     for(int i = 0; i < N; i++)
46         {
47             printf("%d",num[i]);
48             if(i < N-1) printf(" ");
49         }
50     puts("");
51     return 0;
52 }