难得全A一场比赛……

#A. The Child and Toy

比赛的时候一眼看出贪心

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

居然AC了……

Code

#B. The Child and Zoo

首先按照点权倒序排一遍

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

最后答案除以\(\frac{n^2}{2}\)

Code

#C. The Child and Polygon

很水的一道题

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

注意有\(f_{i,j}=\sum_{i<k<j} f_{i,k}f_{j,k}\)

答案就是要求\(f_{1,N}\)，显然记忆化搜索走起！

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

Code

#D. The Child and Sequence

线段树水题

注意要利用上取模的性质

操作1和操作3都很简单

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

完成区间取模操作的次数的是均摊\(\log\)级的

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

证明如下：

对于一个数\(a_i\)，对\(x\)取模

则记\(a_i/x = k\),\(a_i \textrm{mod} x = p\)，显然，\(a_i = kx+p\)，这里，\(p<x,k\ge 1\)

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

log次取模（指模数小于它）之后，这个数就变成0了……

Code

#E. The Child and Binary Tree

设答案为\(f[]\)的前\(m\)项

同时设其对应的母函数为\(F(x)\)，为了方便，下面以\(F_i(x)\)代指\(F(x)\)的前\(i\)项

显然\(f[0]=1\)，同时设母函数\(C(x)\)表示哪些权值是“好”的

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

（居然这么简单？！这么简单？！这么简单？！）

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

Div2→