8.24-8.30 学习记录

发表于 更新于 分类于

8.24

完善了区间贪心的笔记。
反悔贪心速刷：

  • 种树：将 “替换当前决策” 的价值加入堆
  • 建筑抢修：用当前决策替换 最劣的那个决策
  • Buy Low Sell High：股票买卖经典转化之，“i 买 k 卖 = i 买 j 卖 j 买 k 卖”。撤销 j 卖这次决策，只需要再把它买回来就好了。
  • Least Cost Bracket Sequence：括号序列经典性质之，“一个括号序列合法，当且仅当在任何时刻，左括号数量 >= 右括号数量，且整体数量相等”。先全选决策一，出现非法时，将决策一替换为决策二。先把决策做完，再考虑调整。
  • Olympiad in Programming and Sports：先全放入队1，再调整。
  • 社团招新：先不考虑约束随便放。在找到唯一超限集合进行调整。
  • 拯救小矮人：涉及到顺序的问题考虑排序。临项交换证明排序规则。反贪。

模拟赛。
补 T4。T3 力竭了。

8.25

模拟赛。
补题。
P12650（未码）：分类讨论好题。

8.26

模拟赛。
模拟赛+补题。
CF888G：xor mst 板子
U694141：区修想差分，差分数组与原数组是双射。生成任意序列的本质是，可以独立的修改每一个点，而不改变其他点。翻转操作具有传递性质。转化之后就是 xor mst 板子。
复习一下。

8.27

补题：

  • U694143：反悔贪心。细节很多。
  • P5798：通过排序解决后效性。

AT_arc183_c：区间最值位置限制的排列计数。考虑相对大小。枚举最大值坐标。