avatar
文章
83
标签
20
分类
13
首页
标签
分类
友链
关于
wjyppm's BlogOI大技巧 返回首页
搜索
首页
标签
分类
友链
关于

OI大技巧

发表于2025-07-14|更新于2025-12-06|笔记
|总字数:9|阅读时长:1分钟|浏览量:
OI大技巧
https://worldcpu.github.io/posts/a3f4a75/
作者
wjyppm
发布于
2025-07-14
更新于
2025-12-06
许可协议
CC BY-NC-SA 4.0
技巧
cover of previous post
上一篇
根号分治
1. 介绍与引入 没有前言，懒得写了。 根号分治，本质是平衡规划思想（大纲 9 级），在预处理和询问复杂度中寻找平衡，我们通常用根号作为问题规模的分界线。我们确定一个界限 BBB，小于 BBB 的暴力预处理，大于的回答一次时间只需要 nB≤n\dfrac{n}{B}\le \sqrt{n}Bn​≤n​ ，那么整个题目就可以做到 O(nn)O(n \sqrt{n})O(nn​)。 根号平衡思想，是平衡规划思想中重要的内容，例如空间平衡，时间平衡，根号滚动数组，都可以用这种思想。 我们以一道例题引入：CF797E Array Queries 这种操作我们发现没有什么很好的性质来维护，因为 apa_{p}ap​ 和变化的 ppp 是有关的。这两个关系是相互制约的，如果我们只关注一个肯定是不行的。怎么办？ 首先我们先想暴力，我们有两种想法： 预处理所有 p,kp,kp,k 的答案。 暴力模拟。 第一个虽然可以 O(1)O(1)O(1) 回答但是预处理时间空间复杂度 O(nk)O(nk)O(nk) 无法承受，而暴力算法时间复杂度一次是 O(nk)O(\dfrac{n}{k})O(kn...
cover of next post
下一篇
NOI2025_机器人
不是，近 5 年 NOI 从来没考过绿吧，不会吧？ 形式化题面如下： 给定一个有向图，包含 nnn 个节点和 mmm 条有向边。边有长度。对于每个节点 xxx，其出边被编号为 1→dx1\to d_{x}1→dx​（dxd_{x}dx​ 是出边数量）。从 111 号点出发，初始有一个变量 p=1p=1p=1，按以下规则移动： 若当前位于节点 xxx 且 p≤dxp\le d_{x}p≤dx​，则走 xxx 的第 ppp 条边，移动到相邻节点 yyy。花费为边的长度。 修改参数 ppp： 若 p<kp<kp<k，则令 p←p+1p\leftarrow p+1p←p+1，花费为 vpv_{p}vp​。 若 p>1p>1p>1，则令 p←p−1p\leftarrow p-1p←p−1，花费为 wpw_{p}wp​。 求 1→i1\to i1→i 的最小花费，若无法到达输出 −1-1−1。 一眼分层图，题目转化为建 kkk 层的有向图，每次跳不同层要花费规则上指定的代价，求单源最短路跑 Dijkstra。但是空间复杂度是 O(nk)O(nk)...
评论
avatar
wjyppm
高中蒟蒻信竟生
文章
83
标签
20
分类
13
Follow Me
公告
👋🏻我是PPM，一个热爱编程和信息学竞赛的高中生，喜欢分享做题经验。本博客中所有 latex 公式均可以选中后复制哦😊

❓有问题欢迎提问，确保内容有意义。如需联系我，欢迎通过邮箱联系我！📧

嗷嗷！热烈欢迎🤪！来自

的朋友，你好呀！
你的网络IP为：***.***.***.***

目录
  1. 1. 0.1 模拟赛技巧
    1. 1.1. 比赛策略
    2. 1.2. 做题
    3. 1.3. 墓志铭
    4. 1.4. 规划时间必须留出对拍！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！
    5. 1.5. 做题 Trick
  2. 2. 1. 数据结构+离线算法专题
    1. 2.1. 1.1 问题转化
      1. 2.1.1. 删除操作看作回退
      2. 2.1.2. 维护值域较小的分段函数
      3. 2.1.3. 线性操作使用矩阵维护
      4. 2.1.4. 高精度，但是是 x 次
      5. 2.1.5. 强制在线转离线思考
    2. 2.2. 1.2 考虑限制
      1. 2.2.1. 区间范围也是二维偏序
      2. 2.2.2. 一个序列整体加一个数后与另一个序列相同
    3. 2.3. 1.3 确定维护对象
      1. 2.3.1. 尽量不要维护特定值信息
    4. 2.4. 1.4 思考如何维护
      1. 2.4.1. 等效操作思想
      2. 2.4.2. 用线段树维护的技巧
      3. 2.4.3. 切换主体思想
      4. 2.4.4. 每个子区间的区间最值信息
      5. 2.4.5. 值域分块
      6. 2.4.6. 整体标记法
      7. 2.4.7. 维护链的数据结构与均摊复杂度
      8. 2.4.8. 单调栈维护最值更新(离线)
      9. 2.4.9. 倍增二分思想
      10. 2.4.10. 重链刨分平衡复杂度（链分治）
        1. 2.4.10.1. 轻子树与重子树分治
        2. 2.4.10.2. 树上维护相邻点信息
    5. 2.5. 1.5 常见模型
      1. 2.5.1. 判断一个集合和另一个集合是否相等（或出现次数）
      2. 2.5.2. 换维扫描线
      3. 2.5.3. 对询问建立扫描线
      4. 2.5.4. 区间右端点扫描线
      5. 2.5.5. 对询问进行差分（离线）
      6. 2.5.6. 子区间计数问题
      7. 2.5.7. 二进制分组（强制在线）
    6. 2.6. 1.6 根号相关
  3. 3. 2. 图论专题
    1. 3.1. 图论模型的建立
      1. 3.1.1. 一些杂项
      2. 3.1.2. 要么取…要么不取…
      3. 3.1.3. 最短路树
      4. 3.1.4. 区间LCA或LCA限制（虚树）
      5. 3.1.5. 难以处理的全局限制
    2. 3.2. 图结构的分析与建立
      1. 3.2.1. 操作具有连锁反应
      2. 3.2.2. 缩点
      3. 3.2.3. DFS 树与生成树
      4. 3.2.4. DAG 简化问题
    3. 3.3. 问题转化
      1. 3.3.1. 用图论表示贡献
      2. 3.3.2. 一类仅贡献一次
      3. 3.3.3. 度数与连通性
      4. 3.3.4. 拆分贡献法的应用
      5. 3.3.5. 可达性转连通性
      6. 3.3.6. 点边互换
      7. 3.3.7. 环问题
      8. 3.3.8. 边权转点权，点权转边权
      9. 3.3.9. 链操作的本质（边 -> 点）
    4. 3.4. 寻找结论
      1. 3.4.1. 拓扑覆盖问题
      2. 3.4.2. 双图策略寻找限制
    5. 3.5. 经典算法的拓展应用
      1. 3.5.1. 最短路
      2. 3.5.2. 连通性
      3. 3.5.3. 拓扑排序
      4. 3.5.4. 其他
    6. 3.6. 树问题
      1. 3.6.1. 问题转化
      2. 3.6.2. 树上算法
      3. 3.6.3. 常见模型
  4. 4. 3. 贪心法
    1. 4.1. 3.1 贪心
      1. 4.1.1. 区间操作转差分表示
    2. 4.2. 3.2 反悔贪心
  5. 5. 4.一般DP
    1. 5.1. 一般 DP 过程
      1. 5.1.1. 转化问题
        1. 5.1.1.1. 方格图上的路径问题
        2. 5.1.1.2. 匹配问题的 DP
        3. 5.1.1.3. 覆盖所有点的状态设计
        4. 5.1.1.4. 高维问题转不相关低维问题（分离限制思想）
        5. 5.1.1.5. 操作或限制具有某些特殊性结构
        6. 5.1.1.6. 存在性问题转限制性问题
      2. 5.1.2. 发掘性质
        1. 5.1.2.1. 发掘性质的时机？
        2. 5.1.2.2. 多过程多步骤的思考角度
        3. 5.1.2.3. 区间和与前缀和转差分
        4. 5.1.2.4. DP和贪心的结合
        5. 5.1.2.5. 贡献延后计算
        6. 5.1.2.6. min 和式子转匹配（贡献延后）
        7. 5.1.2.7. 限制过松？强化限制
        8. 5.1.2.8. 模数及其奇怪
        9. 5.1.2.9. 求深度和
        10. 5.1.2.10. 排列连边转化（排序）
        11. 5.1.2.11. 答案对 2 取模
        12. 5.1.2.12. 当限制主体量过大，考虑归纳或递归方法描述限制
        13. 5.1.2.13. 答案的 k 次方但 k 不大
        14. 5.1.2.14. 将期望拆开来算
        15. 5.1.2.15. 排列与出现次数
        16. 5.1.2.16. 不断转化等价模型
        17. 5.1.2.17. 题目有双关键状态量
        18. 5.1.2.18. 对答案发掘性质（最后一招）
      3. 5.1.3. 选定 dp 主体
        1. 5.1.3.1. 多个最值的笛卡尔树的 DP 问题
        2. 5.1.3.2. 多边形转笛卡尔树建树
        3. 5.1.3.3. 去除无需计算的状态，重设 DP 主体
        4. 5.1.3.4. 区间最大值，枚举最大最小值转移
        5. 5.1.3.5. DP+自动机
        6. 5.1.3.6. 连续段DP
        7. 5.1.3.7. 排列上扫描线（插入法）
      4. 5.1.4. 设计 dp 状态
        1. 5.1.4.1. 保留与代价计算有关的量
        2. 5.1.4.2. 动态的状态设计
        3. 5.1.4.3. 全局变量或操作放入局部状态内
        4. 5.1.4.4. 状态和答案对换
        5. 5.1.4.5. 离散化减小状态
        6. 5.1.4.6. 等价类状态
        7. 5.1.4.7. 操作序列会使得答案算重
        8. 5.1.4.8. 确定顺序类型的题目
        9. 5.1.4.9. 枚举法确定决策以及其运用
        10. 5.1.4.10. 设计相反的状态（正难则反）
      5. 5.1.5. 确定转移顺序
        1. 5.1.5.1. 一些类型
        2. 5.1.5.2. 答案是 0/1 交错组成的答案
      6. 5.1.6. 寻找子问题
        1. 5.1.6.1. 一些感想
        2. 5.1.6.2. 技巧
      7. 5.1.7. 考虑如何转移
        1. 5.1.7.1. 转移过程过大
        2. 5.1.7.2. 将最大值不等式限制融入方程或转笛卡尔树转移
        3. 5.1.7.3. 树形DP但儿子向父亲不好转移
        4. 5.1.7.4. 微元贡献法
        5. 5.1.7.5. 转移上的优化（分割点证明）
        6. 5.1.7.6. 如果贡献很难算(具有决策单调性)
        7. 5.1.7.7. 矩阵DP二分转移优化
    2. 5.2. DP 优化
      1. 5.2.1. 势能分析
      2. 5.2.2. 讨论法
      3. 5.2.3. 数据结构优化 DP
      4. 5.2.4. 组合意义优化
      5. 5.2.5. 保留有效状态
        1. 5.2.5.1. 将状态定义为和式
      6. 5.2.6. 费用计算优化
      7. 5.2.7. 解决巨大数据范围
      8. 5.2.8. 神秘优化
    3. 5.3. DP 模型
      1. 5.3.1. 树形 DP
      2. 5.3.2. 状压 DP
      3. 5.3.3. 背包
      4. 5.3.4. 计数 DP
    4. 5.4. 计数小技巧
  6. 6. 6. 字符串
    1. 6.1. 本质不同的回文串不超过 n 个
    2. 6.2. 重复类型问题分块思想（关键点思想）
    3. 6.3. 循环同构匹配
    4. 6.4. 字符串匹配代数化
  7. 7. 7.数学
    1. 7.1. 7.1 数论
      1. 7.1.1. 平方数的性质
      2. 7.1.2. 模运算的套路
      3. 7.1.3. 鸽巢原理
      4. 7.1.4. 质因子太多啦怎么办？
  8. 8. 8. 网络流与图匹配
    1. 8.1. 量的意义
    2. 8.2. 发掘性质
    3. 8.3. Little Trick
    4. 8.4. 图匹配
    5. 8.5. 常见模型
  9. 9. 9. 构造
    1. 9.1. 构造循环操作序列
    2. 9.2. 棋盘染色方法
    3. 9.3. 限制很松，考虑强化限制
    4. 9.4. 通过限制次数下的交换还原排列
    5. 9.5. 递归方法构造（子问题合并，归约与增量）
    6. 9.6. 对于树的构造方法
    7. 9.7. 答案与总方案的占比
    8. 9.8. 构造满足特定值的方案
    9. 9.9. 复杂操作类型的题目
    10. 9.10. 树上所有点被覆盖的选取路径条数（下界）
    11. 9.11. 无向图上构造树上内容
    12. 9.12. 答案取值很少
  10. 10. 10. 计数
    1. 10.1. 问题转化
    2. 10.2. 容斥与反演
  11. 11. 11.Unknown
    1. 11.1. 势能法与均摊法
      1. 11.1.1. 一些势能分析与均摊技巧
        1. 11.1.1.1. 区间加均摊
        2. 11.1.1.2. 颜色段均摊
        3. 11.1.1.3. 值域上的均摊技巧
    2. 11.2. 拆分法
    3. 11.3. 分治法与倍增法
    4. 11.4. 调整法
    5. 11.5. MEX
    6. 11.6. 序列大小关系的处理方法
    7. 11.7. 数学式子转数组
最新文章
路线反思
路线反思2025-09-28
猫树分治
猫树分治2025-09-21
MatrixTree矩阵树定理
MatrixTree矩阵树定理2025-09-17
abc423题解
abc423题解2025-09-15
整体DP—从勤拿少取到量大管饱
整体DP—从勤拿少取到量大管饱2025-09-12
© 2025 By wjyppm框架 Hexo 7.3.0|主题 Butterfly 5.4.3
搜索
数据加载中