[通知]
由于LL喜新厌旧另置新书,这篇博客目测,会无限咕下去
大概会在十月及以后再次拿起
[进度]
20/34
咿呀,还有14章了QwQ
我太蒻了
连一本通都没刷完
是分块哒(^~^)
例题解析请看书啦
当然如果有些题我很欢喜,会吧代码存在博客里
第一部分 基础算法
第 1 章 贪心算法
总结:贪心的习题大致与例题一个思路
一般来说都是强行暴力,也不一定,反正实在没法,贪心一发
注意数据的处理
1.
对于每次产生的新数放入序列中重排,根据规律进行下次累计
2.累加,若大于,则新计
3.对时间段结尾进行排序,找到第一个大于等于当前时间的时间段左端点
4.重要的掐着时间先弄
5.对于1,1~2……,1~n分时间段贪心
6.
要证一波规律,=》得出中位数结论
第二部分
第3章 Trie
1.Immediate Decodability
在建trie时,对串结尾打标记,并且另外标记访问路线
如果有一个串的结尾被访问过,或经历过一个结尾则存在
2.L 语言*
对trie强行暴力dp水过
反正我用的是AC自动机
3.
同Immediate Decodability标记改成统计和就好
4.
你先变后缀为前缀,弄进trie里
在根据根节点重构树,找出size最小的子树,放前面
5.
统计出每个点到根的xor,塞进去
最后遍历,求find()最大
第三部分 图论
第 1 章 最小生成树
1.
将发电站费用当做一条电网弄到最小生成树里去
2.
每个连通块的大小*要合并的连通块的大小*(连接路径的权值+1)
相当于给两个连通块里的点分别加了一条路,保证连通块里的完全图
3.你每次选这性不取那些在最小生成树的边以及未在但与他们相等的边
4.
二分,以图恰好选need个白点
5.6.
第 2 章 最短路
1.
单源最短,在遍历找个最大值
2.维护严格次小路
3.spfa+cnt计数
4.状压+dijkstra(话说无负权图跑dijkstra令人极度舒适)
5.正反跑两遍spfa就好
6.7.第 5 章 强连通分量
1.
第一问试求缩点后的图中的没有入度的点 个数
第二问就是让你将找到在没有入度的点个数与没有出度的点个数的最大值
以求将他们弄成一个新的环
2.上题一问
3.
不能受贿并且没有被遍历的则无法掌握
如果可以,我们找出缩点没有没有入度的环的最小贿赂值,累加
4.
缩点后,如果环中有bar,则标记;
你再跑一遍最短路就odk了
5.2-sat的入门题
第 6 章 割点和桥
1.
求割点个数
2.求确定两点路线上的割点
3.求桥的数量
4.求一个割点所连桥的最大数+原本不连通的块
5.割点所连道路数(前面的儿子大小*新生儿子的大小+size*外面数)
第 7 章 欧拉回路
模板
2.
分别统计连通块,以及各自的笔画数(cnt[d[i]>2+1]>>1)
3.欧拉回路,求具体路径,搜一搜
4.同上,直接枚举,暴力剪枝
5.将0放入特殊的点内,分类枚举,计算
6.第四部分 数据结构
第 1 章 树状数组
1.
模拟,模板
2.查分,区间修改,单点查询
3.二维树状数组模板
第 2 章 RMQ 问题
1
模板(话说为什么每次都要打成moban)
2.
统计一次最大,一次最小,相减
3.
统计最近的两家客栈是否存在<=P的咖啡店+dp
第 3 章 线段树
1.
模板,话说这道题可以用单调队列维护
2.
对于区间都是1的打上标记,下一次跳过
3.
维护加,乘
累乘时,累加也要先乘
第 4 章 倍增求 LCA
1.
模板*1
2.模板*2
3.可以枚举三个LCA暴力求解
也可以用三个点dep-三个LCA的dep
4.第 5 章 树链剖分
1.
裸题,不解释
2.
解析同上
3.维护是否被安装,并统计个数
4.做好邻接点的相同-1
5.动态开点权值线段树,不解释
第 6 章 平衡树 Treap
莫想了,LL只会splay,这些题都是用splay水过的
1.
用优先队列(话说splay,常常用优队存些值)累计一下要领的宠物,或领养者
找一下前驱和后继,判断一下
2.
你不可能更改以前人的工资
你只有在现存的水平值内
对新放进去的工资,以及查询做调整
3.正所谓模板题放最后
第五部分 动态规划
第 1 章 区间类动态规划
话说为何区间dp为什么那么喜欢与高精捆绑?
其实区间dp都是格外相似的
不外乎再加点特殊判断以及拆环的技巧(弄成2*n,选max(1,n),(2,n+1)……)
//在下先说,反正以下只有一道题我做了,其他都是一眼题,出锅勿扰
1.
在左右端点配对时,f[i,j]区间直接等于f[i+1,j-1]与f[i,j]的最小值
2.根据条件,区间dp
3.一行一行的区间dp
第 2 章 树型动态规划
在区间内枚举中间点,dp
2.
求最长链,再记录答案
3.
最小独立集
4.
最小独立集+强制选择
5.
基环树+独立集+破环,强制选择
第 3 章 数位动态规划
1.
记录每次取模后的数,累加累取模到最后
2.
记录上一位所选的数字last
每一次不能选4,last为6时不能选2
3.
记录各个位上数字和取模,以及同1的取模后的数;
用一种玄奇思解数学,平方和
4.记录每个数在统计路线上中,出现过多少次,有无前导0
第 4 章 状态压缩类动态规划
1.
你将三进制转成二进制
2.连续记录前两维,转移时注意维护中间维一致性
3.位运算好题,状压水题
第六部分 数学基础
第 1 章 快速幂
1.
模板
2.模拟+模板
3.总共有m^n种状态
其中不越狱的有m*((m-1)^(n-1))种
第 2 章 质数
首先筛质数
1.
找到能整除他的质数,不停除直到没有这个因数
2.将所有数带进去,在范围内刷一遍
再减去自身
3.从小到大枚举奇质数,遇到则输出
4.总而言之,是质数就输出1,合数输出0,
统计是否有合数,总共涂多少颜色
5.
分解下式子,求一个数的约数个数
第 5 章 矩阵乘法
1.
模板
2GT.kmp,先写出dp方程式,再用矩阵
3.