over 2 years ago

前言

闲来无事水一水的题目。

CF 286E

题目大意:给你一个长度为的序列以及一个整数,要你求出一个最短的序列,假设其长度为,满足以下条件:
1).对于任意一个,都存在,且
2).对于任意,如果,那么一定要满足
这道题怎么做呢?首先我们可以明确的知道
我们考虑一个合法的,对于任意,要么满足,要么存在一个使得。根据贪心原理可以知道是由那些不能由其他组合而成的构成。
的生成函数为,考虑的前~项。如果的话,很显然这个值是不能由其他的组合而成的,将其加入中。如果,说明构成了一个不存在于中的值,肯定无解。于是这样我们就得到了序列。
时间复杂度
CF286E.cpp

CF 300D

题目大意自己看吧。。不想写了。。
首先我们有一个朴素的想法,设表示时的答案。
那么方程就是:
其实换句话说,我们考虑第三种情况,设表示的生成函数,那么
但是考虑到,直接这样是不行的,其实我们只需要考虑最多能经过多少次减半就无法继续减半下去了。
因此我们设表示最多能减半次的数,对于的答案,那么类似的有:
这里的级别的,因此我们可以预处理~,预处理的时间复杂度就是
然后对于每一次询问计算出的最多减半次数,然后就可以的时间回答。
时间复杂度
CF300D.cpp

CF 438E

题目大意:给出一个正权值集合。对于一棵带权二叉树,每个结点的权值都在中,定义其权值为所有结点权值和。给定一个,问你权值为~的二叉树有多少个。左孩子与右孩子是不同的。
为答案的生成函数,其中表示权值为的生成树个数,设为权值集合的生成函数。
根据二叉树的定义,我们可以得到一个式子:是表示
根据初中解二次方程的方法,我们得出。然而我们知道一个多项式可逆当且仅当可逆,因此只能取,所以答案就是
然后就是多项式开根,多项式求逆啥的参见picks博客啦,时间复杂度又是喜闻乐见的
CF438E.cpp

CF 472G

题目大意:定义两个等长串的Hamming Distance。给定两个,有组询问,每次询问表示求子串与子串Hamming Distance
我们考虑对于固定的长度为的子串,如何对于中的每一个长度为的子串求出答案。
对于中以结尾的长度为的子串的答案可以表示成
串反转,那么答案可以表示成
我们对于串构造一个新的串,其中同理,那么我们就可以的时间来算出这种情况下的答案。
我们考虑对于串分块,设块大小为,对每一块的串与计算答案,时间复杂度就是
然后对于每次询问的回答就很简单了,时间复杂度为
我们取,那么时间复杂度就是
CF472G.cpp

CF 528D

题目意思自己看吧,感觉这道题是上一道题的简化版,将串反转,四次即可。
CF528D.cpp

CF 553E

题目大意:一个个点条边的有向图,每条边有一个权值和一个通过时间,不过这个通过时间是根据概率给出的,即有的概率以的时间通过这条边。刚开始在1号点,我们要走到n号点,我们记总花费为经过的路径的权值和,如果总时间一个给定的阈值,那么花费要加上一个额外的给定的。求最小花费。
我们设表示从点使用时间为的最小花费,那么有:

很显然裸的,还是不够的。
假如我们已经知道了,那么求答案时间复杂度就是,所以我们的问题就变成了如何快速求那个式子的值。
我们考虑按时间分治嘛,对于时间范围,我们先求出,再计算这一段区间对的贡献,再求。感觉很简单的样子(^_^),其实也很简单啦。
我们现在已经知道了,对于贡献其实我们就是要求的卷积,因此时间复杂度就是。然后我们就愉快的AC了。
CF553E.cpp
终于搞完了CF上的FFT题目了!

← 好久没更新博客了 UR#4 追击圣诞老人 →
 
comments powered by Disqus