Logo

菜单

fogflea
fogflea
发布于 2026-01-24 / 3 阅读
0
0

NOIP前若干trick，思考方式及注意事项大复习

#NOIP

cover: Pixiv ID 138508251

update on 2025.12.30：补完，本来是想在 noip2025 前做一个大复习的，因为时间原因没干完。现在退役后时间多了就把这补完了。（发现自己惊人地退化了

update on 2025.1.5：重构，将一些比较细的东西放到了其他文章，以这篇文章为根树形链接到其他文章。

以下为正文

与君共勉

距离 NOIP 还有一天，再做什么题也积累不了什么了，不如把自己刷过的题再看一遍，好好复习一下过去一年自己累积的知识和打的模拟赛，不要让学过的在考场发挥不出效用。

下面让我们开始复习吧！

做一道题的流程（我的

1 读题 < 5 min

注意点：

  • 形式化题意
  • 数据范围
  • 时空限制

要求：认真快速，以不读错题为最优先！

2 确定题目基本属性 < 1 min

  • 写出可能的时间复杂度，多考虑一些不寻常的时间复杂度，比如利用 bitset 的 O(\frac{}{w}) ，以及根号分治，分块带来的 O(\sqrt\ ) 做法 （本人常常忘记。
  • 确定题目类型 tag ，可以自由组合，常见：构造题，ds 题，计数题，最优化题，判断题，其他计算题。
  • 明确有哪些限制，哪些性质，所要求的对象。（可以写下来

\frac{5}{2} 人类智慧时间 < 3 min（构造题独享？

反正我只在构造题给这个时间。

注意保存假算法，说不定能水分呢。

3 正式考虑做法 < 15 min

3.1 确定大致算法

首先根据 2 的 tag 写出大范围算法及初步操作。

下面给出一些可能的初步操作：

3.1.1 一些可能的初步操作

  • 通用：
    • 弱化问题
      • 优化暴力
      • 特殊性质推广
    • 标准化，例如：用值-下标，从初态走到目标和从目标走到初态的互化。
    • 正难则反
    • 考虑信息的性质，形态
    • 删除和增加的互化
    • 子问题复用
    • 切换主体
    • 考虑一些数学结构或模型比如笛卡尔树
  • 构造题：
    • 从数据中找规律
    • 差分，前缀和
    • 交错，奇偶
    • 裂项，抵消
  • ds 题：
    • 离线，更进一步的：时光倒流，莫队，CDQ
    • 预处理
    • 先考虑不带修
  • 计数题：
    • 考虑 O(ans) 的可行性
    • 容斥，全=合法+不合法
    • 切换计数主体（算权重
    • dp
    • 分治
    • 打表
  • 最优化题：
    • 二分
    • 贪心
    • dp
    • 容斥，全=最优+最劣
  • 判断题
    • 不可以，总司令
    • 通常转化为其他题
  • 其他计算：这里是一些更具体的 trick 和手法，见下文

3.2 分析

从 3.1 的列举的各种做法中依次考虑当前最有可能的做法，失败后记录断点，然后换下一个。

3.2.1三种常用的手段。

  • 分析数据：看样例，造数据打表，可用于猜/验证性质
  • 推导：证明，推式子，其实就是直接想
  • 套模型：勾连一些基础算法，可以理解为建模，比如：
    • 沃柑，这个有后效性的 dp 式子怎么这么像三角不等式，治療計画

注意力强可以注意到某些性质，那注意力不强怎么办？

对于一些对象我们可以主动研究它的一些容易被忽略的属性和子结构！下面列举一些：

3.2.2 一些容易被忽略的属性和子结构

  • 通用：
    • 数量，（这个东西会不会很少？可以枚举这个搞吗？
  • 区间（矩阵类似）：
    • 交区间和包含区间
  • 序列：
    • 差分序列，前缀和序列
    • 顺序无关时可考虑 cnt 数组，即元素出现次数序列
  • 点（图论）：
    • 各种度数
    • lca
    • dfn
    • 轻重儿子
  • 边：
    • 定向（无向边
  • 路径：
    • lca（树上
    • 端点
    • 前后缀
  • 树：
    • dfn 序列
  • 无向（子）图：
    • 各种奇技淫树：
      • e-bcc 缩点后的树
      • 圆方树
      • Kruskal 重构树
      • 最短路树
      • dfs 树
    • 两种连通分量：
      • e-bcc
      • v-bcc
  • 有向（子）图：
    • dfs 树
    • 强连通分量缩点 DAG 图
    • 基环树（如果有点的度数性质

推导分析不知道从哪里下手的话，不妨试试这些基础的研究方法：

3.2.3 一些基础的研究方法

  • 序列：
    • 一般：
      • 将 (i,a_i) 作为坐标点画到平面上
      • 将 [l,r] 视为一个坐标点 (l,r) 画到平面上
      • 直方图，可以是原序列或 cnt 数组
      • 笛卡尔树
    • 01 序列：
      • 原序列
      • 括号树（可三度化，用于研究序列结构及变化
      • 折线图（便于考虑 1,0 数量最大最小以及变化
    • 排列：
      • 逆序对
      • 康托展开
  • 图：参考 3.2.2
  • 树：
    • dfn 序列也可以使用序列的研究方法！

3.3 停机

到这里有两种可能：

1.我做出来了！

可以先明确整个算法流程和细节，看看假没假，假了看情况要不要回 3.2，没假就评估一下实现难度，时长啥的，具体情况具体分析。

2.思路枚举完了，没做出来。

开部分分或者换题。不要摆烂或灰心，你一定行。

更加具体的 trick

一般

构造

计数

最优化

DP

  • [HAOI2015] 树上染色 不一定要 dp 子问题的解，也可以直接 dp 对全局答案的贡献，适用于子问题受到其他非包含子问题影响，且影响可拆分的情况
  • U588953 计树 森林 dp ,本质是提取树上连通块的特征进行的 dp
  • P5999 [CEOI 2016] kangaroo 排列插入段 DP 板子，本质是在 dp 一个排列的前缀时记录当前排列值域上的某些信息（可以是连续段个数，空位个数或其他...
  • CF1476F Lanterns 可达性 dp 用 bitset 优化，或利用贪心等某些性质将 bool 数组转为 int 数组
  • 先暴力 dp ，然后一步一步通过分讨/发现冗余信息（可以通过联系所求或性质）减少所记状态数

贪心

图论

数据结构

数论

字符串

祖宗大全

谨防见祖宗！！！

进食后人：中元节见祖宗的最好方法是

【挂分指南】日常做题错点解析

挂分导论

记录最近的两道印象稍深的题
dp 专题总结

评论