数据结构篇

数据结构

栈

• 单调栈:模板必会

队列

• 单调队列
  最大子序和

字符串

• 括号序列
  合法的括号序列：令"("=1,")"=-1
  1.和为0，左右括号数量相同
  2.所有的前缀和大于等于0
  6447. 最长的括号匹配

字符串哈希：模板题,必会

爪痕，强颜欢笑，并非是爱的某物:循环节很好找，从后往前枚举，然后验证，关键在对比字符串用到哈希，高效判重.

KMP：Nex数组是，前缀和后缀相同的最长长度，但前缀和后缀不能是整个子串本身。

周期：经典题，题解，另："爪痕，强颜欢笑，并非是爱的某物"，也可以使用KMP解决
寻找字符串：考察对KMP字符串nex数组的理解

字典树

其实就是归并前缀建树的操作

AcWing 142. 前缀统计: 与模板相反的，建树末端记录次数+1，统计时枚举所有前缀，总和答案

哈希

• 判重
  小红的双排列查询:设定好排列的哈希值，高效判断双排列
  AcWing 137. 雪花雪花雪花 : 通过哈希值确认是可能的雪花，再进一步判重
• 异或+哈希: 利用哈希的独特性，结合异或自身等于0的性质，可以高效判重
  -小紫的优势博弈
  -H. Robin Hood Archery

图论 Graph Theory

基础

• 图的遍历

  A Path in A Dictionary：找出最小字典序简单路径，对于每个点，按照字典序搜索下一个点，如果第一次搜这点却不能到达终点，那下次就没有必要搜索

• 建图思想
  Train Wreck:任意入栈后的栈不能相同，那么模拟，可以构造出一个树来表示所有时刻的栈，那么此时就可以由此构造一个图来表示，方便后续的处理

• 思维题
  B - Triangle Toggle : 注意到一次操作，对顶点的黑边数的影响分别是0，-2，+2，，所以最终一个顶点最大的黑边数与初始黑边数同奇偶

树 Tree

• 基础
  在树（或二叉树等树形结构）中，节点的 “度”指的是该节点拥有的子节点的数量

  叶节点，叶节点是度为0的节点：D. Arboris Contractio:最终的图是菊花图，因此找出最小的点使得其直接相连的非叶节点最少
  -二叉树

  1. 对于任意二叉树，结点总数n由度为 0（叶子结点）、度为 1、度为 2的结点数之和组成
  2. 对于任意二叉树，度为 0 的结点数比度为 2 的结点数多 1

• 计数问题
  Pair Counting: 理解好题意，题解

树的直径

两遍dfs，第一次dfs，任取一个点，找到离开该点距离最大的点，第二次dfs，以该点为起点，找到离该点最远的点，此时两点距离即为树的直径

并查集

• 简单习题：
  AcWing 237. 程序自动分析:需要离散化
• 带权并查集：AcWing 238. 银河英雄传说[NOI2002]:模板题
• 解决区间问题：
  • 小笨的蓄水池：并查集的点也可以是区间
  • 并查区间染色模型: 区间每个元素指向后一位，使得遍历达到线性复杂度
    • AcWing 6100. 奶牛选美
    • 疯狂的馒头
• 启发式合并：
  • [NOIP 2013 提高组] 货车运输,将小的并查集合并到大的之中

最近公共祖先

倍增法
dfs序
树链剖分
本人只会树链剖分，多写，方便以后写树链剖分
小红的树不动点：不断找满满足第i个点是不动点子树的深度dep，会有个dep个子树满足第i个点是不动点子树

最小生成树

一般有两种算法：Kruskal算法和Prim算法
次小生成树:题解

• 增加理解：AcWing 346. 走廊泼水节:加深你对最小生成树边权的理解，两个完全图（节点数分别是a,b）合并成完全图需要a*b个边
• 超级源点：应对既有点权还有边权，求最小值时，将点权转化为由超级源点（一般为0）指向该点的边权，再求最小生成树
  练习题:
  1. [USACO08OCT] Watering Hole G
  2. CF1245D. Shichikuji and Power Grid
• 最大生成树：有时候需要构造最大生成树.
  连通块的思想
• 最小限度生成树：先不连s，划分成连通块求最小生成树，再相连
• 野餐规划:上一题是恰好k个，这一题是可以[1,k]个

线段树/树状数组

1. 进阶模板：

• 树状数组 2：利用差分达到区间加+k的操作，利用树状数组迅速查点
• 线段树 2: 重点是先乘后加，加深你对laze tag的理解

2. 新定义
   线段树的应用不仅在于查询区间和，区间最小/大值，还可以其他你需要的值
   - 区间gcd
   - D. Gifts Order：题解
   - 更改区间字符
   [蓝桥杯 2022 国 AC] 替换字符/G. Mass Change Queries
   - 总结：这种不是像板子一样的使用线段树，而是要思考线段树上，子节点与父节点传递关系，例如lazy的传递，从而高效的利用线段树解题

3. 离线/在线处理
   这两个算法有时涉及区间反复的修改，查询...
   而查询分离线和在线，离线查询可以最后给出全部回答，在线则必须立即给一个回答，两者均有不同的技巧：

   • 离线
     离线有时可利用不同询问中，重复的信息以便高效回答：
     例题：

     1. P1972 [SDOI2009] HH的项链
        这里给定询问区间，由上述离线查询的核心思想，我们可以询问顺序排序，改成以r值从小到大的排序.由于我们只考虑种类，所以只保留尽可能靠右的不同种类的贝壳，只要在每次查询就能保证答案不重.
        类似的题：数对统计
        以上两题的详细题解

   • 在线

树链剖分

• 相较模板更简单的题：
  [ZJOI2008] 树的统计
• 边权化作点权：
  • [NOIP 2013 提高组] 货车运输
  • P3038 [USACO11DEC] Grass Planting G)

基环树

拓扑排序

• 基础
  C. Max Tree：因为是树，所以无环，题目的条件仅仅让你决定边的方向，于是形成拓扑图，以此来决定答案

• 与状态压缩结合
  可达性统计

最短路

• Floyd算法
  Floyd算法中使用前k个节点更新最短路的思维：

  • 灾后重建

• dijkstra算法

  • 最短路模板
  • 次短路
    次短路基于最短路算法，再更新最短路的同时记录次短路
  • 最短路计数：最短路距离更小方案数直接由前一个点转移，最短路距离相同累加方案数
  • 建反图：可以将原图建在每个点+n之后
    邮寄员送信

• spfa算法: 负环

  • [NOIP 2009 提高组] 最优贸易:有环就可能需要用到spfa，双向spfa

    此题也启发我们，最短路算法不一定用来求两点之间最短距离，也可以用来求两点之间路径上的最大值或者最小值

  • SLF优化算法.道路与航线:板子优化

• 分层图:这一层到下一个层，为出现的特殊情况，分多少层取决于出现的次数

  • 通信线路
  • [NOIP 2009 提高组] 最优贸易: 此题亦可用分层图来写，第一层到第二层同一点的边权为水晶球的负值，表示买入，第二层到第三层同一点的边权为水晶球的正值，表示卖出，这样就形象地表示买入卖出，到3*n的点最短路就是赚的钱
  • 分层图有时候会出现内存不够的情况
    • 可以考虑建立中转节点来实现层与层的转化，同时也不必使每一层都完整，离散化点的编号
    • 或者只分两层，滚动求最短路，Asia EC Online 2025 (I) M. Teleporter

图论的连通性

• 传递闭包:模板题，改改floyd就好，可以用bitset优化
  AcWing 343. 排序

连通性:主要考察连通性，割点，割边，缩点

• 连通性
  图在建立时的连通性就在变化：
  P2700 逐个击破：该题给定K个点不能连通，逆向思考，如果建图的时候，保证这个k个点始终不连通，那么就达成了目标
  连通分量
  图的连通分量:难点主要在遍历联通的点上，从二进制角度思考，对于整数x,应该遍历x取反后，所有1的位置组成的二进制子集。题解
• 缩点
  模仿者:简单题