Codeforces Round #788 (Div. 2)

A. Prof. Slim

一开始读了个假题,一度怀疑不该extra registration…

容易知道负号一定都在左边,所以模拟改操作后判断是否已排序即可

B. Dorms War

遍历维护答案即可,答案为相邻两个特殊字符之间的下标差

C. Where is the Pizza?

一开始的想法是维护每个数字在两个序列的下标,然后一个for循坏使得所有关联位置的标记数组置真

后来发现并查集即可。。。于是修修补补过了

D. Very Suspicious

首先知道图中仅会存在三组直线系,每两条不平行直线可以贡献两个正三角形,于是我们可以贪心地每组直线系的直线数量依次加一,而每次该操作的贡献为另外两组直线数量和的两倍

E. Hemose on the Tree

构造题,首先应该注意到从$1$一直异或到$2\times n-1$的答案为$n$,所以我们要构造到最大代价为$n$的图

所以我们不妨选择$1$为根,将$1$的代价置为$n$,并且维护两个数$st=1,en=n+1$,如果遍历到当前点的代价不为0(实际上此时为$n$),则我们将下一条边的代价置为$en$,点的代价置为$st$。否则我们将反过来构造代价。

上一篇
下一篇