CF中的yy算法

OranJun · 2023-08-20 08:02:47 · 个人记录

• bui：

  1. CF1927G

     • dp[i][j]

       表示覆盖到前i，上一个覆盖的是j，发现需要记录i是否被用过，再开一维0/1记录i是否已经使用

     • 转移时有两种方式
       • 取 j \rightarrow i-k 的数往右延伸
       • 取 l > i，转移到 f[l][i/j]

  2. CF1928E

  3. 考虑最坏情况时，一定要让每种情况都成立

  4. 当k \leq 20思考与k有关。

• 数学入门

  1. 计算期望，\sum后取平均
  2. 期望路径长度
  3. 位运算按位考虑，贪心

• 单调队列

  1. two-pointer 固定右端点，观察左端点是否单调 WIL

• CDQ分治

  1. 偏序优化DP