3. 其他

3.1 计数

3.1.1 映射法 (Mapping Method)

1.多对一问题：当多个方案产生相同的结果时，可以通过添加限制使其一一对应，从而简化问题。
- 例如，在 “Two Histograms” 问题中，通过添加限制使得每个方案唯一。
- 通过数感和常见结构建立映射关系，例如 “神必的集合” 和 “Slime and Sequences” 问题。
- 在信息题中，通过考虑已知信息和未知变量的关系来建立映射关系，如 “Bears and Juice” 问题。

2.组合意义法 (Combinatorial Significance Method)：如果方案数是加权的，可以通过思考权值的组合意义来简化问题。
- 例如，在 “Min Product Sum” 问题中，通过将加权方案数转化为纯粹的方案数。
- 合并多步计数来简化问题，例如 “盒” 问题。
- 外层枚举可以通过建立虚点等效替换，如 “数叶子” 问题。
- 逆向应用一些定理也是一种组合意义的方法，如 “无损加密” 问题。

3.单侧限制 (Single-Sided Constraints)：将限制转化为单侧限制，使计数顺序更加明显。
- 例如，在 “Centroid Probabilities” 问题中，通过单侧限制简化计数过程。

4.切换计数对象 (Switch Counting Objects)：通过改变计数对象来简化问题。
- 去除不易处理的限制，如 “count” 问题。
- 添加限制使得对象容易计数，如 “Two Pieces” 问题。

3.1.2 容斥/反演 (Inclusion-Exclusion/Inversion)

1.枚举不合法的个数 (Enumerating Illegal Counts)：
- 例如，在 “Two Histograms” 和 “神经网络” 问题中，通过枚举不合法的情况进行容斥。

2.强制选取与容斥系数 (Forced Selection and Inclusion-Exclusion Coefficient)：
- 如果存在选取个数≤ (a_i) 的限制，可以强制选取 (a_i + 1) 个，然后记上-1的容斥系数，如 “钥匙” 问题。

3.LGMV 引理 (LGMV Lemma)：
- 求偶数逆序对的不交路径减去奇数逆序对的不交路径，如在特殊图中可以直接求不交路径数量。
- 例如在 “无损加密” 问题中，通过容斥计算不交路径。

4.先算重后容斥 (Counting Then Exclusion)：
- 先给出一种会算重的计数方法，然后找出算重原因并进行容斥，如 “树” 和 “Finding satisfactory solutions” 问题。

5.集合划分容斥 (Set Partition Exclusion)：
- 用于解决相等关系的限制，直接对边数进行容斥，如 “Distinct Multiples” 问题。

3.1.3 统计方法 (Statistical Methods)

1.统计形式与位置 (Form and Position of Statistics)：
- 思考答案的形式并在合适的位置进行统计，例如在 “Chords” 问题中，在端点处统计。
- 在树上的点集统计，可以在LCA处统计，如 “Vladislav and a Great Legend” 问题。

2.统计顺序 (Order of Statistics)：
- 合理的统计顺序可以简化公式，有偏序关系的问题需要考虑统计顺序，如 “Inversions” 问题。
- 分步统计逐步确定结果，如 “钥匙” 问题。

3.去重方法 (Deduplication Methods)：
- 给同构的方案增加限制进行去重，如 “Piling Up” 问题。
- 计算方案被计算的次数并用除法去重，如 “Fox And Travelling” 问题。
- 无序子结构的去重可以使用隔板法，如 “Shake It!” 问题。

3.1.4 常见模型 (Common Models)

1.卡塔兰数模型 (Catalan Number Model)：
- 解决在网格图中行走但不越过某条直线的方案数，如 “Ball Eat Chameleons” 问题。

2.斯特林数模型 (Stirling Number Model)：
- 在 (n) 大 (k) 小的情况下优化计算 (n \choose k)，如 “Vladislav and a Great Legend” 问题。

3.本质不同字符串计数 (Essentially Different String Counting)：
- 直接考虑建立 DFA，如 “Strange Operation” 问题。

3.1.5 概率期望 (Probability and Expectation)

1.等概率性质 (Equal Probability Properties)：
- 利用等概率的性质简化计算，例如转等概率环，将总体方案分配到单点，如 “Wine Thief” 问题。

2.概率关键点 (Probability Key Points)：
- 如果题目保证了出现的概率，可以基于概率寻找关键点，如 “James and the Chase” 问题。

3.拆分与转化 (Splitting and Transformation)：
- 独立变量的概率可以拆分，逐步解决问题，如 “Strongly Connected Tournament” 问题。
- 前缀/差分类型的转化可以简化问题，如 “地震后的幻想乡” 问题。

3.2 基础方法

3.2.1 势能法/均摊法

势能法和均摊分析是一种分析算法性能的方法，特别适用于某些动态数据结构和具有单调性的问题。

势能法：
势能法通过定义一个势能函数来分析算法的运行时间。这个函数表示数据结构当前状态的“势能”，通过分析势能的变化来推导出操作的均摊时间复杂度。

• 覆盖问题：如小Z与函数，染色问题，如Intervals of Intervals、亿块田（位运算可以看成数位的颜色段均摊）。
• 区间合并与分裂问题：如货币、Holy Diver。通常维护的东西具有单调性，可以把值相同的一段看成区间来处理。
• 定义势能函数：如在题目Souvenirs中通过感性的角度定义势能函数。
• 具有变量一定减少的性质：如Addition and Andition，通过加速简单的过程来优化。
• 势能线段树：如在特殊区间问题上的应用，能够维护区间取min、区间除法等操作。

均摊法：
均摊分析通过分析一系列操作的总成本并均摊到每一个操作上，以得出每个操作的均摊时间复杂度。

• 总体复杂度分析：如在Berland Miners中，虽然某些操作看起来很慢，但总体复杂度优秀。

3.2.2 拆分法

拆分法通过将问题分解成独立的小问题来优化整体复杂度，关键是保证独立性。

• 打破时间顺序：如在Addition and Andition中，重新排列计算顺序以保证独立性。
• 左右端点拆分：如Student’s Camp中的区间dp问题，通过拆分左右端点来优化。
• 高维问题降维：如Berserk Robot、Jumping sequence，通过拆分高维问题为低维问题。
• 集中限制：如Drazil and His Happy Friends，通过分解限制来等效到一个主体上。
• 线段树的拆分：如在Xor-Set中，利用线段树来拆分问题。

3.2.3 调整法

调整法通过选取初始状态并逐步调整来求解优化问题，特别适用于复杂的匹配问题。

• 匹配问题：如Modulo Pairing、Bear and Cavalry，通过调整法证明结论。
• 从最优状态调整：如Two Faced Cards、Chips Challenge，从最优状态开始调整以最小代价达成合法性。
• 邓老师调整法：从合法状态开始，通过微调使得权值变大或变小，如邓老师调整法、Pastoral Oddities。
• 研究最优解性质：通过简单的不等关系，如遇到困难睡大觉、转盘、Max Correct Set。
• 两种决策问题：如Squares，主一副二的方法，先固定一个，再用另一个调整以获得最优解。
• 连续型问题转化为离散型问题：如Parametric MST、Levko and Game，通过调整法证明只会取到端点值。

3.2.4 分治法/倍增法

分治法通过将问题递归地分解为更小的子问题来解决，倍增法通过逐步扩大问题规模来优化。

• 矩形问题交替分治：如Empty Rectangles，结合点双指针单调性。
• 后缀数组倍增技巧：如Minimal String Xoration、月球列车，充分利用上一层的信息。
• 结合单次询问分析：如麻烦的杂货店、Hopping Around the Array，找到关键的可加速过程。
• 异或问题的倍增技巧：如温故而知新，基于二进制的倍增。
• 唯一后继的倍增：如唱诗，通过确定唯一的后继并让其满足优良性质。

3.2.5 神奇复杂度

通过保留有用的点或点对进行暴力计算来优化复杂度，或者利用动态扩展状态等技巧。

• 保留有用的点或点对：如Weighted Increasing Subsequences、法阵，通过基本不等关系入手。
• 动态扩展状态：如A Serious Referee，只考虑用得到的状态。
• bitset 优化：如Substrings in a String、strings，通过 bitset 加速字符串匹配和异或计算。
• 关键元素的优化：如大套子、Phoenix and Diamonds，通过找到能让值域翻倍或折半的关键元素来优化暴力复杂度。
• 四毛子思想：如strings，通过对原序列分块处理所有子集的信息。

3.2.6 根号相关

通过利用根号复杂度技巧来优化问题。

• 种类数量为根号级：如Snowy Mountain、Tree Degree Subset Sum，在总和一定时，种类为根号级。
• 值域分治：如In a Trap，通过位运算和四则运算混合预处理，实现 (O(n \sqrt{n})) 复杂度。
• 根号分治：如Summer Oenothera Exhibition，对序列跳跃问题的后继距离进行根号分治。
• 操作分块：如Jumping Through the Array，把每 (O(\sqrt{n})) 个操作分成一块分别处理。

3.2.7 贡献法

通过改变和式的计算方式，确定贡献对象并分析其贡献情况来优化问题。

• 贡献对象的确定：如Move by Prime，通过分析对象在什么情况下产生贡献来进行优化。
• 统一贡献形式：如钥匙（可以贪心匹配上的就贡献）。
• 01-principle：如线段树，基于大小关系比较的题目，通过01-principle进行贡献分析。

3.2.8 随机化

通过引入随机化技术来优化问题，减少出错概率或加速计算。

• 扩大值域：如亿些整理，通过扩大值域来计算行列式，减少出错概率。
• 随机抽样：如Olha and Igor，在出现频率差距较大时，随机抽样多次获得结果。

3.2.9 枚举法

通过适当枚举来考虑限制或将复杂问题转化为简单问题。

• 枚举不交点：如Path，枚举点不交的问题。
• 化归简单问题：如Prefix Suffix Addition、制作菜品，通过枚举法化归为简单问题。
• 切换枚举对象：如鸽子固定器，通过分析清楚枚举过程来切换枚举对象。

3.2.10 贪心法

通过贪心策略来求解优化问题，尽可能单一化贪心对象，独立化贪心代价。

• 单一化贪心对象：如[省选联考 2022] 序列变换，通过拆分法处理贪心对象。
• 树上依赖贪心：如三角形、牛半仙的魔塔，存在先选父亲才能选儿子的限制，通过堆维护合并规则。
• 凸性代价：如WYR-Leveling Ground，代价具有凸性时，通过堆贪心求解。

3.3 数据结构

这里不是系统总结数据结构，而是分享一些有趣的思维方式，这些思维点可能对你理解和使用数据结构有所帮助。当然，前提是你已经具备扎实的数据结构基础，能灵活运用各种数据结构。

3.3.1 问题转化

将问题转化为更易处理的形式，可以利用现有的数据结构和算法来解决。

• 线性变换与矩阵应用：如“密码箱”问题，将操作转化为线性变换，可以直接使用矩阵运算解决。
• 删除操作的回退机制：如“火车管理”，删除操作可以看成回退到上一时刻，用保留所有历史版本的主席树支持回退。
• 区间求和与分段函数：如“Tower Defense”，对区间内分段函数求和时，将自变量当成版本，以位置建立主席树来处理。
• 强制在线问题的离线处理：如“区间第k小”，先思考如何离线处理，再使用可持久化数据结构转化为在线问题。

3.3.2 考虑限制

在处理问题时，考虑限制条件，灵活调整限制的对象和方式。

• 切换限制主体：如“铃原露露”问题，通过重新表述限制，将限制的主体切换到更易处理的对象上。
• 保留有效限制：如“事情的相似度”，利用树上启发式合并，排除无效限制，减少需要处理的限制总量。
• 放宽限制：如“被创与地震”，寻找合适的必要条件，减少总检查次数。
• 收紧限制：如“Path”，通过讨论特殊情况，缩小需要考虑的范围。

3.3.3 确定维护对象

在设计数据结构时，确定合适的维护对象，使得问题更容易处理。

• 放宽条件转化为维护最值：如“Bear and Bad Powers of 42”、“Into Blocks”，避免维护特定值的信息，转而维护最大或最小值。
• 切换主体确定维护对象：如“The Tree”，根据修改与询问的特性，切换维护对象的角度，确定最合适的维护对象。
• 切换承载信息的主体：如“Nauuo and ODT”，切换承载信息的主体，确保原主体和新主体之间存在对应关系。
• 寻找决定性对象：如“区间和”，寻找决定答案的对象，并尽力描述和维护该对象。

3.3.4 思考如何维护

在实现数据结构时，仔细考虑如何维护信息，以确保高效性和正确性。

• 对称维护两个对象：如在图论问题中，如果难以选取主元，可以考虑对称地维护两个对象。
• 等效操作的应用：如“The Tree”、“数轴变换”，通过等效操作适应当前维护的对象。
• 整体标记法：如“Latin Square”，思考整体标记对于单点的影响，简化维护过程。
• 维护信息的顺序：如“Julia the snail”，注意维护信息的顺序，有些问题只适合以特定顺序加入。

3.3.5 常见模型

一些常见的模型和方法可以简化问题的解决。

• 递归半边模型：如“Nastya and CBS”，结合离线与在线方法，每次将考虑的区间折半处理，维护括号匹配或极长上升子序列等信息。
• 染色模型：如“轻重边”，将类区间赋值操作转化为染色模型处理，扫描线结合染色模型维护最晚被染的颜色，如“rrusq”、“区间本质不同子串个数”。
• 猫树分治：如“rprmq1”，提供分治中点，将其作为历史最大值的起点。
• 二进制分组：如“Unknown”，支持末尾的在线加入，在线段树上支持末尾删除和区间查询。