HBC230851[HAOI2007]反素数ANT,深度优先搜索(DFS),数学,贪心,数论,搜索,搜索Bitwise Exclusive-OR Sequence题解

庄子墨算法基础篇 2023-11-21 02:38:02 99 0

题库丰富多样，涵盖各个领域，全网最全C++题库，让您在练习中不断成长！

More precisely, the bitwise exclusive-OR operation is a binary operation which is equivalent to applying logical exclusive-OR to every pair of bits located on the same positions in binary notation of operands. In other words, a binary digit of the result is equal to. 1 if and only if bits on the respective positions in the operands are different. For example, if. Now AAA wants to find out the minimum sum of all the elements in the sequence, or determine that the sequence meets all the constraints does not exist.

AAA has a nonnegative integer sequence a_1,a_2,ldots,a_n a 1 ,a 2 ,…,a n with m m constraints, each of which is described as a_u oplus a_v = w a u ⊕a v =w, where oplus ⊕ denotes the bitwise exclusive-OR operation. More precisely, the bitwise exclusive-OR operation is a binary operation which is equivalent to applying logical exclusive-OR to every pair of bits located on the same positions in binary notation of operands. In other words, a binary digit of the result is equal to 1 1 if and only if bits on the respective positions in the operands are different. For example, if X = 109_{10} = 1101101_{2} X=109 10 =1101101 2 and Y = 41_{10} = 101001_{2} Y=41 10 =101001 2 , then X oplus Y = 1000100_{2} = 68_{10} X⊕Y=1000100 2 =68 10 . Now AAA wants to find out the minimum sum of all the elements in the sequence, or determine that the sequence meets all the constraints does not exist.