前言
这篇文章主要用来记录学习算法竞赛的过程中遇到的那些注意事项,比如一些调试了很久却没有发现,到头来却发现非常弱智的bug。持续更新,部分条目会附上题目或代码提交记录。
灵感来自 Rainybunny 的博客 (其实本来想叫这个名字来着)
乱搞做法
随机化
有些时候,题目中让你维护的信息并不是你真正需要维护的,比如 [CSP-S 2022] 星战 这道题中,虽然在一张图上操作,但只需要维护每个点的入边是否为1,以及整张图上的每条边是否有且仅有一条出边,并且操作也很简单。这时候可以把大部分信息舍弃掉,给每个点附上随机权值,用很小的代价维护这一个信息。
杂项
time(0)
的值每秒更新一次,也就是说如果用它做随机种子,每秒只能产生一个种子。当你使用这个东西作为数据生成器对拍的时候,切记不要拍两秒之后看没啥问题就跑,因为你很可能测试了许多相同的数据。
图论
距离相关
- 可以使用 BFS 计算边权为 $1$ 的图上的最短路径,单源时间复杂度为 $O(n)$ 。还可以用 0-1BFS 计算权值为 $0$ 或 $1$ 的图上的最短路径,复杂度同 BFS。
- 有些时候,计算最短路径并不使用松弛操作(比如上面这种),在连通图上dis数组初值为0不会出错,然而到了非连通图上,两个不连通的点的距离就成为了0,显然会出大问题。所以,记得给dis数组赋初值 $\infin$ 。
网络流
- 割是一种点的划分方式,把一些边割开只是计算最小割的方法。计算时只有 $S\rightarrow T$ 的边会计入割的容量,$T\rightarrow S$ 不会计入。(Luogu P1361 的建模)
数学
- 碰到重复开方计算的问题关注所需精度,一些重复开方运算是有收敛值的,这种情况下数据范围只是用来唬人的。(MssCTF 2021)
- 浮点数判断等于不能直接写
a==b
,要将计算精度导致的误差纳入考量,相差不超过误差即可,一般设为1e-6~1e-8
之间。
数据结构
函数指针传址是
*&
这样表示的,而不是&*
这样(不过第一个编译也过不了不要随便使用 指针传址 ,尤其在写这种东西的时候一定慎重:
void split(Node *&, int, Node *&, Node *&); void split(rt -> rs, val, rt -> rs, spr) // 当参数1和3都是指针传址的时候,这种写法很容易出bug(事实上这个确实是bug)
平衡树
- 区间操作的文艺平衡树,最后输出时要先下传lazytag
- 下传加减之类的tag时,注意不要下传到叶子节点的左右儿子指针,因为叶子节点的左右儿子实际上是公共的空指针,大家都下传会导致越堆越多,最后向上更新区间信息的时候受到影响。push的时候做特判,或者每次push之后清空(P4146 序列终结者)
- 区间加减操作和区间最值都需要实现的时候,最好像线段树一样,同时更新最值,当前节点值和tag,其实这样操作是没什么问题的(P4146 序列终结者)