A
题意:给长度为n的序列染黑白色,要求连续的黑的格子数量<=a,连续的白的格子数量<=b,问方案总数,有多个询问
分析:递推
注意数据范围,是可以O(n)做的,所以可以直接递推
B
题意:每个servant有ai,bi,ci,pi,有boss的血量H,求满足(ai+bj+ck)(1+pi%)>=H(i!=j!=k)的组数,n<=1e5
分析:FFT典型应用
枚举每个ai的话,问题就是求bj+ck>=M的组数,明显的FFT应用
若b中有大于H的,直接修改成H,不影响结果,同样处理c
将b的权值多项式和c的权值多项式FFT相乘
因为j!=k,所以把每个自己的bi+ci减掉
求个后缀和就是>=M的组数
还有问题i!=j!=k,可以做个容斥,减掉i==k和i==j的,发现这两个很好处理
C
题意:给一个无向图的某些点设置安全通道,使得无论哪一条边断掉,每个点都能前往一个安全通道(注意断掉的那条边连接的两个点若设置了安全通道,那么这两个点的安全通道也会崩坏),求最少要安放多少安全通道,以及在最少前提下的方案数
分析:边双联通分量
容易想到先弄出所有边双然后缩点成一颗树
若树只有1个节点,那么答案一定是2或3,对于2的情况,我们只需要放(u,v),其中u、v没有边相连;但是如果没两个点都有边相连呢(即是完全图)?容易发现这样2个肯定不行,3个是最小答案,任意取3个
若树有多个节点,那么发现最小答案一定是在每个节点里面放一个安全通道,同时这个安全通道不能是连接树边的点,方案就是π(size(u)-1)
D
题意:圆柱桶内、外有两只蚂蚁,里面的蚂蚁找最短路径跑到外面蚂蚁的位置,这题特殊的是,圆柱桶的内部底面可以走
分析:数学分析
问题可以转化成:里面蚂蚁先走到底面圆周一点A,再沿着直线走到圆周一点B,再从B走到外面蚂蚁位置
画出展开图、列方程
具体的题解写的很清楚了,然后三分……(但好像精度不行啊,要暴力求导二分导函数的一边啊,很休闲啊?)
E
题意:求[L,R]内满足条件的x个数,条件是x能分解成若干个整数的乘积,这些数每个位置不能出现1、6之外的数,R<=1e10
分析:暴力
1e10内满足由1、6组成的数很少啊,先dfs出来
然后从小到大枚举乘一乘,装到set里
发现1e10内的x也很少啊……所以不会TLE啊
然后就把set中的东西写到数组中,二分找区间