Q779的博客

洛谷P4357 [CQOI2016]K 远点对题解题目链接：P4357 [CQOI2016]K 远点对题意：给定平面内 \(n\) 个点的坐标，求欧几里德距离第 \(k\) 远的点对本题的正解应该是旋转卡壳、分治等算法，不会而

2022-03-01 OI

算法数据结构玄学

CF1200E Compress Words 题解题目链接：CF1200E Compress Words 题意：给定一堆字符串，依次插入答案串尾部，每次删掉答案串的后缀与待插入串的前缀的最大匹配串解法一 KMP 这个解法常数比较

2022-03-01 OI

算法字符串

洛谷P2387 [NOI2014] 魔法森林题解题目链接：P2387 [NOI2014] 魔法森林题意：每条边有边权 \(a,b\) 两个，求 \(1\) 到 \(n\) 的路径使得所经过的边中 \(\max\{a\}+\max\{

2022-02-25 OI

算法图论数据结构

洛谷P4234 最小差值生成树题解题目链接：P4234 最小差值生成树题意：给定一个点标号从 \(1\) 到 \(n\) 的、有 \(m\) 条边的无向图，求边权最大值与最小值的差值最小的生成树，图可能存在自环这个题不太好利用k

2022-02-25 OI

算法图论数据结构

LCT求解最小生成树前言最小生成树模板： P3366 【模板】最小生成树朴素的kruskal为主流最小生成树算法而LCT(link cut tree)也是可以维护最小生成树的由于LCT动态维护最小生成树，加上常数较大在实际测试中

2022-02-25 OI

算法图论数据结构

洛谷P2147 [SDOI2008] 洞穴勘测题解题目链接：P2147 [SDOI2008] 洞穴勘测题意：给定若干个点，动态连接（无向边），询问连通性由于它有删边的操作，因此用并查集并不可行于是想到LCT（？由于LCT有

2022-02-24 OI

算法数据结构

洛谷P1501 [国家集训队]Tree II 题解题目链接：P1501 [国家集训队]Tree II 题意：树上区间加&乘&link&cut 显然LCT模板题，因为树链剖分并不能维护动态连边考虑如何维护区间乘

2022-02-24 OI

算法数据结构

浅谈快速乘前言想必大家都听说过快速幂那快速乘是个什么东西呢？考虑取模操作a*b%p，1^10 ≤ a,b,p ≤ 2^10 可以发现在 long long情况下，我们直接取模会溢出那么怎么办呢？题目链接：https://www.

2022-02-13 OI

算法数学

AT4284 [ABC116C] Grand Garden & 洛谷 P1969 P3078 P5019 题解题目链接：AT4284 P1969 P3078 P5019 题意：若干次区间减一，使所有数相等，求最小次数这几道题

2022-02-07 OI

算法

洛谷P1234 小A的口头禅题解题目链接：P1234 小A的口头禅给出了一个矩形，让你求出里面有几个hehe（方向无所谓，斜着不算）数据范围很良心，嗯~ 所以暴力枚举即可值得注意的是 \(\tt{eheh}\) 这种也算顺便

2022-02-05 OI

算法

洛谷P2804 神秘数字题解题目链接：P2804 神秘数字题意：询问有多少段连续区间的平均值大于 \(m\) 可以发现将每个数都减去 \(m\) 后任意和大于 \(0\) 的连续区间都满足题意区间和可以用前缀和优化，记为 \(s

2022-02-03 OI

算法数据结构

洛谷P1522 [USACO2.4]牛的旅行 Cow Tours 题解题目链接：P1522 [USACO2.4]牛的旅行 Cow Tours 题意：给定一张无向图，有至少 \(2\) 个连通分量，定义直径为每个连通分量中任意两结点的最短

2022-02-03 OI

算法图论