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

OI大技巧

发表于2025-07-14|更新于2025-08-18|笔记
|总字数:9|阅读时长:1分钟|浏览量:
OI大技巧
https://worldcpu.github.io/posts/a3f4a75/
作者
wjyppm
发布于
2025-07-14
更新于
2025-08-18
许可协议
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
高中蒟蒻信竟生
文章
70
标签
20
分类
13
Follow Me
公告
👋🏻我是PPM，一个热爱编程和信息学竞赛的高中生，喜欢分享做题经验。本博客中所有 latex 公式均可以选中后复制哦😊

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

嗷嗷！热烈欢迎🤪！来自

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

目录
  1. 1. 1. 数据结构+离线算法专题
    1. 1.1. 根号滚动数组，空间与时间平衡
    2. 1.2. 高精度，但是是 x 次
    3. 1.3. 可离线的区间修改问题——CDQ分治注意事项
    4. 1.4. 区间范围也是二维偏序
    5. 1.5. 倍增二分思想
    6. 1.6. 对询问建立扫描线
    7. 1.7. 颜色段问题
    8. 1.8. 区间右端点扫描线
    9. 1.9. 子区间计数问题
    10. 1.10. 换维扫描线
    11. 1.11. 单调栈维护最值更新(离线)
    12. 1.12. 重链刨分平衡复杂度（链分治）
      1. 1.12.1. 轻子树与重子树分治
      2. 1.12.2. 树上维护相邻点信息
    13. 1.13. 维护链的数据结构与均摊复杂度
    14. 1.14. 每个区间的区间最小值之和
    15. 1.15. 对询问进行差分（离线）
    16. 1.16. 二进制分组（强制在线）
    17. 1.17. 一个序列整体加一个数后与另一个序列相同
    18. 1.18. 值域分块
    19. 1.19. 凑 k 的多次询问
  2. 2. 2. 图论专题
    1. 2.1. 最短路树
    2. 2.2. 子树维护求和
    3. 2.3. 缩点
    4. 2.4. 中序遍历
    5. 2.5. 点边互换
    6. 2.6. 要么取…要么不取…
    7. 2.7. 树上路径转树上差分
    8. 2.8. 区间LCA或LCA限制（虚树）
    9. 2.9. 边权转点权，点权转边权
      1. 2.9.1. 链操作的本质（边 -> 点）
    10. 2.10. 环问题
    11. 2.11. 森林图数联通快
    12. 2.12. 求带权重心
    13. 2.13. 树上维护相邻点信息
    14. 2.14. 01BFS
  3. 3. 3.贪心
    1. 3.1. 操作类求最小化操作次数
    2. 3.2. 以模型思考贪心
    3. 3.3. 用堆维护前 k 大/小
  4. 4. 4.一般DP
    1. 4.1. 一般 DP 过程
      1. 4.1.1. 转化问题
        1. 4.1.1.1. 方格图上的路径问题
        2. 4.1.1.2. 匹配问题的 DP
        3. 4.1.1.3. 覆盖所有点的状态设计
        4. 4.1.1.4. 多边形转笛卡尔树建树
        5. 4.1.1.5. 高维问题转不相关低维问题（分离限制思想）
        6. 4.1.1.6. 操作或限制具有某些特殊性结构
        7. 4.1.1.7. 存在性问题转限制性问题
      2. 4.1.2. 发掘性质
        1. 4.1.2.1. 发掘性质的时机？
        2. 4.1.2.2. 多过程多步骤的思考角度
        3. 4.1.2.3. DP和贪心的结合
        4. 4.1.2.4. 限制过松？强化限制
        5. 4.1.2.5. 模数及其奇怪
        6. 4.1.2.6. 排列连边转化（排序）
        7. 4.1.2.7. 答案对 2 取模
        8. 4.1.2.8. 当限制主体量过大，考虑归纳或递归方法描述限制
        9. 4.1.2.9. 答案的 k 次方但 k 不大
        10. 4.1.2.10. 将期望拆开来算
        11. 4.1.2.11. 排列与出现次数
        12. 4.1.2.12. 树形 DP 转 DFN 序
      3. 4.1.3. 选定 dp 主体
        1. 4.1.3.1. 多个最值的笛卡尔树的 DP 问题
        2. 4.1.3.2. 去除无需计算的状态，重设 DP 主体
        3. 4.1.3.3. 区间最大值，枚举最大最小值转移
        4. 4.1.3.4. DP+自动机
        5. 4.1.3.5. 连续段DP
        6. 4.1.3.6. 排列上扫描线（插入法）
      4. 4.1.4. 设计 dp 状态
        1. 4.1.4.1. 保留与代价计算有关的量
        2. 4.1.4.2. 动态的状态设计
        3. 4.1.4.3. 全局变量或操作放入局部状态内
        4. 4.1.4.4. 状态和答案对换
        5. 4.1.4.5. 操作序列会使得答案算重
        6. 4.1.4.6. 确定顺序类型的题目
        7. 4.1.4.7. 枚举法确定决策以及其运用
        8. 4.1.4.8. 设计相反的状态（正难则反）
      5. 4.1.5. 确定转移顺序
        1. 4.1.5.1. 一些类型
        2. 4.1.5.2. 答案是 0/1 交错组成的答案
      6. 4.1.6. 寻找子问题
      7. 4.1.7. 考虑如何转移
        1. 4.1.7.1. 转移过程过大
        2. 4.1.7.2. 将最大值不等式限制融入方程或转笛卡尔树转移
        3. 4.1.7.3. 树形DP但儿子向父亲不好转移
        4. 4.1.7.4. 微元贡献法
        5. 4.1.7.5. 转移上的优化（分割点证明）
        6. 4.1.7.6. 如果贡献很难算(具有决策单调性)
        7. 4.1.7.7. 矩阵DP二分转移优化
    2. 4.2. DP 优化
      1. 4.2.1. 斜率优化
      2. 4.2.2. 费用计算优化
      3. 4.2.3. 解决巨大数据范围
        1. 4.2.3.1. 矩阵二进制分组快速幂
  5. 5. 6. 字符串
    1. 5.1. 本质不同的回文串不超过 n 个
    2. 5.2. 重复类型问题分块思想（关键点思想）
    3. 5.3. 循环同构匹配
    4. 5.4. 字符串匹配代数化
  6. 6. 7.数学
    1. 6.1. 完全平方数的性质
    2. 6.2. 质因子太多啦怎么办？
    3. 6.3. 期望？诈骗！
    4. 6.4. 差卷积
  7. 7. 8. 网络流
    1. 7.1. 将最大流转最小割，用最小割性质玩
    2. 7.2. 在图上删点
    3. 7.3. 平面图问题用染色分析性质
  8. 8. 9. 构造
    1. 8.1. 棋盘染色方法
    2. 8.2. 限制很松，考虑强化限制
    3. 8.3. 通过限制次数下的交换还原排列
    4. 8.4. 递归方法构造（子问题合并，归约与增量）
    5. 8.5. 对于树的构造方法
    6. 8.6. 树上所有点被覆盖的选取路径条数（下界）
    7. 8.7. 无向图上构造树上内容
  9. 9. 10.位运算
    1. 9.1. 位运算每一位独立
    2. 9.2. 异或为 0
  10. 10. 11.杂项或思维技巧
    1. 10.1. 尽可能的简化问题
    2. 10.2. 放宽题目限制转容斥
    3. 10.3. 判断一个集合和另一个集合是否相等（或出现次数）
    4. 10.4. 回溯法
    5. 10.5. 相交区间解决
    6. 10.6. 数学式子转数组
    7. 10.7. 棘手的题目限制！
    8. 10.8. 正难则反，时间倒流
最新文章
2025.8.16模拟赛
2025.8.16模拟赛2025-08-16
20250814模拟赛
20250814模拟赛2025-08-14
广义圆方树
广义圆方树2025-08-13
分治fft
分治fft2025-08-12
组合数学乱学
组合数学乱学2025-08-12
© 2025 By wjyppm框架 Hexo 7.3.0|主题 Butterfly 5.4.3
搜索
数据加载中