易错&重点&知识点 总结

makerY · 2023-07-23 16:37:48 · 个人记录

难度1-6（7）递增

1. 简单，但有一些小易错点，需要多加注意。

2. 比较简单，但有一些不容易考虑到的情况/原题数据以外的Hack

3. 比较基础但没有掌握的知识点&重点，以及题中少量不容易想到的易错点。

4. 有一定难度和比较生疏的新知识点，或代码不易调对的基础坑题，以及一些基础算法的巧妙建模和应用。

5. 难度较大的知识点，或之前知识点知识的巧妙建模/思维应用

6. 难度很大的新知识点，涉及到一些高级的其他知识，目前用处较小，但有学习的必要。

题目

• 重点 【图论】

P4568 [JLOI2011] 飞行路线

难度：提高+/省选-

个人难度：4

分层图，根据题意，本题下层到上层只能连单向边，注意数据范围，尤其注意层数K，边和点都要多K倍，小细节：堆优化dijkstra要放pair进去，不要放成编号了。

注意思考这题为何能想到转化成分层图。

思路及AC代码

• 易错|转化 【图论】

P1629 邮递员送信

难度：普及/提高-

个人难度：3

建反图，该思想需重点掌握。出错注意：原图跑完之后必须先把最短路累加起来再跑反图，因为共用了dis数组，跑反图会把之前跑出的dis覆盖掉变成INF，导致出错（这里调了不少时间才发现）。

思路及AC代码

• 重点|基础 【图论】

P3385 【模板】负环

难度：普及/提高-

个人难度：3

SPFA判负环，该算法需重点掌握。注意:一定是记录最多的入队次数而不是松弛操作的次数。注意理解为什么入队超过nci就一定有负环及SPFA原理。

此题我还没有完全理解，需找状态好的时间复习！

题解及AC代码

• 重点|基础 【图论】

P5960 【模板】差分约束算法

难度：普及+/提高

个人难度：4

差分约束，该算法需重点掌握。注意理解不等式如何转化成图，为什么要建超级原点，为什么跑最短路得出的是最大可行解（我对此的提问），跑最长路得出的是最小可行解，以及该题变式（不等式组的符号改成大于等于、等于等）的同样思路转化。

题解及AC代码

• 重点|基础 【基础思想与技巧】

P3406 海底高铁

难度：普及/提高-

个人难度：2

大体思路：差分预处理+前缀和，注意理解这种转化的技巧。

易错点1：容易错误地理解题意，办卡是针对一条线段，而且办卡后只要经过这条路就优惠

易错点2：差分数组的处理方式，因为本代码是把每条线段的下标对应到了其前端节点，而前缀和是对于线段求的，差分是对于点求的，注意偏移

易错点3：注意数据范围，要开long long

思路及AC代码

• 重点|易错【图论】

[USACO06NOV] Roadblocks G

难度：提高+/省选-

个人难度：4

易错点：更新是分类状态更新的讨论，之前没有考虑到原路返回再过去也能更新次短路的情况(1->2->1->2是1->2的次短路），喜提90pts，原因是只考虑了最短路径去更新的讨论，没有考虑最短路径没法更新的时候次短路径也可以更新（即v点的最短路已经确定，但是次短路没有确定，无法在更新最短路的同时更新最短路），需结合代码详细理解。

题解及AC代码

该方法的应用：P2829 大逃离

难度：省选/NOI-

个人难度：4 几乎是板子，但有很多易错点：

如：有自环和重边，自环不能建边，重边必须要建边而不能再次累加点的度数

需整理复盘

AC记录

• 重点|基础 【图论】

  P2910 [USACO08OPEN] Clear And Present Danger S

难度：普及/提高-

个人难度：3

Floyd-Warshall 求多源最短路，该算法需重点掌握。注意理解透彻dp状态转移过程的推导（尤其是从子图逐步扩大到全图的过程），可以把扩大子图的k这一维空间优化掉的原因，及k的遍历必须在最外层循环的原因。

题解及AC代码

基于Floyd的扩展：B3611 【模板】传递闭包 | 解答

难度：普及/提高-

个人难度：3

重要|Floyd的灵活运用：P1119 灾后重建 | 解答

难度：普及+/提高

个人难度：4

• 注意理解Floyd更新的本质是每次扩展一个新点，用这个新点作为中转点去更新其他所有点的最短路。
• 本题的重建时间具有单调性，可一步一步扩展每个重建好的点。

• 思维|提高 【计算几何】

P4468 [SCOI2007] 折纸

难度：NOI/NOI+/CTSC

个人难度：5

计算几何基本模板的应用，实际上不是很难，重点在考虑用dfs反推前一次翻折的状态，和在右边不考虑的原因，需加深理解和复盘，细节很多，易错点需要多加注意。

注意&易错

1. 写模板重载运算符的时候一定注意必须有返回值类型，如果不加似乎本地不会报错，但洛谷的测评机会CE

2. 有返回值的dfs必须每种情况都要考虑并有返回，开始没有在不符合所有情况时返回0，导致样例过不了（60pts）

3. 重载之后的运算每层最好都加括号！！！！ 不然会把挨着的没重载的小于号等判成没被重载的运算符（导致dfs判叉积的if里一直报错）

4. 为避免一些奇怪的错误，运算符重载的函数参数都加const且传要引用（我也不知道为什么qwq）

题解及AC代码

• 重点|基础 【基础动态规划】

P2196 [NOIP1996 提高组] 挖地雷

难度：普及/提高-

个人难度：3

基础动态规划应用，重点是从转移好的状态反推转移过来的路径，需要熟练掌握，同时做题时要注意状态转移的方向是否合理（如这题按照dp状态的定义必须从最后一个地窖一个一个向前转移）。

思路及AC代码

• 重点|基础【图论】

P3366 【模板】最小生成树

难度：普及-

个人难度：3

Prim

思想：贪心加点。

重点：类似Dijkstra的思想的应用（每次确定最小生成树上的一个点），dis数组的含义（每个点到相邻其他点的最短距离），用类似最短路的松弛操作（但不同）更新每个点的dis。

题解及AC代码

Kruscal

思想：贪心加边。

码量较小，适用于稀疏图。

题解及AC代码

应用

P1194 买礼物|题解及AC代码

P1396 营救|题解及AC代码

（好题）P1195 口袋的天空|AC记录

• 思维|应用【数据结构】【基础算法】

P9474 [yLOI2022] 长安幻世绘

难度：普及+/提高

个人难度：5

重点：枚举思维的建立，如何想到双指针？如何想到线段树？需要整理复盘。

易错：线段树合并前后区间的方法，取等的条件。

详细题解及AC代码（已成功提交到原题公开题解）

• 基础【DP】

P1434 [SHOI2002] 滑雪

难度：普及/提高-

个人难度：2

比较简单的DP，实际上记忆化搜索更好写也不会慢，重点注意从小到大排序高度来DP，以保证每个点的最长路一定能从所有比自己低的点更新（保证所有比自己低的点都被更新到最优）。

写代码的时候出现了一个非常傻的错误，二维数组一维化的操作应该每多一行就多一个宽度 n，而不是 m。

AC记录

• 基础【DP】

P1802 5 倍经验日

难度：普及-

个人难度：2

注意开long long，01背包类型的枚举其实枚举背包大小和每个物体的顺序没有先后要求。

易错：这题必须从容量0开始枚举，表示全部不用药得到的经验。

题解及AC代码

• 基础|易错【DP】

P1064 [NOIP2006 提高组] 金明的预算方案

难度：普及+/提高

个人难度：3

思路不难，看着像分组背包或依赖背包，其实就是有多种情况的01背包，分好每个类即可。

易错：这题调了很久，结果犯了个很傻的错误，因为我没有额外存主件，所以每次枚举一定要记录上一个主件的编号，只能用上一个主件更新，不能直接用 i-1 更新当前最小答案，因为上一个可能不是主件，其 dp 值没有意义，最后输出答案同样，应该输出最后一个主件的 dp 值而不是第 m 个物品的 dp 值。

题解及AC代码

• 基础|重点|易错【图论】

P8436 【模板】边双连通分量

难度：普及+/提高

个人难度：4

注意理解边双连通分量的定义和性质， tarjan 求边双的方法及每一步的含义，理解low的含义以及保证正确的更新方法，尤其注意“ X ”型图的特殊情况。

易错：本题有重边和自环，不能去重边，dfs过程中不能根据前驱节点判断能不能回去，要通过前驱边。

需要理解的细节很多，见博客。

边双连通分量详解及AC代码

• 基础|重点【图论】

P1111 修复公路

难度：普及-

个人难度：2

注意题意的转化，每次修复道路即合并道路两端点所在的连通块，如果可合并（不在同一连通块内）就合并、把现有连通块数量减1，用并查集实现。

注意！！！！ 把某个两个点合并一定是用连通块祖宗去合并而不是建立两个节点的父子关系（不能写成"f[e[i].v]=e[i].u;"，这样达不到合并连通块所有节点的效果）

注意带返回值的函数如果在某些情况下没有返回，开了O2就会爆零，这里是全MLE。

思路及AC代码

• 基础|重点【图论】

{\color{#FFC116}{P3958 [ NOIP2017 提高组 ] 奶酪}}

难度：{\color{#FFC116}{普及/提高-}}

个人难度：3

• 做此题全过程这题未借助题解

注意题意的转化，这题较简单但注意细节。

注意！！！！ 两点并查集的合并一定是合并祖宗，不能写成f[find(i)]=n+1，因为n+1的祖宗可能被改，这样会导致路径变得非常长而MLE。

思路及AC代码

• 基础|重点【图论】

{\color{#52C41A}{P4588 [TJOI2018] 数学计算}}

难度：{\color{#52C41A}{普及+/提高}}

个人难度：3

• 做此题全过程这题未借助题解

注意题意的转化，这题较简单但注意细节。

注意

1. 每次需要初始化线段数为1，不可使用memset置1。

2. 能开long long尽量开，不知道为什么只开int还是会爆掉。

3. 对于同一个线段树，开始确定了区间的范围(即 n )就不能再更改了！！否则会破坏整棵树的结构，这里每次都取得最大可能范围q。

思路及AC代码

• 基础|重点【DP】

{\color{#52C41A}{P1725 琪露诺}}

难度：{\color{#52C41A}{普及+/提高}}

个人难度：4

可以称为单调队列优化DP的模板，此前我没有掌握，需要多加练习巩固。

注意思考什么样的状态转移能用单调队列优化，复习单调队列滑动窗口的具体流程和原因。

注意

一定要赋初值为极小，因为数字可以是负的，初值有问题会被Hack。

Tips

单调队列滑动窗口时，队头在右，队尾在左，队头比队尾更老，所以出队要从队头，而从队尾新加元素，为了查询最大值，让队列单调递减，队头即为最大值。

为什么要这么维护？便于先进队的元素先出队，消除对最值的影响，又由于窗口是从左到右滑动的，所以队尾入队更方便理解，队列中元素的相对位置和原序列中是一样的。

思路及AC代码