[心之碎片II] - OI思想/技巧/套路 (持续更新)

柿子饼同学

主要是在 NFLS 集训的时候总结出来的经验...

注意题目限制寻找突破口, 看看去掉什么条件就不可做了
注意普遍性, 例如标序号不要想当然就标大小
思考做东西的本质是在干嘛, 换一种视角
正难则反
考虑贡献
总的减去不符合的
先解决降维后的问题
数据结构维护前缀和要提前加一个 0, 不然 1 是取不到的
打表
ll = 1ll * int * int
多测不清空, 亲人两行泪
拆贡献

区间, 序列问题应该想到
前缀和, 差分
尺取
值对应下标
枚举右端点, 找左端点

时间倒流 & 正难则反 & 离线!!!
把删除变成伪删除, 时间倒流变成插入

树边定向
对于一个点的权值会流到别的点等等的题要想到无向边转有向边
f(i, j, k) 表示 i 这个点和 j 个点连通, k 个在 i 的子树里的最大值
P9111 [福建省队集训2019] 最大权独立集问题

前缀和 & 差分
区间, 序列, 等差数列等等问题要想到差分
差分也可以用于整体回答答案, 例如 P4211 [LNOI2014] LCA 和 数位dp 等等场合
树上差分
放宽题目限制来做, 然后容斥或者别的去掉不合法的答案

二分
二分答案可以用于具有单调性的问题
把求答案转换为判定
平均数 (区间和 - mid > 0)
中位数 (中位数可以变成大于等于的是 1, 小于的是 -1, 做 sum)
配合数据结构发挥
求第 k 大的东西
转换为 01 序列

倍增
倍增优化时空, 一般是预处理的
需要满足区间可合并性
看到静态的, 很长的东西想到倍增
倍增矩阵优化
倍增 dp, 交换答案和状态后进一步优化空间
字符串倍增比较大小

启发式合并
并查集不能压缩的时候可以试试看
树上启发式合并可以解决一些静态统计问题, 可以预处理

可行性问题
二分
可行性dp
只需要判定是否可行, 少了很多限制, 考虑前缀 min/max/... 做

最小生成树
按照边权分类
建树然后加边

前 k 大
转化为求状态的后继状态, 发现 max 记录位置之后可以划分成两个不同的子状态
后继太多可以考虑手动安排一个顺序, 例如规定 T(a1) = a2, T(a2) = a3 ...
配合堆什么的处理

转化为 01 序列
一般配合二分

树剖
重链剖分应该维护一整个重链的总信息, 查询, 修改的时候 log 跳

走过的边不超过, 不小于...
要想 kruskal 重构树

树上
应该先判断是否连通...

树上问题先想低级算法 :
dfs栈 (把之前的祖先节点放进栈中, 双指针或者二分什么的)  
树上差分 (点上加东西, 在 lca 和 lca 父节点各自减去一个)
dfs做差 (递归进入子树之前先记录当前的答案, dfs回来之后再记录当前的答案, 这样两个相减就是子树答案了)
dfn + 差分, 把点加变成子树加, 设 s[x] 表示 x 到根的什么什么
树上倍增

树上问题的一些思考 :
按照 dfn 来二分判
lca单调性 (一个点是否是 lca 具有单调性 0000011111...)
善用 dfn 的有序性, 把无序变成有序, 把树上转换为序列
自己画图找性质
dfn 越近, lca深度越深
树上的函数 : lca, dist(点点距, 点链距), up(倍增向上跳), Insub(用 dfn 判断是否在子树中)
树上的路径分类: u 到 祖先, 祖先到 u
dep 就是 root 到 u 的 dis
随机树: 可以暴力跳 pa

字符串相关
先想哈希, 数据结构维护, 注意增量
循环节用 kmp
后缀数组, 后缀自动机

根号分治 & 要打部分分
看到总量 < 1e5 或者值域 n 要想到根号分治
暴力 + 大范围维护

在数据结构上求答案, 先记录原始的值然后更新叶子

区间dp
转移方式 : 两个区间合并, 枚举中间点然后加上过这个点的贡献, 从边界上增大区间
类似分治

某一个“天”

cc885544

有点秀

trinityee

kerln888

trinityee

cc885544