Releases: hh2048/XCPC
Releases · hh2048/XCPC
赛用模板打印稿 V1.8.7, 2024.10.07
概述
时间飞逝,一眨眼就退役大半年了,值此国庆假期空闲之际重新整理了一下内容。成稿于2024第一场区域赛前夕,祝大家新赛季取得好成绩。
额外内容
Important
2024.10.21更新:
这里有一个重要的更新,由 @doyowhat 提出的 #5 ,由于代码错误较大,即便已经封装我依旧将其列入这一版本的更新。以附件的形式给出。
- 《图论→缩点(Tarjan 算法)→(无向图)割边缩点》代码有误,重构。
2024.10.22更新:
收集的 jiangly 的模板也更新了一波。为了节约空间,删去了部分旧版本的内容、以及去除了代码中的 ::std
。
2024.10.29更新:
收集的 jiangly 模板封面更新。
更新日志
按时间的说明见此。以下是按章节的说明:
重要问题修复
- 《图论→缩点(Tarjan 算法)→(无向图)割点缩点》修改,计数器修改为先加后使用
++now
。感谢 @doyowhat 提出的 #4 、@coolarec 在QQ的沟通。 - 《获取二维静态凸包(Andrew算法)》小于号写错,修正,感谢 @xxxxbc 在微信的沟通。
- 《图论→二分图最大匹配→HopcroftKarp算法(基于最大流)解》重构,此前的版本可能被卡(时间与正确性均)。
- 【1.8.6增量更新】《线段树 区间加法修改、区间最小值查询》
rmq
函数初始值赋值错误,min
应该对应::max()
- 【1.8.6增量更新】《线段树 区间最值》初始赋值错误。懒标记应该赋值为
$-1$ ,而不是$0$ 。
新增内容
- 《基础算法→常用函数》新增两个
log2
函数。 - 《串→子序列自动机》新增。
- 《数据结构→小波矩阵树:高效静态区间第 K 大查询》新增。
- 《杂类》新增一段测速代码。
- 《exgcd》新增对
$0$ 的特判(还不完美,在改)。 - 【1.8.6增量更新】《OJ测试》新增
numbers
库测试。 - 【1.8.6增量更新】图论新增结论——竞赛图三元环计数。
- 【1.8.6增量更新】《bitset》新增
_Find_next
和_Find_fisrt
两个函数
优化
- 《图论→常见概念》强对应代码的概念分散到代码附近。
- 《常用例题→选数(DFS 解)》重构。
- 《数据结构→树状数组→最值查询扩展(常规+区间最值查询+单点赋值)》优化了单点赋值部分的代码,例题。
- 《串→KMP→统计原串中某个子串重复出现的次数(例题)》删除,通过全串匹配可以以相同复杂度实现(仅常数区别),无需这个额外的版本。
- 《串→KMP→全串匹配》重构。
- 《差分约束》代码重构。
赛用模板打印稿 V1.8.5, 2024.06.01
1.8.5 整合
概述
这是第一次系统性的发布打印件整合包,由于整理时间仓促,此次版本仅包含两个文件:
- XCPC Algorithm Template(I) WIDA's Onfine version
- XCPC Algorithm Template(II) Jianly's Online version
成稿于参加江西省赛前夕。
版本更新小计
2024.04.12
《最长路(topsort+DP算法)》重构
2024.02.06
《快读》代码微调
《扩展欧几里得 exgcd》重构
2023.12.20
《网络流》新增”最小割树 Gomory-Hu Tree“
2023.12.19
《STL》新增“其他函数一章,重构《bit 库与位运算函数 _builtin》
2023.11.20
《Python》在增加输出流长度一小节中新增“递归深度”