A. Ranked minimum spanning tree (pmst)
A sign-in that no one has signed.
The parameter was adjusted to 110 and it passed! However, the side stored by the big constant player, set, was hung up in a log during the race, so I couldn't run a big sample.
Positive solution:
It is found that a chain is formed only by connecting the edges of the numbered neighboring points, when the lengths of all the edges are\(\le n\), so no matter what we can guarantee that the edge weights of each edge of the minimum spanning tree\(\le n\)。
Then we only put the edge weights\(\le n\) It is sufficient to connect the edges of the Edge weights\(\le n\) need to be satisfied\(abs(i-j)\) cap (a poem)\(abs(p_i-p_j)\) At least one.\(\le \sqrt n\). So every point built on\(2\times \sqrt n\) A strip of edge is sufficient.
The maximum number of side rights is\(n\)So start a vector array.\(v_i\) Survivor's rights are\(i\) to avoid the log complexity of sorting.
B. Cardgame
sign in
found\(lcm\) because of\(n\) cap (a poem)\(m\) the least common multiple of\(gcd\) because of\(n\) cap (a poem)\(m\) of the greatest common factor, it is clear that\(lcm\) The rounds are exactly one cycle at a time.
And that's before\(lcm\) There is a guaranteed maximum of one comparison per two people within the round.
\(n=k_1\times gcd\)，\(m=k_2\times gcd\)So in one loop\(a_i\) cap (a poem)\(b_j\) The comparison must have\(i\% gcd=j \% gcd\)and for a\(i\) will correspond to all the\(j\ (if\ j\%gcd=i\%gcd)\)so that all the modes in 1~n\(gcd\) All the modes in 1~m are stored together if they have the same remainder.\(gcd\) The ones with the same remainder are stored together. For all\(i\in [1,n]\)Calculation 1~m in\(i\% mod\) of how much is in that bucket that is less than yourself, equal to yourself, and greater than yourself is just fine.
have altogether\(\lfloor \frac {n\times m} {lcm} \rfloor\) The cycle, find the number of times a cycle A wins, the number of times B wins, multiplied by the number of cycles is good.
insofar as\(n\times m \% lcm\) The part that violently simulates just fine.
C. Bit Jump
Properties of binary operations
Found out it was actually three questions in one.
-
\(and\) portion
It was found that most of the numbers can be made to have an answer of 0, only in the\(n\) is special when all the binary representations are 1, except for the\(n\) is 0, and the value of the value of\(n\) The associated edge builds on running the shortest circuit to find the\(dis_n\) is the answer to n;
-
\(xor\) portion
Think of the different-or operation as adding but not rounding on each bit, so just change the binary representation one bit at a time before connecting the edges back to the original number
-
\(or\) portion
The more or's there are, the greater the weights, so it is preferable to transfer over a number represented only by 1 or a subset of 1 under its own binary.
First, connect 1 to each point and that\(m\) The strip runs side by side with the shortest circuit, and then for each number updates itself with the weights of the number represented by a subset of the 1's in its binary, again changing only one bit of the binary at a time.
Store the weights of each current number as edge weights in Dij's heap and run the shortest circuit again.