• 周一. 8月 15th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

Codeforces Global Round 15

admin

11月 28, 2021

A

(;)
把每种字母所在的区间求出来,对于每一个(i),看(c_i)是否在其应属的区间,若不在,则答案+1

B

(;)
只有我这个sb卡在B了罢。。。。
只有一个胜利者是显然的。
但是如果要判断一个人是否是胜利者需要(O(n))的时间,我们不可能对于每个人都比较一遍。
这里运用到一个思想是排除法(不去找符合条件的人是谁,先把肯定不符合条件的人pass掉)
从前往后扫,如果发现(i)被此时待定胜利者(w)打败了,说明其不可能是胜利者(直接踢掉,不用管他了)
否则说明(w)肯定也不是。
所以要么我们保留(w),要么把一个前缀的人都踢掉了,后面继续排除。
这样只会剩下一个人,再和所有人比较就行了。

C

(;)
手玩一下发现,新加的弦不可能存在其中两根,使得这两根不相交。
将其交换一下,只会使答案更优
直接贪心就好了

D

(;)
满足其中(n-1)个人是很容易的。
把满足条件的两个位置连一条边,那么如果要出现(n)条边,其中肯定会出现环。
也就是存在两个集合(A,B),使得(A)中数的绝对值之和等于(B)
那么(2^{2n} imes n)判断一下就好了

E

(;)
构造好题。
对于一种颜色(c),设其出现的位置为(d_{c,1},d_{c,2},…,d_{c,k})
显然我们只会选相邻的两个位置作为最终答案的一个区间。
观察条件:(lceil frac{n}{k-1} ceil)这个东西很奇怪。
发现(k-1)其实就是每种颜色空隙的数量
有两种想法:
(n)个区间分成(k-1)组,每组最多有(lceil frac{n}{k-1} ceil)个区间,让每个位置最多属于一组

(n)个区间分成(lceil frac{n}{k-1} ceil)组,每组最多有个(k-1)区间,让每个位置在每组中至多出现一次
发现第二种思路比较难搞,得在每个区间都得满足至多出现一次的条件。
考虑第一种怎么做
简化后:让组之间没有交集
按照空隙分组:
先按(d_{c,2})从小到大排序,然后选前几个为一组,这样相当于以第一个空隙为一组
接着对剩余的颜色按(d_{c,3})从小到大排序,再选前几个为一组,以此类推
成功完成了分组

F

(;)
最关键的一点就是,蚂蚁走过一个传送门时,前面的传送门(包括这一个),一定都是开着的
这个归纳一下差不多就可以了
然后维护(k_i)表示从第一次走到传送门(i),到走过去用了多长时间。
(k_i)时,只需要(upper ; bound)一下,再维护一个前缀和即可

发表回复

您的电子邮箱地址不会被公开。