Tricks

本文记录平时遇到的 Tricks。

位运算

1. 拆位（CF 1879D）

图论

1. 分层图：如果“到达某个点时携带的历史信息”会影响之后的边权，就把这部分历史信息一起塞进最短路状态。（P1266）

博弈论

1. 先找必败态（CF2241F）

其他

1. 单调队列维护滑动窗口最值；
2. 需要维护前缀和的前缀和时，用另一个树状数组维护 $i \times a_i$，$\sum_{k = 1}^i\sum_{j = 1}^k a_j = (i + 1)\sum_{k = 1}^i a_k - \sum_{k = 1}^i k \times a_k$

错题

1. CF2230D
2. CF2215A
3. CF2211C2