mygr main()

相关链接：[[最大公约数]]，[[筛法]] Trick 固定右端点，一段数中不同的最大公约数的数量最多只有 $logn$ 个最大公约数 当遇到质因数分解+状态压缩/容斥一类需要减小 $n$ 的范围的题目时，考虑将其按照 $\sqrt{n}$ 为界分解为大小质数 寿司晚宴 ， 卡牌 ^372880 $n$ 内的本质不同质因子个数不是 $log2$ 级别的，事实上比这小得多，使得其能够跑 $10^7$ 以内的范围

[[线段覆盖]] 反悔贪心 # 数据备份

...

2-SAT 当遇到某些选择只有两种变化，问合法方案的题目，考虑使用 2-sat解决 毛子老哥重量级建图技巧题 通过向自己的反连边的方式代表某个点不能被选择 环 无向图无权图上找最小环，可以考虑枚举每个点作为环上一端点，然后bfs处理 $dep$ ，在发现已访问的节点后更新答案，保证不走重复边即可，这样子跑一遍是 $O(n+m)$ 的，当发现实际环的代表元端点数量很少时，可以暴力枚举 # CF1325E Ehab’s REAL Number Theory Problem

考虑对于两个几何图形 $A,B$ ，那么他们的闵可夫斯基和即为 $$C=\bigcup_{a\in A,b\in B}a+b$$ 考虑他的数学意义： $(A_x+B_x,A_y+B_y)$ ，可以利用其来做一些跟凸性相关的东西 例如当我们需要在两个二元组集合 $A,B$ 中分别选出一个元素，使得 $(a_x+b_x)(a_y+b_y)$ 最小时，我们可以这么考虑 将集合内每个点转换到坐标轴上，并对 $A,B$ 求出闵可夫斯基和，最后面的答案一定是下凸包上的点 由于只需要求下凸包，所以对 $A,B$ 分别求出下凸包，再跑闵可夫斯基凸包和就可以了 可能还有许多性质，但本质都在于将二元组的加和再乘积转化为凸包上问题 放到本质上来说，我们对于函数 $f_{i}=\max_{j}{g_j + h_{i-j} }$ (max+卷积)，若有 $g_{i},h_{i}$ 都为凸函数，则最终的 $f_i$ 为 $g_i,h_i$ 的闵可夫斯基凸包和

任意取出树上的一条路径，有大于 $\frac{1}{2}$ 的概率经过树的重心，可以通过此乱搞 # 在路上 当只需要提取出一个序列的中位数/kth元素时，可以考虑像 nth_element 一样随机一个节点，然后分治，时间复杂度是期望 $O(n)$ 的 # 在路上 当图上问题转化为二分图问题更好解决时，可以考虑将图随机染色 # Tourism ，# 「2020-2021 集训队作业」Storm

# LOG 判断方法：将所有元素对当前值取min，判断和是否大于当前值乘配对数即可

考虑这么证明： 将所有点绘制到一个坐标系上，若一个点被选择了，则我们称其为 $1$ 结论：当我们有 $i < j,p_{i} > p_{j}$ 且 $i$ 被选择，则 $j$ 一定被选择 我们考虑这么证明：若 $j$ 被选择，则一定能够构造出一种新的方案使得其比当前方案更优 使用反证法，不妨设当前是最优答案且答案中存在两位置 $i,j$ 使得 $i<j,p_i>p_j$ 且 $i$ 选 $j$ 不选 不妨找到其中使得 $p_j-p_i$ 最小的 $i,j$ ，那么他就会满足 $p_i,p_j$ 中间没有比 $p_i$ 小且被选择的点 $p_i,p_j$ 中间没有比 $p_j$ 大且未被选择的点 没有值在 $i，j$ 中间的元素 发现这样就将整个平面分割为了九个部分，我们分别将其称为 $$\begin{array}{a|a|a|a}\hline 1 & 2 & 3 \ \hline 4 & 5 & 6 \ \hline 7 & 8 & 9 \ \hline\end{array}$$ 考虑让 $i,j$...

考虑使用 b 算法解决 问题就变成了：对于一个集合 $S$ ，我如何去寻找一个点 $p$ 使得 $$\min_{s \in S}w_{p}+w_{s}+dis_{p,s} \le \min_{s\in S,j\not \in S \wedge j \not = p}w_{s}+w_{j}+dis_{s,j}$$ 我们称每个节点所属的集合为他的颜色 考虑启发式合并，对树上每一个点 $u$ 用一个 $set$ 维护子树内每种颜色的点的 $dis_{u,p}+w_{p}$ 的最小值，额外维护所有颜色中的最小值和次小值，启发式合并的同时统计每种颜色的答案即可 发现其实不用启发式合并，用类似树形dp的方式上下 dfs 即可

考虑将每次的决策分为两部分：从左往右的以及从右往左的 额外记录一个 $f_i,g_i$ 表示 $a_i,b_i$ 是否被选择 对于从左往右的，直接线段树上分治即可 对于从右往左的，我们考虑记录一个 $h_i$ 表示 $i+1$ 到 $i$ 的反向边的流量 考虑记录区间前缀的最大联通 $b_i$ ，区间后缀的最大联通 $a_i$ ，区间内最大的从右到左段的大小，区间从右往左方案中的最大值 因为区间内 $h_i$ 非负，所以只需要记录区间内 $Min$ 为 $0$ 以及 $Min$ 非 $0$ 的情况即可