TC SRM690 900

时间:
5.22 21:34

题意:
将\(0 \to 2n-1\)的数填到\(2*n\)的格子,且两行格子满足每行都有一个\(\geq k\)的数。
将每列的最大值依次写下,再将每行的最大值依次写下,问形成的序列的方案数\(\% 10^9+7,n \leq 500000\)。

题解:
枚举最大值的那一行,显然是个\(Catlan\)数,然后一个数能成为行最大值,那么他前面的数都要是他们列的最大值。
然后枚举两行最大值,\(O(1)\)算算即可。

其他:
简单DP

TCO2016 2A 400

时间:
5.25 21:52

题意:
个数对,每次可以取出两个删除他们,并添加一个数对,问最后能否搞出来给定的一个数对,

题解:
合并的过程类似一个树形结构,我们发现最后面的数对肯定来源于原有数对中的数,枚举来源的数对。然后几种情况分别简单讨论即可。

其他:
日竟然想了很久,讨论大法好,不要总想一步解决。

TCO2016 2A 500

时间:
5.29 19:35(玛雅还没写)

题意:
给定一个个点的带边权图,从中选取出一个团,定义这个方案的权值是团中边权值和减去两端点都不在团中的边权值和。求所有方案的权值和

题解:
看到数据范围,显然可以想到将点集分成两半然后分别计算再合并啥的。
方案的权值跟都不在点集中的边有关,好像不太好算。我们发现一个方案的权值可以用只跟团中点有关值求得。
一个点相邻的边权和,一个方案的权值即为
有了这个转换,再回到问题,我们分成两个集合。枚举一个集合中选取的点集,然后另一个集合中可选的子集就可以处理出来,然后用子集莫比乌斯变换预处理即可。

这样复杂度是

TCO2016 2A 1000

时间:
5.29 22:07(玛雅还没写)

题意:
个机器,每个机器有两个属性,你有张票,每次可以往一个机器里投票。每投一次票,有的概率获得奖励,在没有获得奖励之前不能换机器,并且在获得奖励后下一次投票必须换一个机器。
问期望最大奖励是多少,

题解:
其实是裸的FFT啊,然而我以为要随时取max,傻逼了。

表示刚开始往投票,还剩下张票的期望值。然后转移里面只有加法没有max,是一个卷积形式,分治+FFT即可。
可以过。

BZOJ4621 TC605hard

时间:
6.14 22:37

题意:
最初你有一个长度为的数字序列。为了方便起见,序列是一个排列。
你可以操作最多次。每一次操作你可以先选定一个的一个子串,然后将这个子串的数字全部变成原来这个子串的最大值。问最终有几种可能的数字序列。答案对取模。

题解:
...

THOI2013 魔塔

时间:
5.31 上午考试

题意:
你是一个英雄,有个怪物,每个怪物属性为:表示血量、攻击、防御,你也有这三个属性。你和怪物们依次决斗,每回合同时互相攻击,直到一方血量非正,攻击伤害为攻击者的攻击防御者的防御。为了使你最终战胜所有怪物,你可以购买属性,假设属性为,那么所需金币数为,问你最小花金币数。

题解:
花费金币数为
第一看上去,直接三分套三分啊,然而发现不对劲。
考虑枚举,因为关于的式子很诡异,然后我们发现有效的对于每个怪物只有个。
然后确定后这个式子关于导数不增,是个单峰函数,这个就可以求出来,然后发现在递增的时候这个函数的极值点也递减,用单调指针扫就可以了,扫的过程中维护后缀和,由于指针单调修改、查询是可以的。
总复杂度为

THOI2013 星际飞船

时间:
5.31 上午考试

题意:
个向量,你需要求出:1.从中选出一些,使得其向量和在上投影最大。2.从中选出一些使得其向量和模长最长。3.从中选出个向量使得其向量和模长最长,求出所有答案。

题解
(哼,明明考场上想cai出正解了,结果没时间了)
一开始没看到有部分分,于是就想第一、二问是在逗比吧,不是只要求出第三问就可以了?于是想起来了数学题里第一问证明的结论是为第二问服务的。于是恍然大悟。
如果知道最终向量方向,就可以和第一问一样地做,都可以求出来,那就随机或直接暴力精度枚举最终向量,就可以了。

BZOJ4605 崂山白花蛇草水

时间:
6.14

题意:
每次在平面一个位置加入一个数,询问矩阵第k大,强制在线。

题解:
替罪羊思想+KD-Tree模板题,这两样都没写过= =。
值域线段树套KD-Tree,因为KD-Tree需要重构,放入内层。
应用替罪羊思想,当不满足深度平衡时,找祖先中最深的不满足重量平衡的,进行重构。
然而每次插入后,找到一个最深的不满足重量平衡的会更快= =。

BZOJ 两个串

时间:
6.18

题意:
给定两个只含小写字母和通配符'?'(即可以匹配任意一个字符)的串,问中出现次数。

题解:
经典FFT字符串匹配题。

暴力:
CF Fuzzy Search算法,对于每一种字母,表示在位置的该字母匹配数。
那么对于每个字母,,我们发现这是一个类似卷积的东西,,对于每个字母做FFT即可。

对于这道题,两个位置匹配=,那么我们定义两个位置的匹配值,当该值为0时匹配否则不匹配。
那么一个位置的特征值
在某一个位置时,能匹配意味着
把式子划开可以得到一个卷积,那么做一遍FFT即可。

然而我们忘记考虑通配符了,那么重新定义匹配值,只有这一位为'?'时,该位为0。
展开后一样是卷积。

PE Divisors

时间:
6.18

题意:
给定,求

题解:
推式子,%Cab。

于是枚举计算右边的式子。
复杂度为:

其他:
主要是要推对式子,然后把重要的东西提到前面来,发现有一个可以合并的两项。

SPOJ DIVCNT2

时间:
6.18

题意:
给定,求

题解:
推式子,%Cab。
洲阁论文杜教筛例题。

,则,其中表示的不同质因子数。
可以通过质因子分解的方式计算除数函数来证明。

于是我们有:

其中第二步、第三步可以通过他们的实际意义来推得。
线性筛预处理,然后记忆化递归算上面三个式子,复杂度是

Cab做法是,将第二个式子代入第一个式子,得到:
由上面第三个式子,计算的复杂度是
计算复杂度是的。
运用杜教筛复杂度证明,预处理后复杂度为

其他:
灵活运用每个式子的实际意义(这种神奇转换怎么看得出啊)。

Comments

comments powered by Disqus