[我的 Slope Trick 题单](https://www.luogu.com.cn/training/851622#problems) # 前言 本文讲的 Slope Trick 与传统 Slope Trick 在求得答案的过程有少量差别，个人感觉更好理解。 **本文存在大量平衡树。** # Slope Tric…

考虑算不合法的情况。显然是买了 $w=1$ 的 $i,j$，然后存在一个没有买的 $w=2$ 的 $k$，然后满足 $a_i+a_j j$）和 $k$。显然要满足以下几个条件： - $a_i k$，此时无论 $w$ 为啥，$p$ 的性价比均高于 $k$，这样的 $p$ 有 $n-k$ 个，$w=1$ 时花费 $1$，$…

# CF1797F Li Hua and Path ## 前言 模拟赛赛时打了一半，拿了 $q=0$ 的。~~2e5不就是给双 log 过的吗~~ ## 正文 首先考虑解决 $q=0$ 之后怎么做。添加一个点，新的贡献也一定是由这个点贡献的，并且是作为最大值（新点编号一定比原来的大）。 考虑求不合法方案数。如果 $fa…

$$ \sum_{i=1}^n\sum_{j=1}^mc(ij)\varphi(ij)\\ =\sum_{i=1}^n\sum_{j=1}^m\frac{\varphi(i)\varphi(j)\gcd(i,j)}{\varphi(\gcd(i,j))}\sum_{x|i}\sum_{y|i}[\gcd(x,y)=1]…

# [CSP-S 2025] 道路修复 / road 过民间数据了来水一发。 发现 $k$ 非常小，因此考虑枚举哪些村庄被操作。 使图联通且花费最小，这符合**最小生成树**的定义。因此考虑建边后跑 Kruskal，时间复杂度 $O(2^k(m+nk)\log (m+nk))$。 这并不能接受，于是考虑缩小边集大小。先…

# P5325 【模板】Min_25 筛（PN 筛） 定义 $\tt{Powerful\ Number}$ 为每个质因子项次数至少为 $2$ 的数。 显然的一点，任意一个 $\tt{Powerful\ Number}$ 可以被表示为 $a^2b^3$。而在 $n$ 以内的 $\tt{Powerful\ Number}$…

# P3768 简单的数学题 ## 题意 给定 $n$ 求： $$ \sum_{i=1}^n\sum_{j=1}^nij\gcd(i,j) $$ ## 正文 性质： $$ n=\sum_{d|n}\varphi(d) $$ 那么： $$ \sum_{i=1}^n\sum_{j=1}^nij\gcd(i,j)\\ =\s…

# Teleportation in Byteland 学校联测搬了这道题，赛时脑抽了，没想到树剖是一款。 ## 1. $O(\sum \text{dis}(s,t)\log V)$ 发现最多只会往下 $\log V$ 次，并且在一个点做完全部的向下必然是不劣的。因此可以考虑枚举向下的次数 $k$，答案就是由原路径加上…

# P7220 [JOISC 2020] 掃除 ## 题意 有四种操作： 1. 询问点 $x$ 的坐标 2. 对所有 $y\le l$ 的点进行 $x=\max(x,n-l)$ 的操作 3. 对所有 $x\le l$ 的点进行 $y=\max(y,n-l)$ 的操作 4. 加入一个新的点 $(x,y)$ ## 部分分…

# P13954 红黑树 ## 暴力 DP 设 $f_{u,i}$ 表示点 $u$ 为根的子树中的叶子节点到 $u$ 的路径上黑点个数均为 $i$，此时的最小修改数。 分两种情况考虑。 第一种，点 $u$ 的颜色最终为红色，可得转移方程： $$ f_{u,i}=\left[s_u=1\right]+\sum_{v\in…

# AT_joisc2017_c 手持ち花火 ## 前言 ~~今典的拓拓拓拓展题~~ 校内模拟赛搬了这道题，来写个题解。 ## 正文 最优的方法是所有人朝着 $k$ 走，与 $k$ 相遇时就一起走，当 $k$ 的火把熄灭时再把其他同位置的一个火把点燃，相当于每个火把加了 $t$ 秒的总燃烧时间。因为所有人速度一样，因此…

实际上 ``` 2 2 1 2 2 1 1 1 2 No 2 2 1 1 1 2 2 1 2 No ``` 可以hack非常多人（包括STD）

# P13009 特殊性质启发我们应该考虑分类做。 1. 当 $a_i\le \sqrt m$ 时： 此时 $\dfrac{m}{a_i}\ge\lfloor \dfrac{m}{a_i}\rfloor \ge a_i$，则 $\dfrac{m}{\lfloor \dfrac{m}{a_i}\rfloor}\ge a_…

# [COI 2025] 象掌兽 / Lirili Larila # 前言 本题解仅说明思路，代码之后补上。 # 正文 ## 树 考虑树怎么做。  先考虑距离为奇数的两个点。例如 $(7,2)$…

# P3992 [BJOI2017] 开车 ## 前言 分块好题。 本文讲述的算法总复杂度为 $O(q\log n+q\sqrt{n}\log n)$，其中瓶颈在桶（unordered_map）。 ## 正文 考虑不带修。首先将 $a$ 与 $b$ 的元素放入 $c$ 排序并去重，设第 $i$ 位及其以前车的数量减加油…

在文章《[RMI 2024] 八边形 题解》发表评论：

这个好可爱呀

原因： 1. 本题考查CDQ的运用，同时还有颜色段均摊ODT的运用，整体思维难度较高（虽然有分块做法，但是还是很难，有比这简单的黑题 2. 码量很大，细节较多，还是很难调的，因此建议升黑

# P11678 Watering the Plants P ## 前言 这道题我做了四天，是一道很有难度的题。~~标记打错+少判情况~~ ## 题意 有 $n$ 个水池，每次可以花费 $w_i$ 的代价让第 $i$ 和第 $i + 1$ 个水池的水量加 $1$。求最小代价使第 $i$ 个水池中至少有 $a_i$ 的水…

# P9970 套娃 ## 前置知识 1. 主席树（动态开点权值线段树） 2. set 维护 $\text{mex}$ ## 在线区间 $\text{mex}$ 考虑确定右端点后 $\text{mex}$ 咋求。设 $i$ 出现最晚的位置记为 $p_i$，若没有则为 $0$，权值线段树单点赋值实现；询问时，满足 $0\…

# [ABC392G] Fine Triplets ## 前言 赛后才知道有官方库。 ## 正文 题意就是问有多少三元组 $(i,j,k)$ 满足 $a_j-a_i=a_k-a_j(a_i #include #define int long long using namespace std; using namespa…

# P11664 [JOI 2025 Final] 缆车 ## 前言 vector 还是太好用了，二分跳了一晚上。 ## 正文 这里定义 $[l,r]$ 为好的区间即从 $1$ 号点只经过编号 $\in[l,r]$ 的公司修建的边，可以到达其他任意一个节点。 该图为一个 DAG，若要满足从 $1$ 号点可以到达所有点，…

在讨论《81分鑪关求条》回复：

好了是rj vector的问题，换成数组就A了

```cpp #include #define int long long using namespace std; int n , m , p , q; const int N = 4e5 + 5 , inf = 0x7f7f7f7f7f7f7f7f; vector s , a[N] , g[N]; int d[4…

细节很多，双 tag，看24S T3，NOIPT1，这题给蓝是合理的

# SP8073 CIRU - 圆并集的面积 ## 前言 初中生第一次接触 Simpson 公式，有写得不好的请指出。 本题要求**圆并集的面积**，而 [P1222 三角形](https://www.luogu.com.cn/problem/P1222) 是求**三角形并集的面积**，也可以用本题的方法计算。 ##…

\# 1 2 3 5 9 一天下五个点，堂玩了

# [AT_abc389_f [ABC389F] RG](https://www.luogu.com.cn/problem/AT_abc389_f) ## 前置 1. 线段树 + 二分 2. 平衡树 ## 正文 ### 方法一（线段树） 将所有询问离线下来并排序，记为数组 $a$。可证得在操作中 $a$ 满足单调不降性…

# [P9097 [PA2020] EIF](https://www.luogu.com.cn/problem/P9097) ## 前置 1. 分段 DP 2. 树状数组 3. 二分等其它算法 ## 正文 设 $f_i$ 为以 $i$ 为一段区间结束点，前 $i$ 个点的最小连边数。可以易得以下转移方程： $$ f_i…

在文章《题解：P11570 「chaynOI R1 T3」镍铬合金机器人》发表评论：

所以低减呀

# P11570 「chaynOI R1 T3」镍铬合金机器人 ## 前言 这道我场切的，但是赛后发现题解是高贵的单 $\log$ 做法，而我是低贱的双 $\log$ 做法。 那就讲一下双 $\log$ 的做法吧。 ## 正文 首先要会求区间 $\text{mex}$。设 $mx_{i,j}=\text{mex}(\{…