算法参考
# 算法参考Notebook
本页面是广义的算法，将ICPC会考到的统统包括进来。
消除编译生成的可执行文件：
rm *.exe
# 〇、前言
自从旧年十月份，受校ACM协会选拔后，登记在册以来，……总赖环境不足，最终又成摆子。疏于训练。（所有真正的训练都是自我训练。这里的自我，当然是符号系统装载完全的。也就是律令化好的、平等化好的、性化好的——符号学内容见自由学习的要素。）
三月份，我几乎完成了我的第一个项目——个人网站（尽管现在看来，那丁点努力，微不足道），可作知识库查询所需知识，也可作博客发发牢骚。于是乎，一个日常工作学习流就建立起来。（我始终认为，学会有两个衡量标准，或者说必要条件……也就是说，笔记是必要的，就当作讲义来写。）
（一谈及学习，我就不能不回想起我在乒乓球上从不会搓到高中校运亚军的成长历程。学习的实质，就是字面上的学着去习惯而已。而这个地方就是实践。而我所接受的“学校教育”几乎都完全与实践脱节。）
2025年4月2日，16:43:16。
XCPC不是考验灵光一闪的比赛，而是代码能力，多写就好。如果你当摆子，过多少年还是小白。多写，多写就完了。
# 一、技巧
# 0、字符串操作
# C系：<string.h><cstring>
<string.h>cppreference文档 (opens new window)
注意存字符的字符数组，与存字符串的字符数组的区别，
字符串的末尾总有一个隐式的\0，就是它使printf输出%s时能够输出字符串，
同时，这也是存字符串的字符数组，与其它所有数组都不一样的地方，即数组名可以指向整个字符串。
而像整型数组，使用%d输出它的数组名，永远只会输出第一个元素而不会是所有元素。
同样使用%p也只会输出第一个元素的地址。
# C++系：<string>
cppreference文档 (opens new window)
stringstream可以将数值转换成字符串。就从这里引入流的概念。 istringstream可以将字符串转换成数值，用来处理数组的不定项输入。
# 1、流的概念
C++中，输入/输出的实现依托着一种“流”的观念。
# 2、ios::sync_with_stdio(false);
# 3、位运算。Bitwise operation
位运算直接按二进制编码运算，有点密码学的意思。 因为是计算机十分底层的运算，所以速度较快，可用来优化。 位运算符：按位与&、按位或|、按位异或^（又称不进位加）；左移<<、右移>>。 ——详见 https://oi-wiki.org/math/bit/
异或^例题： https://www.luogu.com.cn/problem/P1469 左移<<、右移>>例题： https://www.luogu.com.cn/problem/P1100
位运算的奇技淫巧妙用：（1/26补）【以下n是int型变量】
n除以2，等价于n>>1
n乘2，等价于n<<1
判断n的奇偶性：
n&1==0则n为偶数
n&1==1则n为奇数
——参考 https://zhuanlan.zhihu.com/p/54946559 或者谷歌以搜索更多。
# 数论
素性测试。
# 高精度
# 双指针
https://leetcode.cn/problems/count-the-number-of-good-subarrays/solutions/3643775/tong-ji-hao-zi-shu-zu-de-shu-mu-by-leetc-uvcm/?envType=daily-question&envId=2025-04-16
# 特殊：快慢指针
# 动态规划
Dynamic_Programming.cpp
# 二、数据结构
我涉足数据结构蛮久了，结论是这个名字严重名不副实。其实就是对对象建模。
引入对象的概念，比一坨冷冰冰的数据的结构更符合思维规律。
所以面向对象的C++的std库才会安排许多容器，避免造轮；但可惜的是，大多数数据结构课都是用C上吧。
只有两种数据结构——数组和链表，其它都是变种。这是由内存的物理结构所决定的：
物理结构反映了数据在计算机内存中的存储方式，可分为连续空间存储（数组）和分散空间存储（链表）。
# 1、数组
# (1)栈
# (2)队列
# (3)哈希表
哈希映射。哈希映射（Hash Map）可以用std::unordered_map直接实现。
https://leetcode.cn/problems/count-largest-group/
std::map 或 std::unordered_map 类型的容器，std::map 的元素是键值对std::pair (opens new window)。它有两个成员对象，first是键，second是值。
# (4)线段树
前缀和是一种预处理，使数组某部分和的时间复杂度达到O1。但是在修改时就失效了。
于是就引入线段树这种预处理。可以用二维数组实现。sum[i][j]表示i到j的和，访问时间仍为O1。 如果要修改某一元素[k]，那么每个i≤k≤j的sum[i][j]随之改变。
如果要对数据结构进行操作，就必须要分治。倍增和分治都是二分的思想。
这里功能和复杂度跟树状数组一样。但后者需要自己手搓，而这个套用模板即可。
凡计算复杂度都应考虑最坏的。
区间和因为满足结合律，所以可以用线段树。进一步，理论上所有满足结合律的都可以用线段树。
而不符合结合律的，一律不能用线段树存。d[p]=d[p2]#d[p2]+1，#必须存在。
按位和、或、异或都是满足结合律的。
这种递归分治的思想，在很多代码里会用到。
另外还有偶尔用到的，比较偏门的使用动态数组vector存的动态线段树，及其偶尔。用来处理一些特殊情况。
# 2、链表
std::list对于迭代器auto it：
*it为当前元素
*prev(it)为当前元素的前驱
*next(it)为当前元素的后继
# 贪心
https://leetcode.cn/problems/maximum-value-of-an-ordered-triplet-i/?envType=daily-question&envId=2025-04-02
# 数学
https://www.lanqiao.cn/paper/4396/problem/19732/ https://vjudge.net/contest/698712#problem/L
https://www.lanqiao.cn/paper/
# DFS BFS
绝大多数算法源自优化。
# 图论
graph_theory.cpp