【Trick】常见小trick

LinkyChristian · 2025-10-20 22:33:13 · 个人记录

放宽限制

很经典的Trick，当题目的限制难以计算和维护时，考虑是否存在一种更平凡的维护条件，而能使得题目的限制在这种条件下自然称为最优解。

差分贡献

形态1：类似 a_i=k 提供 k 贡献转化为对每个 i ，使所有 a_i \geq i 提供 1 的贡献。

形态2：对每个最终结果为 pos 的求贡献，转化为对每个最终结果 \le pos 的求贡献。

组合意义

将一些有组合意义的式子转化为其组合意义，并进行dp

整除分块

当贡献仅与 n/i 相关时，由于不同的 n/i 只有 O(\sqrt{n}) 级别，因此可单独考虑每种 n/i ，用整除分块处理。