这里记录一下有些神奇的思想

整体数值偏移及后续

题目是 P1486 NOI2004 郁闷的出纳员 - 洛谷

重要的思想: 偏移,以及后序偏移的影响(也就是反偏移,去除偏移的影响,使之加上偏移之后就是原来的值0)

例如我们进行三个操作，插入工资为20的人，加工资50，插入工资为60的人。具体执行的时候，我们现在数据结构中插入一个20，然后将偏移量+50，然后再插入一个60-偏移量，既插入10。

常用

• 枚举
  • 优化枚举范围:
    • $A \to B$,可以枚举B对应的集合
  • 折半枚举 (Meet-in-the-middle): 将指数级枚举变为两次根号级别的枚举
• 集合
  • 集合的最值等于子集的最值的最值:$A = B \cup C \Rightarrow \max( A) = \max(\max (B),\max(C))$
  • 求数组最值 : $\min B =\min( \min (B \setminus c) ,\{c\} )$
  • 集合的基等于不重不漏的子集的基的和
• 前缀和与差分
  • 把区间操作转成两个点的操作,O(1)操作,O(n)查询单点的值
  • 平数: 最少多少次区间+1或-1操作后,所有的数字一样大
• 贪心
  • 交换验证法:
    • 最优方案转换成目标方法:区间选点,最小生成树
    • 通过邻项交换证明贪心策略的正确性，常用于排序相关问题。
  • 反悔贪心: 先做出一个看似最优的决策，之后如果发现有更优的决策，可以撤销之前的选择。常使用优先队列实现。
  • 排序后贪心: 对元素按某种规则排序后，按顺序处理。
• 二分: 数据具有二分性
  • 答案二分: 解决"最大化最小值"或"最小化最大值"问题。
  • 数据二分: 在单调序列上查找。
• 双指针/滑动窗口
  • 在序列上维护一个区间，通过移动左右端点来解决问题。
  • 1. 有序 2. 及时排除不可的点,
• 动态规划
  • 将问题分解为重叠的子问题，通过记录子问题的解来避免重复计算。
  • 常见类型: 线性DP, 背包DP, 区间DP, 树形DP, 状压DP, 数位DP。
• 数学
  • 异或运算的值与1的奇偶数量右观
• 分治
  • 将大问题分解为小问题，递归求解，再合并结果。
  • 常见应用: CDQ分治, 整体二分。
• 倍增
  • 静态区间信息统计
  • 结合率,合并性: $jump(i,x+y) = jump(jump(i,x),y)$
  • 本质统计的是两点边上的信息
  • 常见应用: ST表 (RMQ问题), 树上LCA (最近公共祖先)。
• 构造
  • 根据题目要求，直接构造出一种合法的解。
• 思维转换/建模
  • 正难则反: 直接求解困难时，考虑求解其对立面（补集）。
  • 图论建模: 将问题抽象成图论模型来解决。