Class 2
看到这里的读者,我会默认你至少已经学会了包括线段树的等基本的数据结构和算法,并且掌握了一些基础的数论知识,但这个Class 2的题目我并不希望涉及比线段更高级的知识点,
交换（Easy Version）
普通的树形背包计数dp问题,但这涉及一个并不明显的时间复杂度分析的问题,详细证明可以看别人的文章
有关hash的问题
P12197 Hash Killer I
P12198 Hash Killer II
P12199 Hash Killer III【Open Problem】
这三个是一起的,可以很好地知道字符串哈希被精确hack的方式,以及改进算法的方式
可以使用哈希来判断集合是否满足特定限制条件
比如判断某个集合是否出现偶数次,这也需要我们构造出一个符合期望的哈希方式
F - Adding Chords
这题涉及两个问题
如何判断圆上弦是否相交,即\(l_1<l_2<r_1<r_2\)弦会相交
有关利用异或哈希判断是否区间内的数出现了偶数次
有关笛卡尔树
E. Yet Another Array Counting Problem
笛卡尔树可以用线性的时间很好的解决有关区间最值问题,当然很多时候仅使用单调栈即可,不必使用笛卡尔树,不过似乎都要用到栈
值得一提的是,使用st表记录最值的位置,而不是值本身,可以近似地实现笛卡尔树的效果
有关组合数学须知,除了高中生会有的基础的组合数学知识,这里记录了一些需要额外掌握的知识组合数学进阶,这里的知识可以应对很多题目,不过这文章里有些地方写错了,需要甄别一下
F. Learning Binary Search
这道题同时用到了组合数学知识,区间最值的问题,以及多次前缀和实现更好的区间修改,可以很好的拓展知识面
P6824 「EZEC-4」可乐
v_calc
利用Trie优化有关异或的数位dp
P1168 中位数
有关对顶堆,可以优秀地维护前k小的值
有人可能图方便使用set代替堆,但是堆的原理和实现更简单,所以单从时间的角度看,堆更好一点
有关pb_ds库
里面有现成地优秀的数据结构可以使用(主要是平衡树,其他不太用得到),但是一定一定要注意
pb_ds（Policy-Based Data Structures）只能在 GNU 的 g++ 编译器（搭配 libstdc++ 标准库）下使用，不支持 MSVC（Visual Studio）、Clang（默认库）等其他编译器
E. Relearn through Review
P10463 Interval GCD
实际涉及两个需要注意到点
- 一个数最多做 log 次改变其值的 gcd
- \(gcd(a1,a2,a3,a4)=gcd(a1,a2-a1,a3-a2,a4-a3)=gcd(a1,d2,d3,d4)\),这样区间修改可以转化成在其差分序列上得单点修改,其中\(d_i=a_i-a_{i-1}\),问题得以简化
P3403 跳楼机
有关同余最短路,需要见过至少一次
P3372 【模板】线段树 1
这只是一道模板题,但是这题存在树状数组解,树状数组解可以理解成单纯的和式变换,进而能够解决下面这题
H. Hard Demon Problem
这题需要用到树套树,但其实理解树状数组的本质的后,树状数组可以视作是线段树的阉割版
所以我们可以写出可以说是最简单的树套树,即树状数组套树状数组
E. Kevin and And
这招太狠了烤学妹
用到了没见过很难察觉的性质
我总结,抽象出一个简单的题目来
给定长度为\(n\)的数组\(A\)
存在一个操作,每次操作可以对数组中一个元素\(A_i\)进行操作
且对第\(i\)个数执行第\(j\)操作之后都产生一个\(value_{i,j}\)
现在我们要在执行k次操作后使得产生的\(value\)的总和最大
如果存在一下性质,可以很简单的直接贪心求解
\(\forall i\)满足\(value_{i,j}\)是一个非严格单调递减的函数
贪心策略为每次操作选当前\(value_{i,j}\)最大的操作,一定可以得到最优解,证明见题解
不过题目肯定不会直接告诉你\(value\)是什么,需要分析把什么视作\(value\)可以很好的利用上面这个性质求解
了解这个之后,可以轻松解决上面两题
B. 精神胜利
基于随机性的题目
和对数据范围进行分类论
(其实自己尝试过出题的话,在造数据的时候,会很容易的发现,数据如果是纯随机出来的话,大多情况都是很垃圾测试数据,这题就会被秒杀)
G. Path Summing Problem
这题同样的是数据的分类讨论
在尝试求解时,发现在特定的数据范围下,求解会变得很简单时,可以尝试这类方法
E. Minimum Path
D. Gifts Order
同样没见过难以注意到的可利用的性质
需要发现,自己需要求解复杂问题的最优解 实际上完全等于另一个简单问题的最优解
这里的所谓的简单问题,一般指一定程度放宽条件后的题目
P8600 [蓝桥杯 2013 省 B] 连号区间数
这题并不那么特殊,但是是练习的好题,主要需要两个东西
其一需要一定程度上理解单调栈的本质是在干什么,只是认识单调栈的代码是没用的
其二是一个为了方便计数,要利用性质 把判断区间是否连续的 等式转化成不等式
C2. Maple and Tree Beauty (Hard Version)
这题可以查漏补缺一点知识点和注意力
知识点
背包9讲模板题不多说
bitset可以非常好的优化只有01关系的问题,如dp
但是bitset长度只能设置为常量,实际写题还是更需要变长的bitset
需要手动实现,原理就是利用int64状态压缩,实现并不复杂,或上网搜索模板
需要补充的注意力
\(m_1+m_2+m_3+...+m_k=n\)
其中\(m_i\neq m_j,i\neq j\),当然,\(m\)要求都是正整数
注意到\(k<\sqrt n\)
也就是说,m至多有\(\sqrt n\)种不同的值
(当然我这写的都是估算)
常见于根号分治
常见的形式是,\(n\)等于数组长度,或别的与n相关的属性,对于这题就是树的节点个数
或者是D. Hero of the Kingdom这样的计算题