CF1305 (Div.1 + Div.2) #

Ozon Tech Challenge 2020 (Div.1 + Div.2, Rated, T-shirts + prizes!)

A. Kuroni and the Gifts #

排个序就行了

B. Kuroni and Simple Strings #

觉得应该和第三题换一下比较好.

为了求稳写了个模拟,从左往右每次扫到左括号的个数小于等于右括号的最后一个左括号时,就把前面的左括号和最后几个右括号同时删掉.

但是可以发现只用删一次,剩下的一定不是合法括号串.

C. Kuroni and Impossible Calculation #

坑比题,由抽屉原理可知$N > M$时一定有两个数字同余,直接输出0.

$N < M$n方暴力就行.

D. Kuroni and the Celebration #

交互题,第一次做,比赛时没敢开,其实很简单的.

每次选两个叶节点询问,如果这两个叶节点的lca是其中一个叶节点,那答案已经就是这个叶节点,否则删掉这连个点,继续询问.

E. Kuroni and the Score Distribution #

可以发现,对于固定的N,[1,2,…,N]是balance最多的序列,所以M>这个序列的balance时一定是-1.

同时,从[1,2,…,N]到[1,2,…,N+1],balance多了$\lfloor \frac{N}{2} \rfloor$.

可以先找出最大的N,使[1,…,N]的balance不大于M,用t代表这个序列的balance与M的差值,显然,这个t是小于$\lfloor \frac{N}{2} \rfloor$的.

然后,输出这个序列倒数第一个(即N)与倒数第(2*t)个(即$N-2\times t+1$)的和,这样就可以多出t对数与新输出的这个数组成一个合法对.

如果此时还剩下数没有输出,可以按照$1e8+cnt\times 1e4$输出剩下的数,其中cnt代表剩下的第几个数.因为前面的数不会大于1e4,而cnt不会大于5e3,所以新输出的数不会超过2e8,这样就保证的新输出的这些数不会影响到这个序列的balance.