牛客网暑期ACM多校训练营（第七场）1

牛客网暑期牛客网暑期ACM多校训练营（第七场）多校训练营（第七场）

一. 编程题

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

Output n space-separated integers, where the i-th integer denotes p

i

vertex in the right part that is matched with the vertex numbered i in the left part. All p

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

输出

2. In a strange kingdom, there are N months in one year and there are M days in one month. A day in a year

of the Kingdom can be represented by a pair (x, y) where 1 ≤ x ≤ N denotes the month and 1 ≤ y ≤ M

denotes the day.

A nonempty set of days S is given. Charlotte's birthday is one of the elements of S. Alice, Bob and David

know this fact but they didn't know any other information about her birthday. Let's denote Charlotte's

birthday as (c

x

, c

y

).

Charlotte tells Alice the value of c

After that, the following exchange happened exactly L times :