Codeforces Round #180 (Div. 2) 解题报告

时间:2022-11-16 11:55:39


​题目链接​

A.​​Snow Footprints​

​A - Snow Footprints​

The starting position can be anywhere with a footprint. The footprints can be categorized into 3 types.

  1. L
  2. R
  3. R s followed by L

R or the leftmost L

​B - Sail​

We can simply move by greedy method — only moves when it takes the boat closer to the destination.

​C - Parity Game​

Fact 0: If a has odd parity, we can apply operation 1 to increase its number of 1 by 1.

Fact 1: If a has a even parity, its number of 1

a has parity 0, unless we pop a 1, otherwise we cannot write a new 1 into a.

Fact 2: If the number of 1 in a is not less than the one in b, we can always turn a to b

b at the right of a. Lets assume a has even parity now. If we need a 0, simply apply operation 1. If we need a 1, keep remove from head until we remove a 1. Notice that we never remove digits from 'new part' of a. Now the parity of a will be odd and we can apply operation 1. After that, the parity of a becomes even again, the number of 1 in the 'old part' of a decrease by 1 and we handle a 1 in b.

a. Now we get b.

a into b


countOnes(a) + parity(countOnes(a)) ≥ countOnes(b)

​D - Fish Weight​

n > m, set every weight to 1 and done. Otherwise, lets sort a and b in non-increasing order, and trim the last part of b such that its length equals a.

Claim: answer is YES if and only if exists i such that ai > bi

 If for every iai ≤ bi, that means for every Alice's fish, there is a correspond Bob's fish which is as heavy as Alice's.

 Let i be the smallest one such that ai > bi. We can amplify the gap between wai and wbi

​E - Splitting the Uniqueness​

An equivalent definition for almost unique, is arrays with at least ⌊ 2n / 3⌋ different elements. The idea is to split s into three parts. In the first part, we give uniqueness to a. In the second part, we give uniqueness to b. In the third part, we give uniqueness to both.

s is sorted. Since s is an unique array, si ≥ i for all i (0-based). The image below will give some intuition on how to split it. ais red, b


n = 30.

i = 0... 9:  assign ai = i (do not care values of b)

i = 10... 19:  assign bi = i (do not care values of a)

i = 20... 29:  assign bi = 29 - ia takes the remains. From i = 20, a will have strictly increasing values starting from at least 11.