Disjoint

虽然我不懂计算几何，但是两个三角形互相进入，感觉很涩啊！ —— By 【】 考虑两个互不相交的三角形，寻找一个方式能够不重不漏地统计它们。 容易发现两条不交的线段 \(A_1A_2,B_1B_2\) 之间，必然存在一条直线将 \(A_1A_2,B_1B_2\) 分在直线两端，且与 \(A_1A_2, ......

首先我们知道，若一个数是另外两个数的公共因数，那么它肯定能整除另外两个数的最大公约数。 所以我们可以**枚举最大公约数的质因数**，再把这个质因数在最大公约数中除完，并且答案加一。 注意，要用 `long long` 不然 `int` 溢出之后还在循环，就会导致超时。 ```cpp #include ......

并查集是算法竞赛中常用的一种数据结构。 其主要功能是查询**两个元素是否在同一个集合**以及**将两个集合合并**。 ### 算法思想 1. 我们将所有元素建成很多树（森林），每一棵树就是一个集合，比如下图有 $\{1, 2, 3, 4, 5, 6\}, \{7, 9, 10, 11, 12, 13 ......

题目大意: 给出一个序列P , n 个点 每次可以选择2个 相邻区间进行合并, 会产生一个贡献值,当然合并n-1就合并完了, 问在所有的情况下, 贡献和是多少 思路: 易错点: 这个所有情况, 你枚举的合并的那个先后顺序是有关系的!!! 因此直接去区间dp只能把各个合并的情况给弄出来,但是他的先后顺 ......