牛客网暑期ACM多校训练营(第七场)A Minimum Cost Perfect Matching

  • 2018-08-10
  • 6
  • 0

Description:

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 img (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.

img denotes the bitwise AND operator. If you’re not familiar with it, see {https://en.wikipedia.org/wiki/Bitwise_operation#AND}.

Input:

The input contains a single integer n (1 ≤ n ≤ 5 * 10^5).

Output:

Output n space-separated integers, where the i-th integer denotes pi (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.

Sample Input:

3

Sample Output:

0 2 1

Hint:

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.

题目链接

dfs暴力搜索易观察得最小值均为0,当(\sim x)=y时x\land y(bitwise AND)取得最小值0,所以连接的线可以均为(\sim x)=y,且若xy相连,则y也与x相连,枚举x找相应的y即可。

AC代码:

评论

还没有任何评论,你来说两句吧