[关闭]
@SovietPower 2019-03-22T09:07:16.000000Z 字数 6145 阅读 1454

3.2 青岛正睿

正睿OI



http://immortalco.blog.uoj.ac/blog/2102
http://opentrains.snarknews.info/
Gym Petrozavodsk


Day4 PM Test

https://www.cnblogs.com/SovietPower/p/10504127.html

A.智慧树(树形DP NTT Bluestein)

根据群里的聊天记录,瞎猜理解了一波,重新理解了一遍DFT和NTT...会记在下面(就忽略吧/kel)(我当时是学了些啥啊/kk)。


首先分是直接用优化背包()。就是每次转成点值,对应相乘,再转回去。复杂度是
蒟蒻表示虽然知道能这么做,但是不明白为什么做模的循环卷积,这样还是对的/kk。重学了一下,因为我们代的是次单位根,如果单位根的次数,就又回去了,所以点值乘的时候就是对取模的。

满分做法当然是,DP的过程中不转回系数表示,直接用点值表示做。统计答案时把点值累加,最后回去。
转移是,那个是个常数(虽然是在系数表示下的),所以直接在点值处就可以了。
最初的正变换是次单点的,直接每次代进个单位根转成点值表示就可以了(),复杂度是的。
注意到不是的次幂,而朴素必须将多项式长度补成,但是这样代的单位根就不是次单位根了。也就是多项式长度必须是
任意长度的需要用到,下面写。

补充一点...当时学没注意(或者忘掉)的东西。。
,那么取素数(满足这样形式的素数叫费马素数,朴素必须是这样的模数,因为要存在任意的单位根),那么存在次单位根,且
注意到这题模数存在原根,且都是的约数,所以存在对应的次单位根。

然而后几个点的,不能直接(上面提到了),需要。但是各位说可以快速插值或者多点求值。。
学了下(也没学,就是看了下是干嘛的),大概就是,用点值DP完之后,我们可以得到个点值,快速插值就可以得到原多项式的系数表示了。
注意到实际就是,将次单位根的逆元代入点值出来的多项式,以得到原多项式的系数表示()。
所以也可以把点值的逆元代进去,多点求值就可以了。。
然而快速插值和多点求值都巨难写,而且常数大的恐怖吧。。(这辈子是不会写的.jpg)

正变换是的,中间过程只有点值相乘也是的,最后每个点用 回去是的。


然后,记一下,用以解决任意长度更多相关题目戳这
考虑的形式:

注意到是个卷积,可以用计算。所以的复杂度是的。
具体:可能是负的,所以对后一项右移位,令,那么

同理,可以直接令,代到的式子里,也可以一样的推一下:

,那么

上面是一般的做法(其实就是个),但是指出有更好一些的做法:
像这样写成平方需要(有些题可能不存在次单位根),就可以用:来替换:

随便扯一句废话:必须要有单位根才能做(直接做DP 精度会爆炸)


最后,还有个问题是卡内存。
的时候先重儿子,然后父节点可以直接继承重儿子的DP数组,再轻儿子。这样我们只需要记录当前个DP数组。

关于类似的卡内存,有一道扩展题:
给定一棵个点的树,每个点有一个重量和价值,你要选一个独立集,对于每个重量,求出其最大价值和。要求复杂度
先DFS轻儿子子树,再考虑父节点,再考虑重儿子...状压现在有用的点的状态...(没听懂.jpg,望dalao解答)


B.组合数(数位DP Lucas)

直接考虑

区间限制可以容斥成只有上界的限制,然后就是数位DP了(虽然不明显,但是考虑是进制各位独立以及应该也可以想到)。因为每进制位上是互不影响的,所以当前贡献就是乘个,然后处理下一位。
考虑一些简单情况:,转移时每一位枚举两个数填什么以及是否需要进的位即可。状态就记三维:第一二个数是否卡上界、是否进位。
时,同样每一位枚举每个数填什么即可,上界限制直接记的状态。
时,就直接对每一位记进了多少的数。有个数就先递归次再枚举下一位,就是很暴力的开的数组表示第几位、第几个数、这一位前几个数的和是多少、进了多少、上界限制。
发现像时从高位到低位做,每次转移枚举进了多少不太靠谱,考虑从低位到高位就没这个问题了。只需要处理一下上界的状态:在低位如果有第个数超过上界,令;如果在高位第个数小于上界,令。最后如果所有的就是合法的(没有超上界的数)。
PS:其实也不需要"每次转移枚举进了多少",每一位先枚举是多少,再枚举填什么,这样就可以从高位往低位转移了...
复杂度...因为有个,要么要么最劣吧...
容斥+压状态有个,但是容斥可以去掉,压是否卡上界卡下界。可能同时卡上下界,但是这种情况是不会同时出现的...?所以去掉的状态用哈希表存状态就是的了。

注意最高位的取值要加一,因为最后是可能会再进一位的。

其实会就很好想,但是真这么暴力的吗= = 不敢写.jpg


C.字符串

:离线,按从小到大做。建出的区间会分成若干个组,把每个组的数排序,启发式合并,维护出来后,就成了对于所有相邻对,查询是否存在。对每个维护最小的,求左端点在内,右端点的最小值?()每次二维数点。。?
笛卡尔树
某个询问区间被笛卡尔树上的一个区间包含,那么把扩展成是不会更差的(最大值不变),且只会越来越长。
所以答案要么是笛卡尔树上的一个区间,要么是顶到询问区间,要么是一端顶到笛卡尔树区间,一段是顶到询问区间,这四种情况。
的子串中最大是多少。二分答案求是否有,复杂度。(求区间是否有
对笛卡尔树上每个区间(共个)预处理,复杂度是


Day5 AM Test

http://www.zhengruioi.com/contest/250

A.无向图

建出一棵树,给每条非树边设一个不同的权值,树边权值为跨过它的非树边权值集合。一个边集是割集当且仅当边权异或和为
集合异或不好做。给每条非树边赋一个随机long long范围内的权值,每条边的权值就是跨过它的非树边的权值异或和。判断条边中是否存在异或和为的子集。线性基+高斯消元,
只适合边比较少的,边多的话Hash正确率会低。
正确率:(项数取决于加的边数)。

是割集当且仅当异或和为。一条边是割集,当且仅当其权值为。两条边是割集,当且仅当两边权值相同或一条边的权值为


B.线段树

考虑访问到哪些点。肯定在某个位置分成两部。先只考虑左边部分,都是某个节点的右儿子,假设第一个访问到了,那下一个访问的就是不停往上走碰到第一个啥...的节点的右儿子。这样连一条边能形成一棵树,然后不断向上走直到越界...?
左端点,右端点的最大的区间,作为最初始分割的位置。
然后差分后就是求树上两条链之间的距离。。树上莫队。。


C.玩游戏


Day5 PM ACM

比赛链接

C.Placing Medals on a Binary Tree(模拟)

本质是一个二进制的加法。可以直接用数组存,大于的不管,其它的每次暴力进位。


D.Routing a Marathon Race(DFS)


给定一张个点条边的无向图,每个点有一个权值。求一条从的路径,使得代价最小,输出最小代价。
一条路径的代价定义为,路径上所有点以及和这些点相邻的所有点的权值和。


容易发现,如果选择从走到,那么一定不会再回到的其它相邻节点(不如直接走过去)。
这样从点爆搜的话,每次移动都会删掉个点。
那么复杂度是:,最差情况下是,复杂度约是
注意边数是啊不除!!!(mdzz)
https://www.cnblogs.com/SovietPower/p/10573137.html


E.Non-redundant Drive(点分治)


给定一棵个点的树。在每个点你可以补充的油量,经过一条边需要花费边长的油量。你可以选择从任意一个点出发,任意在树上走直到油量耗尽或不能走(不能重复经过同一个点)。求最多能经过多少个点。


点分治。对每个分治重心,求出从到子树内某个点至少需要多少初始油量、从子树内某个点到,会剩下多少油量。然后sort一下合并即可。注意不要合并来自同一棵子树内的路径,记两个来自不同子树的最大值就行了。
https://www.cnblogs.com/SovietPower/p/10576150.html


F.Parentheses(构造)

比着样例猜一波。


Day7 AM Test

A.


...
除了都最多是三项的卷积,可以枚举三个区间容斥暴力算。
,解是


的非负解个数


B.


的后位不变;
只需要枚举,是级别的。
预处理,枚举

解不定方程的解的个数 数位dp


C.


添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注