[心之碎片II] - OI 复习 1
本帖最后由 柿子饼同学 于 2024-10-24 18:58 编辑一些需要想到的点:
杂项
两个数, 看看他们相加/相乘/... 之后的值是不是定值
一个等式可以把左边右边的差值作为状态
离散化/map
1ll * int * int
注意数据类型, 开 ll 等等
带入极端数据看代码有没有问题
绝对值 : 打开分类讨论, 注意 0 的绝对值不变
排序预处理
贪心交换证明
推柿子
交换研究对象
贡献
用发展的眼光看问题, 例如数字要么是 *10 要么是 +1 这样增长的
恰好 = 不大于 + 不小于
差分解决整体问题
01序列
写数据结构的时候注意 n, m 等等东西是谁, 不要搞错了
分块决策, 可以只考虑小数据和大数据, 平衡复杂度
一个状态, 想想他的后继状态和最初的状态, 然后做
前 k 大 : 状态的后继
遇到奇偶性 : 想到分两类讨论,c 包括了奇数个 a 和 偶数个 a
哈希判定循环串 : 1 - mid-1 和 p - mid 的哈希值相同
枚举两个东西的时候尝试把一个塞进数据结构里
哈希
构造一个必要不充分问题, 然后用哈希让不充分的概率非常小
倍增
非常长的东西 / 不变的东西 / 可以差分的东西
排序
用来二分
去除重复的东西, 只算一次, 例如粉刷匠按照颜色排序
便于整体差分 LCA那题
区间问题
前缀和, 差分, 各种数据结构
遇到相等/匹配问题, 想到栈
值对应下标
枚举右端点来找左端点
尺取
删除操作
时间倒流变成加边
伪删除, 用并查集维护后缀最大值
树上问题
直径都过一个点, 从直径上的点出发求最大距离
深度, 距离, lca, 点的个数可以互相转化
深度相关想到 1-x 的链
树剖维护整个链的答案
dsu 预处理
dfn
dfs做差 : 出的答案 - 入的答案, 见天天爱跑步
树形DP
树形背包的是后记住写对架构, 注意转移顺序
子节点先继承父节点的 f , 然后回来的时候更新父节点
两个 dp 数组互相计算
子树和父节点所在树的合并
DP
注意转移顺序
可行性数组, 然后把一维作为值
刷表转化为填表来优化
数位dp 的时候注意 0, 及时除掉多余项
状压dp 技巧 : 按照 1 的个数分 st , 容斥 , mask
dp的优化
有后效性的dp试着用最短路算法
01的线性dp需要设 f(i) 表示 i 强制什么什么, 也就是当成区间染色问题, 枚举这一段多长, 染什么颜色
图论
超级原点
i - j 的最短路的子路径也是最短路
由一个起点的最短路图不存在环(<= 0 的权除外)
一条边 (x, y) 的出现次数 : 以 x 为终点的数量 * 以 y 为起点的路径数量
拓扑序
待更新... 在复习 OI（信息学奥林匹克）时，以下是一些需要注意的要点和技巧：
### 杂项
- **数值操作**：检查两个数相加、相乘等操作后的结果是否为定值。
- **等式状态**：可以将等式的左右差值作为状态。
- **数据类型**：注意使用合适的数据类型，如 `long long`。
- **极端数据测试**：用极端数据测试代码的鲁棒性。
- **绝对值**：分类讨论，注意 0 的绝对值。
- **排序预处理**：在某些问题中，排序可以简化问题。
- **贪心算法**：通过交换证明贪心策略的正确性。
- **动态视角**：考虑问题的动态变化，如数字增长方式。
- **等式转换**：恰好等于可以转化为不大于加不小于。
- **差分**：用差分方法解决整体问题。
- **数据结构**：注意变量的定义和使用。
### 哈希
- **构造问题**：通过哈希降低不充分条件的概率。
### 区间问题
- **前缀和与差分**：利用这些工具解决区间问题。
- **栈**：在相等或匹配问题中考虑使用栈。
- **枚举端点**：通过枚举右端点寻找左端点。
### 删除操作
- **时间倒流**：将删除操作转化为加边。
- **伪删除**：用并查集维护后缀最大值。
### 树上问题
- **树的直径**：从直径上的点出发求最大距离。
- **深度与距离**：深度、距离、LCA 等可以相互转化。
- **树剖**：维护整条链的答案。
### 树形DP
- **转移顺序**：注意 DP 的转移顺序。
- **子树合并**：子节点先继承父节点的状态，再更新父节点。
### 动态规划（DP）
- **转移顺序**：注意 DP 的转移顺序。
- **数位DP**：注意处理 0 和多余项。
- **状态压缩DP**：使用按 1 的个数分状态、容斥、掩码等技巧。
### 图论
- **超级原点**：在某些问题中引入超级原点简化问题。
这些要点和技巧可以帮助你在 OI 复习中更好地理解和解决问题。祝你好运！
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。 {:7_113:} {:5_106:} 加油 {:10_254:}{:10_254:} {:10_275:} {:10_256:}{:10_256:} {:5_109:}{:5_109:} {:5_91:} {:10_243:} 啊
页:
[1]