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

Codeforces Round #765 (Div. 2)

写完ABC,又罚座了….

D. Binary Spiders

先看这个题,题意很简单,给你一堆数,让你选出一个集合,使得这个集合内任意两个数异或的值都大于等于k,最后问这个集合的最大数量以及一个构造方案。
我们考虑大于k有哪些情况,由于和位运算有关系,我们肯定要从二进制的角度去解析。我们先把k换成二进制位,我们找到它的1的最高位,那么如果一个数x要大于k的话,可以分为以下两种简单情况
1.x的1的最高位大于k的1的最高位。
2.x的1的最高位等于k的1的最高位。之后去掉最高位,再做比较。
我们先考虑第一种情况,要求这个集合内,任意两个数异或起来都是大于等于k的。第一种情况也可以换一种情况表述:将x向右移m位,m为k的1的最高位,x仍>0.也就是说,任意两个数向右移m位后,异或起来仍大于0,考虑什么情况下,两个数异或起来等于0,也就是相等的情况。那么思路就有了,我们可以把所有的数按照向右移m位后的值进行分类,不同类之间,异或起来一定大于0,则意味着情况1成立,他们互不干扰。那么同一类里面,最多能选多少个呢?考虑三个数,他们是同一类的,a,b,c,假如他们都可以被选中的话,那么在m位上他们必定ab=1,ac=1,b^c=1.那么他们中一定有两个数在m位上异或起来等于0,小于k,这说明同一类中最多选2个。至于能不能选,这就要看这一类中最大的异或值了。这是个经典问题,建个0/1 tire树即可。
总的来说这个题真挺好的。

————————

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.