2024 暑假集训

树状数组&线段树

线段树合并，主席树等知识点是第一次接触。

同时对扫描线能解决的问题有了些更好的认知。

毕竟是之前学过的东西，还是比较好的。

掌握程度：\(85\%^+\)

离线分治算法

具体是：

• 线段树分治 \(80\%^+\)

  就是个线段树上二分。

• CDQ 分治 基于时间的分治 \(75\%^+\)

  基本原理主要是二分，这类问题主要是思维问题，,搞定需要怎么合并与维护。

• 整体二分 \(70\%^+\)

  基于值域的离线分治算法：避免多次二分，仅一次二分完成多组询问，掌握的不算熟练。

也是扫盲课讲过的，还可以吧。

DP

怎么说……

大部分是需要线段树 or 树状数组优化的。

有些转移方程并不是很好想。

掌握程度：\(50\%^+\)

图论

具体是：

• 分层图最短路 \(95\%^+\)

  就是个最短路但是多了几个点 or 边。

• 差分约束 \(90\%^+\)

  利用最短路中的松弛操作与不等式的相似性，通过最短路构造出一组特殊解。

• 最小生成树 \(80\%^+\)

  Kruskal, Prim之 前就会，在此基础上学习了 Brovka 算法。

• 强连通分量 \(80\%^+\)

  主要是 Tarjan 缩点。

• 2-sat \(70\%^+\)

  问题形如有 \(n\) 个 \(0/1\) 变量 \(x1, x2, . . . , xn\)，不同的变量有一些限制，形如 \(xi\) 选 了 \(a\) 或者 \(xj\) 选 \(b\)。求出一种合法方案（或判断无解）

  我们可以对每个变量建立两个点，分别表示 \(0\) 点和 \(1\) 点，那么一对关系可以转化为两条表示选了起点就必须选终点的边。

  是否有解：如果一个点 \(0,1\) 两点必须同时选，显然就是无解的。可以发现这个条件两点位于同一强连通分量中。

  求方案：每次找到 SCC 编号小的选择即可。

• 二分图 \(50\%^+\)

  • 匹配：图的一个匹配是一个边集，满足一个点最多作为一条边的端点出现。
  • 点覆盖：图的点覆盖是一个点集，满足每条边至少一个端点处于点集中。
  • 边覆盖：图的点覆盖是一个边集，满足每个点至少一个连边处于边集中。
  • 独立集：图的独立集是一个点集，满足所有点对之间没有一条边直接相连。

• 点/边双连通分量 \(80\%^+\)

  差分求解。

• 割边与割点 \(80\%^+\)

  还是差分求解。

• 圆方树 \(50\%^+\)

  • 以点双为基础建立的树。对图中的每个点双建一个方点，图中原来存在的点是 圆点。对于一个点双，它的方点要向它包含的点对应的圆点连边。

  • 性质：

    • 每条边一定是连接一个圆点和一个方点。
    • 一个割点在圆方树上一定至少 \(2\) 个连边，非割点最多只有 \(1\) 个连边。
    • 一对点在树上路径中的圆点就是它们之间必须经过的割点。

• 欧拉回路/路径 \(60\%^+\)

  • 一个图的欧拉路径为一条经过所有边恰好一次的路径。
  • 一个图的欧拉回路为一条起点终点相同的欧拉路径。
    • 先回溯再找环，开一个栈，当一个点要回溯的时候把它压入栈中，最后栈的倒叙就是答案。
    • 无向图欧拉路径存在的充要条件是恰好两个点度数奇数，说明这两个点分别是起点和终点。
    • 有向图欧拉路径存在的充要条件是每个点入度等于出度，其余和无向图相同。
    • 有向图欧拉回路存在的充要条件恰好一个点出度多一，一个点入度多一，以它们分别为起点和终点

• 网络流

  • 最大流 \(80\%^+\)

    • EK 算法

    • Dinic 算法

    • 最大流 = 最小割

    • 最大闭合权子图：

      结论是我们如果额外建立源汇 \(S,T\)，把正点权由 \(S\) 连接其点权容量的边，负点权连接 \(T\) 一条容量为点权相反数的边，原图的边保留且容量为 \(+∞\)

      最大点权和为：总正点权 − 最小割

  • 费用流 \(60\%^+\)

    • 解决方法是在每次寻找一条费用最小的路径进行增广，知道增广不了为止，可在 dinic 上直接修改 BFS 为 SPFA。

    • 费用流还有额外的性质：具有凸性。

  • 有/无源汇上下界可行流 \(40\%^+\)

    • 无源汇考虑如何处理一条边上下界 \([l, r]\)，假设我们让这条边强行拥有 \(l\) 的流量， 然后设置上下界为 \([0, r − l]\) 就是常规问题。

      但困难在于这样做会导致流量不平衡，我们令 \(din\) 表示一个点的入流量，\(dout\) 表示出流量，\(d = din − dout\)，再建立一个超级源点 \(S\) 和汇点 \(T\)

      • 把 \(d > 0\) 的由 \(S\) 连边，容量为 \(d\)；
      • 把 \(d < 0\) 的连向 \(T\)，容量为 \(−d\)。

      跑最大流，若流量全部拉满则存在一组解，即每条边的流量 \(+l\)，否则无解。

    • 有源汇给汇到源连一条 \(+∞\) 的边即可转化为无源汇。

  • 其他流

字符串

具体是：

• 哈希 \(95\%^+\)

  好用的哈希模数：

  • \(2654435769\)
  • \(1610612741\)
  • \(998244353\)，\(10^9+7\)

• KMP \(90\%^+\)

  重在理解 nxt 数组

• Trie 与 AC 自动机 \(60\%^+\)

  重在理解 fail 指针

• Manacher \(75\%^+\)

  当前处理到的中心点被这个之前的回文串覆盖，就可以继承很多信息。

树上问题

具体是：

• LCA \(95\%^+\)

  • 倍增
  • 重链剖分
  • LCT
  • 倍增求 RMQ

• 树的直径 \(95\%^+\)

  • 两次 DFS
  • dp

• 树的重心 \(95\%^+\)

• 树哈希 \(50\%^+\)

  构造 f 函数和 g 函数

• 重链剖分 \(65\%^+\)

  感性理解

• dsu on tree \(50\%^+\)

  启发式合并

• 树分治（点分治 \(75\%^+\) 点分树 \(60\%^+\)）

• 虚树 \(50\%^+\)

数论

专业对口了属于是

具体是：

• 欧几里得算法 \(95\%^+\)
• 费马小定理 欧拉定理 裴蜀定理 Lucas 定理 \(100\%\)
• 扩展欧几里得算法 \(90\%^+\)
• 乘法逆元（\(p\) 为质数：费马小定理，否则：扩展欧几里得算法） \(90\%^+\)
• 扩展欧拉定理 \(100\%\)
• 中国剩余定理—CRT \(100\%\) 拓中—exCRT \(90\%^+\) 感觉代码并不是很好写
• BSGS 与 exBSGS 原根优化 exBSGS \(85\%^+\) 思路会了，但是……
• 阶与原根 \(85\%^+\) 之前数学老师让看了，结果居然在信竞用上了
• 积性函数与狄利克雷卷积 \(85\%^+\) 很好理解
• 前置：数论分块 \(90\%^+\)
• 筛（主要筛积性函数）（埃氏筛 \(90\%^+\) 欧拉筛 \(90\%+\) 亚线性杜教筛 \(80\%^+\) just 会思路，代码没实现过……）
• 莫比乌斯反演 \(80\%^+\)

组合容斥计数

具体是：

• 小球模型（四大类，其实就是 dp）： \(80\%^+\)

  • 球和盒子没有区别：规定盒子中的小球个数是不增 确实是 dp

  • 球没有区别盒子有区别：插板法

  • 球有区别盒子没区别：第二类斯特林数

  • 二者均有区别

    • 可以为空：染色

    • 递推

• 广义容斥

  • 子集容斥（参考莫反找到一个单位元） \(75\%^+\)

  • 莫反也是广义容斥 \(80\%^+\)

  • min max 容斥也可以算一种广义容斥 \(75\%^+\)

• 卡特兰数与格路计数：容斥 \(75\%^+\)

概率期望

具体是：

• 经典模型 \(80\%^+\)
• 后头貌似都是题

引用一下 lyc 的话：

如前面所说，一些期望 dp 不过就是普通计数 dp 套了一层概率期望的壳。

这类题太过无趣，讲它们几乎和普通的 dp 选讲无异，不能突出概率期望题的独特之处。

这里选的题目其中一部分也许能体现概率期望题目方面的独特思维。

总结

寄……