Kx-Triumphs

摘要： 前言 题目链接 首先说明一下，这题题面有个地方不太严谨：题意要求求凸包直径，然而当 \(n=2\) 时凸包并不存在，此时直径也应该不存在。所以应该是求平面中最远的点对的距离。 旋转卡（qia）壳可以用于求凸包的直径、宽度，两个不相交凸包间的最大距离和最小距离等。 这里就不过多赘述了，仅介绍两种不同的 阅读全文

摘要： 题目链接 这里使用扩展域并查集实现。 既然来看题解了，相信你已经读懂题了，这里不再赘述题意，直接进入主题。 没读懂可以去看其他题解 思路： 为何用并查集 考虑什么情况下一个变量的最终值为 \(U\)？当且仅当一个变量 \(x=-x\) 或 \(x\) 与 \(-x\) 中有一个等于 \(U\) 那么 阅读全文

摘要： Trick 树的直径性质了解加深 P1099 [NOIP 2007 提高组] 树网的核 P2491 [SDOI2011] 消防(P1099加强版) 尾部添数ST表 P1198 [JSOI2008] 最大数 splay实现细节经验 P10689 SuperMemo 当贡献与边之间的关系有关，而与点无关 阅读全文

摘要： 随机爬树题解 题目传送门 更好的阅读体验 \(n^2\) 暴力： 思路： 求期望，即求所有点的权值乘上概率后的和，即： \[ans=\sum_{u \in V}{P_u a_u} \] 求每个点的概率 \(P_u\) ： 由题，令走到父亲的概率为 \(P_f\)，走到儿子 \(s\) 的概率则为 \ 阅读全文

摘要： 题解 更好的阅读体验 考虑如何计数： 我们在建树的过程中记录每个模式串的结束位置 \(End_i\)。 在文本串匹配时，每跑到一个结束位置，就将其对应的 \(cnt\) 加一即可。 询问与统计答案： 询问：不同于简单版 I，每个串每出现一次都要统计，不能提前结束。 统计答案：所有模式串枚举一遍，看哪 阅读全文

摘要： 前置：并查集 扩展域并查集(种类并查集) 思想：每种个体存在多种不同的关系时，将这些关系分为不同的集合，最后通过并查集维护每个集合内部与两两集合之间的关系。 理解思想 一.团伙 给定若干满足如下两条的关系，求会构成多少个团伙： \(x\)、\(y\) 为朋友。 \(x\)、\(y\) 为敌人。 普通 阅读全文

摘要： PS： 线段树并不与扫描线绑定，此篇仅讲解更接近原理的 \(n^2\) 做法，线段树做法为基于此做法的时间优化。 扫描线（实则为一种思想） 用处：求取图形面积、周长并。 思想：将整个图形用一条线扫过去，统计扫过一次得到的答案。 实现过程： 以从左往右扫的矩形面积并为例： 预处理 将每个矩形的两个 \ 阅读全文

摘要： DP-子序列问题(待完善 上升子序列 定义：在一个序列 \(a\) 中满足 $a_j < a_i $ 且 \(j<i\) 的子序列。 \(e.g.\) 在序列 { \(0\) \(3\) \(2\) \(5\) \(1\) \(4\) } 中 { \(0\) \(1\) \(4\) } 与 { \( 阅读全文

摘要： 前置 单调队列（没学过或忘了点这里） 简化题意 有一块牛排，要求对它烹饪 \(2n\) 秒，可在给定的 \(k\) 个时间段中将它翻转任意次，使得牛排两面都受到了 \(n\) 秒的烹饪。 状态设计 可以发现当总共煮了 \(i\) 秒，其中一面如果煮了 \(j\) 秒，自然可以求出另一面为 \(i-j 阅读全文

摘要： 算法总结 - 重链剖分 概念 重儿子（红点）：父节点 \(f\) 的子节点中子树大小最大的儿子。 轻儿子（蓝点）：父节点 \(f\) 的子节点中除重儿子以外的节点。 重链（橙圈框出的链）：链顶为轻儿子，由重儿子组成的链。 重链剖分 用处： 将树划分成不超过 \(\log{n}\) 条连续的链。 通过 阅读全文