杯水车薪的，该不会还不会的数据结构试题调研

Reference

非原创，主要来源博客和洛谷题解，原作者和链接在此处统一注明，文中会如有侵权请联系删除。
Ref.1. OI Wiki
Ref.2. @Develop

啥也不会的数据结构

关于前缀和

对区间和分析，变成两数关系，不支持动态
NJUNTOJ 4

关于差分

对区间所有值动态操作O(1)，查具体值慢O(n)
LUOGU 1083

关于单调队列，单调栈（和优先队列）

一些基本特征

• 延迟判断：一些情况需要后续取舍
• 逆序结构：“当发现比你小还比你强的OIer的时候，你就应该出队了。”
• 局部最优：必须满足需要的是局部最优，且能求出局部最优（局部最优在出栈时）
• 额外条件（优先队列）:这个条件还必须具有FIFO性质

习题

• LUOGU P1901 单调栈，比较简单，两侧跑一遍即可。

关于树状数组

维护的信息必须满足结合律和可差分。

核心性质

时刻注意和二进制编码的联系

• 对于任意 ，当且仅当是的祖先，c[u]真包含于 （上面几条性质的总结）。这就是树状数组单点修改的核心原理。
• 设 ，则其儿子数量为 ，编号分别为 。
  举例：假设的二进制编号为 ，则有三个儿子，二进制编号分别为 。

基本操作

• LUOGU
  只看了区间加区间和。

规约不到的基本问题

子段和(Ref.2)

chapter1最大子段和

• 枚举区间起点和终点，暴力求和；
• 枚举左右端点时 可以动态维护 的前缀和；
  预处理前缀和，枚举左右端点时计算；
  枚举中点,分别往前面和后面计算一个包含center的最大子段和，预处理前缀和一次判断是 的;
  考虑 ，设状态 为包含且以 结尾的最大值，方程： ；
  一个以结尾最大子段的定义： ，计算可以动态维护一个前缀和的最小值;
  chapter2子段长度不大于的最大子段和
  仍然考虑最大子段和的定义，动态维护 ，使用单调队列维护，队列中的数递增(参考滑动窗口);
  chapter3子段长度不小于m的最大子段和
  longn 可以将分治思想中的枚举中点改成枚举一个中段，同理；(但是显然需要枚举一个段的话编码难度会提升)
  先计算一次不限长最大子段和，再从头开始，枚举每一个长为的子段，在它前面拼上以结尾的最大子段和;方程: ，最后取一个;
  动态维护 ，比上一种编码简洁，只需要一次循环，维护前缀和；

最长上升子序列(Ref.2)

最长公共子序列(Ref.2)

最长公共上升子序列(Ref.2)

最长回文子串(Ref.2)

最长回文子序列(Ref.2)

做题记录

Principle: Sequent 2 [IK] s then alter to green, sequent 2 [FW] s then alter to yellow. Do nothing if [AJ].

• [IK] Immediate Kill
• [FW] Fei Wu
• [UD] Can be defined…
• [AJ] Adjust the solution after read the standard

1. 11/20 P1090 哈夫曼树，用堆维护即可(nlogn) [IK]
2. 11/21 P1212 BF [UD]
3. 11/22 P1213 菜的一P，还原成同余方程BF即可，注意同余方程的解空间是有限的！有限的！有限的！（须满足结合律）其实是个群论问题 [UD]
4. 12/x P1118 杨辉三角，枚举，剪枝 [IK]
5. 12/6 P1209 注意:有限状态的记忆化搜索其实就是DP！(虽然这题就是一个贪心，逆向思维啊，间距连接其实就是断开，最小化一个量可以考虑把它最大化在尽可能减小) [UD]