[心之碎片II] - OI 复习 1

柿子饼同学

一些需要想到的点:

杂项
两个数, 看看他们相加/相乘/... 之后的值是不是定值
一个等式可以把左边右边的差值作为状态
离散化/map
1ll * int * int
注意数据类型, 开 ll 等等
带入极端数据看代码有没有问题
绝对值 : 打开分类讨论, 注意 0 的绝对值不变
排序预处理
贪心交换证明
推柿子
交换研究对象
贡献
用发展的眼光看问题, 例如数字要么是 *10 要么是 +1 这样增长的
恰好 = 不大于 + 不小于
差分解决整体问题
01序列
写数据结构的时候注意 n, m 等等东西是谁, 不要搞错了
分块决策, 可以只考虑小数据和大数据, 平衡复杂度
一个状态, 想想他的后继状态和最初的状态, 然后做
前 k 大 : 状态的后继

哈希
构造一个必要不充分问题, 然后用哈希让不充分的概率非常小

倍增
非常长的东西 / 不变的东西 / 可以差分的东西

区间问题
前缀和, 差分, 各种数据结构
遇到相等/匹配问题, 想到栈
值对应下标
枚举右端点来找左端点

删除操作
时间倒流变成加边
伪删除, 用并查集维护后缀最大值

树上问题
直径都过一个点, 从直径上的点出发求最大距离
深度, 距离, lca, 点的个数可以互相转化
深度相关想到 1-x 的链
树剖维护整个链的答案
dsu 预处理
dfn
dfs做差 : 出的答案 - 入的答案, 见天天爱跑步

树形DP
树形背包的是后记住写对架构, 注意转移顺序
子节点先继承父节点的 f , 然后回来的时候更新父节点
两个 dp 数组互相计算
子树和父节点所在树的合并

DP
注意转移顺序
可行性数组, 然后把一维作为值
刷表转化为填表来优化
数位dp 的时候注意 0, 及时除掉多余项
状压dp 技巧 : 按照 1 的个数分 st , 容斥 , mask
dp的优化
有后效性的dp试着用最短路算法

图论
超级原点
i - j 的最短路的子路径也是最短路
由一个起点的最短路图不存在环(<= 0 的权除外)
一条边 (x, y) 的出现次数 : 以 x 为终点的数量 * 以 y 为起点的路径数量
拓扑序
待更新...

FishC

在复习 OI（信息学奥林匹克）时，以下是一些需要注意的要点和技巧：

### 杂项
- **数值操作**：检查两个数相加、相乘等操作后的结果是否为定值。
- **等式状态**：可以将等式的左右差值作为状态。
- **数据类型**：注意使用合适的数据类型，如 `long long`。
- **极端数据测试**：用极端数据测试代码的鲁棒性。
- **绝对值**：分类讨论，注意 0 的绝对值。
- **排序预处理**：在某些问题中，排序可以简化问题。
- **贪心算法**：通过交换证明贪心策略的正确性。
- **动态视角**：考虑问题的动态变化，如数字增长方式。
- **等式转换**：恰好等于可以转化为不大于加不小于。
- **差分**：用差分方法解决整体问题。
- **数据结构**：注意变量的定义和使用。

### 哈希
- **构造问题**：通过哈希降低不充分条件的概率。

### 区间问题
- **前缀和与差分**：利用这些工具解决区间问题。
- **栈**：在相等或匹配问题中考虑使用栈。
- **枚举端点**：通过枚举右端点寻找左端点。

### 删除操作
- **时间倒流**：将删除操作转化为加边。
- **伪删除**：用并查集维护后缀最大值。

### 树上问题
- **树的直径**：从直径上的点出发求最大距离。
- **深度与距离**：深度、距离、LCA 等可以相互转化。
- **树剖**：维护整条链的答案。

### 树形DP
- **转移顺序**：注意 DP 的转移顺序。
- **子树合并**：子节点先继承父节点的状态，再更新父节点。

### 动态规划（DP）
- **转移顺序**：注意 DP 的转移顺序。
- **数位DP**：注意处理 0 和多余项。
- **状态压缩DP**：使用按 1 的个数分状态、容斥、掩码等技巧。

### 图论
- **超级原点**：在某些问题中引入超级原点简化问题。

这些要点和技巧可以帮助你在 OI 复习中更好地理解和解决问题。祝你好运！

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

很cool的阳

sunshine_8205

学习编程中的Ben

加油

trinityee