Muyang的博客

重链剖分（因为主播只会这个）

以前放学，听着音乐 像伤感深情的片尾曲 有飞鸟和夕阳​现在放学，走在路上 像群贤毕至的开头曲 你的身边会经过这些人:放肆的初三，细腻的初二，更有百态的初一​真的愈发感觉自己老了，这一届初一给我的感觉太奇特了……

C++中字符串的基础知识以及 KMP 和字典树算法。

点开这篇视频会自动播放，声音有点大小心点。

讲解 DP 思路及经典 DP 模板。

有点耻辱，打比赛的时候去吃饭了，最后赛后 20 分钟就把 E 题写出来了……还给我掉了分╥﹏╥…又被 ABC 做局了。 题目大意 给定长为 $N$ 的整数序列，每次操作可以将单个元素加一，求至少多少次操作，使得每个长为 $L$ 的子段和为 $M$ 的倍数。 题目分析让每个固定长度的子段和为一个数的倍数……这一眼就很数学，或者说很有规律啊。我们发现，如果有$$\sum_{i=k}^{k+L-1}a_i\equiv \sum_{i=k+1}^{k+L}a_i\equiv0\pmod{M}$$那恒等式两边减去公共部分 $\sum_{i=k+1}^{k+L-1}a_i$，就有$$a_k\equiv a_{k+L}\pmod{M}$$那我们就可以把每隔 $L$ 个的数分为一类，每类的数字对 $M$ 取模相同。那这样，我们只需要把前 $L$ 项的数算出，就可以用把剩下的都算出来了。 只用算前 $L$ 项，观察到 $L\leq N,M\leq500$，我们可以枚举每一项和前一项模 $M$ 的余数，就可使用动态规划进行状态转移（一眼 dp）。 令 $dp_{i,j...

前言十年 OI 一场空，不开 long long 见祖宗。这是我第一次洛谷的官方题解。 题目大意给你一个 $N$ 个点，$M$ 条边的无向图，图中有 $K$ 个点有机场，有机场的点可以耗时 $T$ 时抵达另一个有机场的点。 有 $Q$ 个查询，分为 $3$ 种:加边、加机场、询问所有联通的点之间的最短距离之和。 分析注意到 $N\leq500$，还要求最短路、加边，我们可以直接使用邻接矩阵存图，并用 Floyd 计算多源最短路。 使用 Floyd 进行加边操作很简单，假设加上了连接 $u,v$ 长度为 $w$ 的边，状态转移方程如下： $$dis_{i,j}=min{dis_{i,j},dis_{i,u}+w+dis_{v,j},dis_{i,v}+w+dis_{u,j}}$$ 但是添加机场应该怎么处理呢？其实很简单（虽然我在比赛的时候 D 没开 long long 调了好久导致E没时间）。 可以添加一个虚点 $N+1$，让这个点与所有有机场的点连接一条长为 $\frac{T}{2}$ 的边。有点新建机场时，只需让它与 $N+1$ 连边，即转化为加边操作，如上述方程转移...

题目描述有一个大小为 $n$ 的环，要求给环上每个节点染色为 $1 \sim k$ 中的某种颜色，使得任意两个相邻的节点颜色不同，询问染色的方案数。答案对 $10^9+7$ 取模。 数学推导注意到 $n,k\leq10^9$，连数组都开不了，于是我们考虑数学（还有数列大佬嘿嘿嘿）。 定义 $A_n$ 表示染色方案数，如右图： 若 $1,n-1$ 不同色，方案数为 $(k-2)A_{n-1}$ 若 $1,n-1$ 同色，方案数为 $(k-1)A_{n-2}$ $$\therefore A_n=(k-2)A_{n-1}+(k-1)A_{n-2}$$ 考虑到 $A_1=k$ 不满足上式，令 $a_n=A_{n+1},a_1=k(k-1),a_2=k(k-1)(k-2)$，也有： $$a_n=(k-2)a_{n-1}+(k-1)a_{n-2} \ ①$$ 熟悉的待定系数法，仿照斐波那契数列，设 $a_n+\mu a_{n-1}=\lambda (a_{n-1}+\mu a_{n-2})\ ②$ 联立 $①②$...

前情提要本题与这一道或最小生成树思路一样，做完本题可以做这一道巩固一下。 题目大意给你一个连通无向图，求 $1$ 到 $n$ 的简单路径的边权之或的最小值。 思路分析看到路径的最小值，首先想起最短路，用 dijkstra？但立即意识到不太行，并不是一个边权越大它与另个一个值按位或的值就会越大。 接下来以按位或的性质作为突破口。位运算中不同位是相对独立的，我们可以考虑从每一位枚举。 如果答案的第 $i$ 位可以为 $0$，无论后面其它位是多少和都不会超过 $2^{i-1}$。 即若能取 $0$ 则永远比取 $1$ 优。所以我们从高位到低位贪心，尽量让高位不要取 $1$，如果可以取 $0$ 就取 $0$。 注意到数据范围 $0\leq w <2^{30}$，枚举 $0\leq i \leq 30$。什么时候这一位必须要取 $1$ 呢？当只用这一位是 $0$，且前几位满足之前枚举的要求的边无法使 $1$ 与 $n$ 连通时，这一位就只能取 $1$ 了。 举个例子 第一个样例： 当 $i=2$ 时，我们去掉所有第 $3$ 位是 $1$ 的边，发现 $1$->$2$...

看到滑动窗口，很容易想到单调队列，但该做法在本题中时间复杂度达到了 $O(n^2)$，不可取，于是考虑计算每个元素在不同窗口的贡献。 首先，元素在哪些窗口会作为最大值？对于每一个 $i∈[1,n]$ 我们可以用单调栈预计算出左右两边第一个大于他的值，并得到其能向左/右扩展多少步。同时为了避免重复计算贡献，我们使用左闭右开，即： 向左找到最近的一个位置 $j$ 使得 $a_j\geq a_i$ （若不存在则为 $0$），则 $l_i=i-j$ 向右找到最近的一个位置 $j$ 使得 $a_j>a_i$ （若不存在则为 $n+1$），则 $r_i=j-i$ 接下来分类讨论，计算贡献，记 $k$ 为滑动窗口的长度，$x=min(l_i,r_i),y=max(l_i,r_i)$，有： 当 $k∈[1,x]$，对长度为 $k$ 的窗口有贡献的共有 $x$ 个，$ans_k=ans_k+a_i k$ 当 $k∈(x,y]$，对长度为 $k$ 的窗口有贡献的共有 $x$ 个，$ans_k=ans_k+a_i x$...