mygr main()

Trick： 在做涉及到类似向量一类的问题时，考虑将两点化为线，将三点化为面，最后变为凸包去解决 合金

其实与分治本质相同，都是确保两个不同的数都被分至两种不同的集合中过 # 旅行者

经典PPT 本质是通过离线扫描线+权值平衡树将所有需要查询的部分离散到数轴上

相关链接：[[二进制分组]]，[[Trie]]，[[异或]] [[异或]]： Trick： 类比于前缀 gcd， 利用"优势段"有且仅有 log 段来使用数据结构暴力维护 # MIN_XOR_SEG ^8ecb0b

[[树分治]] 朴素分治 本质有两种： 对于计数/查询问题，则是在统计经过中点的合法点对数量 对于决策问题，则是递归为两个与相同的子问题进行求解 决策问题 最优化决策 当证明出可以递归为两个相同的决策去求解出方案，再合并得出最终方案，且最终方案一定最优时，则可以考虑 可行性决策 当一个可行的答案可以分解为两个子方案的和时，则可以考虑，注意需要满足分解的两个子问题存在合法解 而“合法解的存在” 一方面可以证明，另一方面可能 题目条件已经给出 最值分治 相关：[[笛卡尔树]]，[[启发式合并]]

数据范围较小且每个统计的问题可以分解为几个互不相干的小问题再合并处理时，考虑区间dp 关键在于合并的本质：枚举了所有可能的合并方式以及合并顺序，这也是其与线段树上合并信息的不同点 “信息间的合并顺序会对结果产生影响” #under_construction 凸包的三角剖分与区间dp的结合 对于代价随着时间的变化而增长，满足条件后停止增长的问题，可以考虑把每一时刻的代价表示为每一时刻未满足条件的代价的和 修缮长城 ，或是将每一段的代价乘上未来累计所需的时间 修车 对于字符串的拼接问题，也可以使用区间dp去解决 https://www.luogu.com.cn/problem/P2400

总题单： 何为动态规划 何为动态规划二代目 [[状态压缩]]： [[区间dp]]： [[序列分段]] Trick： 放缩与删减状态 放缩即为将必定较劣的答案 或 后续注定被删去的答案合并统计，从而达到减少分类讨论的效果 典型的题目有 #under_construction 删减状态即将某些在总决策中没有特长的决策删去，或者将相同类型的状态合并 典型的题目有 背包 ，划艇 misc 注意观察已知部分，例如当已知当前选到第 $i$ 个位置时，那么当前位置必选，也就可能可以省略掉一些状态 many moves 动态规划问题添加元素不一定是唯一的出路，也可以考虑在原有状态的基础上合并状态 找硬币 当碰到“某类方案数的 $x$ ”次方一类的题目时，可以考虑用类似多项式拆分一类的方法，将其拆为“ $x$ 个线程同时，全程相等的方案数 管道取珠 离散化是个好东西，有时候可以砍去许多本质相同的决策 划艇

有几种常见模型： 区间查询区间序列中区间的最值 这种问题一般都是在区间序列的基础上进行分块，然后考虑对块内所有区间合并答案，对散块用正常方法暴力查询，然后根号平衡即可 例题：# P11750 「TPOI-1D」谢谢您。 区间查询区间并 转化为对区间序列的扫描线问题，元素序列上上标记 “上次被区间标记的时间”，查询时直接查询 “上次出现时间在左端点之后的” 元素的权值和，用分块朴素维护即可 例题：# P6783 Ynoi2008 rrusq

Trick 当无法使用双指针(不具备单调性时)，考虑转化为单调队列解决 # 划分

# 从零开始的博弈论 # 何为博弈论 相关链接：[[异或]] 反 Nim 游戏 对于一个游戏，当一个人无法取时则胜利 结论： 当场面上 $\forall i,a_i=1$ 时，若 $\mid a\mid \mod 2=0$ 时则必胜，否则必败 当场面上存在一个位置使得 $a_i > 1$ 时，若 $\oplus_{i}a_i \not = 0$ 则先手必胜，否则必败 考虑证明 对于结论一是好证的 对于结论二，则每一步先手都必定能够构造出一种方式使得 $\oplus_{i}a_i=0$ ，而后手则一定不能，由于当前局面并非所有数都为 $1$ ，且会留给后手一个异或和为 $0$ 的状态，故此时后手的局面中必然存在 $\ge 2$ 个非 $1$ 的数，于是最后面一定会留给先手一个有且仅有一个数使得其 $> 1$ 的情况，此时就可以随意控制其到上一个结论了 当遇见与异或相关的 SG 函数时，可以考虑将其往线性基上面去靠 New Nim 博弈论不一定要推奇奇怪怪的式子，也有可能从最朴素的 dp 出发也能达到推出类 SG 函数的状态式，而且就大部分题目而言的话还是 dp...