线性降维技巧

题单介绍

- 前缀和-差分（区间转前缀） * P1115 最大子段和 * P3406 海底高铁 * P3397 地毯 - 离散化（压缩一维的大小） * P1097 [NOIP2007 提高组] 统计数字 * P1052 [NOIP2005 提高组] 过河 * P3138 [USACO16FEB]Load Balancing S - 双指针（关于两维的询问，通过单调性降维） * P1102 A-B 数对 * P3143 [USACO16OPEN]Diamond Collector S * P1638 逛画展 * P1083 [NOIP2012 提高组] 借教室 - 单调栈/单调队列（应用：单调性优化 DP） * P2866 [USACO06NOV]Bad Hair Day S * P3467 [POI2008]PLA-Postering * P1886 滑动窗口 /【模板】单调队列 * P2880 [USACO07JAN]Balanced Lineup G * P2251 质量检测 * P2216 [HAOI2007]理想的正方形 * P2254 [NOI2005] 瑰丽华尔兹

题目列表

  • 最大子段和
  • 海底高铁
  • 地毯
  • [NOIP 2007 提高组] 统计数字
  • [NOIP 2005 提高组] 过河
  • [USACO16FEB] Load Balancing S
  • A-B 数对
  • [USACO16OPEN] Diamond Collector S
  • 逛画展
  • [NOIP 2012 提高组] 借教室
  • [USACO06NOV] Bad Hair Day S
  • [POI 2008] PLA-Postering
  • 【模板】单调队列 / 滑动窗口
  • [USACO07JAN] Balanced Lineup G
  • 质量检测
  • [HAOI2007] 理想的正方形
  • [NOI2005] 瑰丽华尔兹