# Codeforces Round #765 (Div. 2)(Codeforces Round #765 (Div. 2))-其他

## Codeforces Round #765 (Div. 2)(Codeforces Round #765 (Div. 2))

### D. Binary Spiders

1.x的1的最高位大于k的1的最高位。
2.x的1的最高位等于k的1的最高位。之后去掉最高位，再做比较。

————————

### Codeforces Round #765 (Div. 2)

After writing ABC, I was fined again

### D. Binary Spiders

Look at this question first. The meaning of the question is very simple. Give you a pile of numbers and let you choose a set so that the value of any two numbers XOR in this set is greater than or equal to K. finally, ask the maximum number of this set and a construction scheme.
We consider what is greater than K. because it is related to bit operation, we must analyze it from the perspective of binary. We first replace K with binary bits, and we find the highest bit of its 1. Then if a number x is greater than k, it can be divided into the following two simple cases
The highest bit of 1 of 1. X is greater than the highest bit of 1 of K.
The highest bit of 1 of 2. X is equal to the highest bit of 1 of K. Then remove the highest bit and compare it.
Let’s first consider the first case, which requires that any two numbers in this set are XOR greater than or equal to K. The first case can also be expressed in another way: move x to the right by M bits, M is the highest bit of 1 of K, and X is still & gt; 0. That is, after any two numbers are shifted m bits to the right, the XOR is still greater than 0. Consider the case where the XOR of two numbers is equal to 0, that is, equal. Then we have the idea. We can classify all numbers according to the values after moving m bits to the right. The XOR between different classes must be greater than 0, which means that case 1 is established and they do not interfere with each other. How many can you choose in the same category? Consider three numbers, they are of the same class, a, B, C. if they can all be selected, then they must be ab = 1, AC = 1, B ^ C = 1 in the m-bit Then two of them must be XOR equal to 0 and less than K in the m-bit, which means that at most 2 numbers in the same class can be selected. As for the choice, it depends on the largest XOR value in this class. This is a classic problem. Just build a 0 / 1 tire tree.
On the whole, this question is really good.