Codeforces Round 250 Div.1

Posted on By 二价氢

难得全A一场比赛……

#A. The Child and Toy

比赛的时候一眼看出贪心

然后手动枚举各种贪心策略……

居然AC了……

Code

#B. The Child and Zoo

首先按照点权倒序排一遍

对于每个点,所有与它相连的点且权值比它大的点加到它的集合里,答案就加上它的权值分别乘上两个集合的点数

最后答案除以

Code

#C. The Child and Polygon

很水的一道题

给的点是已经排好序的……

注意有

答案就是要求,显然记忆化搜索走起!

注意如果线段在多边形外面就要排除掉……

Code

#D. The Child and Sequence

线段树水题

注意要利用上取模的性质

操作1和操作3都很简单

保存下区间最大值的位置,下面讨论操作2

完成区间取模操作的次数的是均摊级的

在数据范围内是不能被卡住的

证明如下:

对于一个数,对取模

则记,,显然,,这里,

所以一个数取模之后小于它的一半

log次取模(指模数小于它)之后,这个数就变成0了……

Code

#E. The Child and Binary Tree

设答案为的前

同时设其对应的母函数为,为了方便,下面以代指的前

显然,同时设母函数表示哪些权值是“好”的

然后,我们只需要将这个母函数不断地自己乘自己就好了……

(居然这么简单?!这么简单?!这么简单?!)

Code(不要在意那六行卖萌)

Div2→