[心之碎片] - NOIP复习

柿子饼同学

NOIP就要来了, 祝大家好运

注意点
先仔细读题, 然后手算一下样例
有了超时做法先写上去
模块化代码, 写完一个模块就检验正确性
部分分启发正解
连通, 重边, 自环, 重复, 数据范围...
特殊数据 1, 0, ... (9199)
打表
不要慌, 你难大家也难
先加/减 后 修改答案 还是什么样子
尽量不要用 ceil, 精度不够, 可用 (x - 1) / y + 1
多测不清空, 亲人两行泪
不开 ll 见祖宗
恰好 = 不大于 + 不小于
考虑一个条件的性质, 想想去掉这个条件会影响什么

杂项
把一个东西分成两个阵营, 可以按照二进制位分 logn 次 (5304)
有不等式, 等式一定要写下来, 放在一起考虑, 防止漏 (2471) (1972)
有很多地方都满足条件, 我们只需要找最 左/右/小... 的那个 (6617)(1972)
很多问题都可以转化为区间问题, 区间问题可以想想用前缀和等等转化为单点
询问差分 (4211)
先把一个变量定下来, 然后别的看看怎么维护
从一维考虑
变换枚举的对象 (6824)
做一件事, 需要安排一个顺序
先思考不对的情况
反悔贪心, 就是先定下来, 然后用新的看看能否代替, 有些东西是需要定下来的 (3045 中, 我们默认必须买当前的牛)
奇偶性, 说明可以分成两类直接算 (7114)
有了全局的增量 d, 但是会来新的东西怎么办: 插入这个新数 - d (8767)
差分实现 01 序列反转 (2882)
小的尽量在前面 != 字典序最小, 而是相当于字典序最大的反序 (3243)
求状态的后继(前 k 大), 状态的源头 (2048) (1852)
排序去除重复
时间倒流
放宽问题限制, 容斥
一个东西想想可不可以直接枚举, 因为很小 (9118)
两个值拼起来就是答案 (7913)
一般化处理: 把常数也看成一个变量

二分和倍增
长的, 不变的, 想优化一次跳一下的东西想到倍增
二分转化为 01 序列 (2824)
平均数 (区间和 - mid > 0)
中位数 (中位数可以变成大于等于的是 1, 小于的是 -1, 做 sum)

哈希
哈希 : 构造一个充分不必要条件, 然后利用哈希把她变得大概率充要 (8819)
哈希 + 二分判断是否是循环串 (4302)

图论

模板:
Dijkstra暴力(n^2), 堆优化
SPFA 双端队列优化, dfs判断负环
Kruskal算法, 重构树(在对最大/小边权有要求...等等场合)
Tarjan 求强连通分量, 点双, 边双, 缩点, 圆方树
二分图判定
拓扑排序
欧拉回路
Floyd 枚举转移点, 传递信息...
差分约束系统 (2824) (3084)

常用技巧:
建立超级源点
建立正/反图, 枚举一条边, 两个端点各自找最短距离 (2829) (5304)
DAG应该想到的 : DP, 拓扑排序, 按照拓扑序来枚举, 划分阵营 (3573) (5304), 最短路图
严格次小生成树要注意存第二大的边 (4180)
枚举边, 看边的贡献, 两边不知道就转化为两个有向图分别看 (5304)!!!
二分图, 看看两个人之间能不能共存, 不能共存就连边
MST问题两种思考: 按照边权分类 / 建一个 MST 然后用边去代替
MST 限制问题, 先求出必须加的边, 然后再做一次, 把必须加的加上, 然后加别的 (3623)
注意自环 (5008)


树上问题

模板:
倍增, 树剖, 树上dsu

常用技巧:
dfs栈保存了根到 u 路径上的点
dfs做差可以得出子树的答案 (1600)
换根
两个不重叠路径: 一个在子树内, 一个在子树外, 枚举 u 即可
dep, dist 的关系
路径分类: 按照 lca 分上下路径
dfn
lca 的单调性, 可以预处理等等

数据结构
模板:
线段树, 动态开点, 线段树合并
树状数组
栈, 队列, 单调栈, 单调队列
set 的使用
分块

技巧
值对应下标, 下标查询值 (1972)
询问差分
离线

DP
想让转移次数最少, 可以给每次转移加一个高昂的手续费 (6647)
区间类型 dp 可以按照区间拓展的方向考虑, 想想在旁边增加一个东西的代价, 让一个东西插入的代价
也可以想想中间点, 分成两个区间和一个点 (3592)
注意求方案数不要重复
按照顺序完成问题 (2051)
连续段 dp (2467)
状压dp状态的分类可以大幅降低复杂度 (3349)
树形dp 的模板 (4516)

字符串
哈希是强力的工具
二分 + 哈希 判断循环串
回文串, kmp的next数组的相同性
next数组是一棵树

FishC

你好，看起来这是一份很详细的NOIP复习备忘录，包含了竞赛中常见的算法、数据结构和解题技巧。以下是一些重点提醒：

[ul]
[li]题目理解： 认真阅读题目，确保理解清楚。手算样例，以验证思路正确。[/li]
[li]代码风格： 代码模块化，验证每个模块的正确性。有超时做法先实现以防得不到正确做法。注意特例和边界情况。[/li]
[li]算法优化： 使用合适的数据结构和算法，注意时间复杂度。哈希、二分、图论等方法需灵活运用。[/li]
[li]树与图： 了解Dijkstra、Kruskal、Tarjan等算法及其应用。关注连通性、边权限制、DAG上的操作等。[/li]
[li]动态规划： 理解状态转移，避免重复计算。注意在区间DP中，按区间拓展或划分考虑问题。[/li]
[li]特殊技巧： 多测例需注意变量初始化。处理精度问题时避免使用浮点运算。[/li]
[li]冷静应对： 保持冷静，逐步分析问题。如果你难，别人也难，审题和不慌是关键。[/li]
[/ul]

如果有任何具体问题，可以随时问我~ 祝你NOIP取得好成绩！

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

柿子饼同学

@zhangjinxuan

FishC

柿子饼同学 发表于 2024-11-28 19:36
@zhangjinxuan

你好！请问有什么我可以帮助你的地方吗？如果你有关于NOIP或者编程的问题，请随时提问！

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

咔咔咔米

看不懂QAQ

6bingame

虽然不太懂但是感谢分享

很cool的阳

zhangjinxuan

位运算记得 ll，用 "\n" 不是 endl，一定用 -fsanitize=undefined,address 查 ub，一定要用 command time -f "%e, %M" 看运行时间和内存，memset 注意 memset 的操作对象大小。

技巧？这是真的没有（硬要说有的话我可以说 O(向量乘矩阵) < O(矩阵乘矩阵)），但是建议看一看李博杰的骗分导论。

骗分导论.pdf (2.8 MB, 下载次数: 0)

2024-11-29 10:15 上传

点击文件名下载附件

trinityee

wuming12345678

虽然不太懂但是感谢分享

尹玄睿

baimups

感谢分享，学习学习。

菜菜大大^_^

柿子饼同学

zhangjinxuan 发表于 2024-11-29 10:16
位运算记得 ll，用 "\n" 不是 endl，一定用 -fsanitize=undefined,address 查 ub，一定要用 command time - ...

zhangjinxuan

柿子饼同学 发表于 2024-11-30 15:35

你怎么知道我T2写线段树优化DP+矩阵还没写出来

柿子饼同学

zhangjinxuan 发表于 2024-11-30 17:49
你怎么知道我T2写线段树优化DP+矩阵还没写出来

第二题写了50分跑了, 计数题不会

wuming12345678

感谢分享

XiaoMengXin-1

666

liujun_fishc

kerln888