A 四章
题意:有个
和
个
,把它们分成尽量少的组,使得每组的和不超过
。
我们使用一个贪心算法,每次先选择尽可能多的,再选择尽可能多的
分成一组。可以证明这样能够得到最优解。因为如果在还没被选的数中,把一个
换成两个
,答案一定不会变劣;所以如果在新选出的一组里存在两个
、且存在至少一个
没被选,把两个
换成一个
必然更优。
由于数据范围为,无法直接模拟。
可以先计算出若和
都足够多,每组要选几个
、几个
。然后再不断使用这种方案直到
或
之一不够。之后下一组必定会将
或
选完。之后就只剩一种数了,直接计算即可。
复杂度。
B 一章
以下图片中红点为割点、红边为桥。
当时:
- 若
,构造一个三元环即可。
- 若
,构造两个点之间连一条边即可。
- 若
,无解。因为可以发现若一个桥边的某个端点不是割点,那这个端点必定是
度点。
当时:
- 按照以下方法构造:
当时:
- 按照以下方法构造:
C 欢乐斗地主
设第张牌被替换的时间为
,那么地主的操作就等于随机生成了一个排列
,而这个排列的答案就是从左到右第一个
且
的位置。
如果我们对于每个,求出有多少个排列满足答案
,即可求出原问题的答案。设以上的答案为
,那么
就等于满足以下条件的排列个数:对于所有的
且
的位置,满足
。
对于一个,我们可以用以下方法求:从左到右枚举满足
且
的
,设
之前已经有
个
了,那么
的选择方案需要满足
且和前
个
的选择不同,即答案要乘上
。最后,设总共枚举了
个数,那么剩下
个数的决策还没确定,需要再乘上
。
容易发现根据以上方法,可以方便地从小到大一次性求出所有。这样我们就在
的时间解决了此题。
D 买糖果
一句话题意:求的所有非空子集的和的积。
可以采用meet in middle。先把前一半是空集和后一半是空集的情况用的复杂度处理掉,然后就是前一半和后一半都非空的情况。
设前一半的所有情况的和为,后一半所有情况的和为
,那么要求的就是
。
设, 答案就是
。那么我们对所有
跑个多点求值即可解决这个问题。
复杂度为。
E 正整数序列
以下定义。
定义为满足以下条件的长为
的数组
的个数:
。
- 对于任意
,
是
的子序列。
- 对于最后一个非空序列
,满足
中不存在数字
。特殊地,若
,表示没有任何限制。
那么答案就是。
对于转移,一共有两种情况:
为空,那么
。
中第一个数字为
,那么为了防止被计算重,
中
到
间不存在
;但是若
中
到
间为空,
中
到
间不存在
。则依此类推,可得
。
这样便可以解决这个问题。复杂度。
F 时之魔法
我们枚举所有原串或反串中两个后缀,计算它们的贡献,一共有以下几种情况:
和
属于两个不同的串。那么贡献为
乘上
和
所在的串 翻转/没翻转 的概率之积。
和
属于同一个串,且同为 原串/反串。贡献计算方式与上种情况类似,但概率只需乘一次。
和
属于同一个串,且一个为原串、另一个为反串。贡献为
。
对于计算贡献的方式,我们先假定每一对后缀都属于第一种情况。那么总贡献即为每一对后缀的概率之积乘上它们在后缀树上的深度。我们可以利用广义后缀自动机建立后缀树,然后在上面
求出答案。
之后我们需要减去属于同一个串的所有后缀的贡献,并重新计算它们的贡献。那么我们可以仅对同一个串的原串与反串建立后缀树,重新计算贡献。而这个过程也可以通过在后缀树上解决。
设字符串总长为、字符集大小为
,我们在
的复杂的内解决了此题。
全部评论
(2) 回帖