你好，我是 zbl2012 👋

原题Linkhttps://www.luogu.com.cn/problem/P15395 有点牛的数学题。 题意 求 \sum{i=1}^n \lfloor\sqrt{i}\rfloor Solution 注意到 n\le 10^{18} 发现是数学题。 这里介绍 O1 的做法。 首先将 \lfloor\sqrt{x}\rfloor 拆解。 发现 \lf...

原题Linkhttps://www.luogu.com.cn/problem/ATabc185e 题意 给定字符串 A 和 B ，可以插入，添加和删除。问最少次数。 Solution 一道 DP 裸题。 先设一下状态 设 dp{i,j} 表示串 A 前 i 个字符到串 B 前 j 个字符的最少次数。 看一看每一个 dp{i,j} 可以怎么得到： 如果当前...

原题Linkhttps://www.luogu.com.cn/problem/SP15558 ~~这题只有橙我吃~~ Manacher 至少蓝吧。 题意 给定字符串 s，要把 s 划分成数量最小的回文串，求这个数量。 Solution 这一种划分类问题，通常是 DP。 定义 dpi 表示前 i 个字符的最小划分。 边界就是前 0 个字符的最小划分是 0。注意到要求最小，...

原题Linkhttps://www.luogu.com.cn/problem/P2216 其实算是一道 ds 吧。 题意 有一个 a\times b 的矩阵，要找出一个 n\times n 的矩阵，使其里面的最大值与最小值的差最小，并输出差值。 Solution 发现有最大值问题与最小值问题，考虑二维 ST 表。 令 st{k,i,j} 为以 i,j 为左上角，大小 2^k...

原题Linkhttps://www.luogu.com.cn/problem/ATabc287h 版，不知道为什么评绿。 题意 其实就是一个类全源最短路，求 sx 到 tx 的最小值。 Solution 考虑 Floyd。 众所周知，Floyd 要从大到小枚举每一个节点转折点的 k，而在这个过程中，如果有一组询问的两个端点恰好连通，则说明最大值为当前转折点。 发现是一...

原题Linkhttps://www.luogu.com.cn/problem/SP14543 好玩的题。 题目大意 给定一个长度为 n 的序列，有 Q 个操作。若 op=1，则求 l,r 的区间和，否则将 x 放在序列最前面。 Solution 看到 1\le N,Q\le 10^5，发现根据题意暴力模拟，最坏的时间复杂度是 OQN，明显不可以过。 考虑优化。 发现这...

原题Linkhttps://www.luogu.com.cn/problem/P3472 模拟赛被打爆了。 题意 其实就是一张图其实也可以是一个森林，每一个节点都有一个可删除的目标可能是自己，问最少与最多可以删掉几个点。 思路 先将问题转换为求最小与最大存活人数。 注意到每一个点都有一个想删除的目标，所以可以想到之间的有着连锁的关系。每一个点处理后都会影响整一张图。...

质数筛也是数论中非常重要的一个部分。 根号筛 这个是很多人第一个学的筛法，也是最简单的筛法。 做法很简单，就是枚举 2 到 n-1 里所有的数，如果当前数可以被 n 整除，那么 n 显然就是一个和数。直到跑完循环也没返回，就说明 n 是一个指数。当然，n<2 要特判，n=2 也要特判。这样做每次判断一个数的时间复杂度是 On，判断 n 个数的时间复杂度是 On^2。太慢了，要优化。 ...

从 1,2,3,...,n 中选择 m 个数的方案数，记为 \dbinom{n}{m}，也可记为 C^mn。读作 “n 取 m”。\dbinom{n}{m}=\frac{n!}{m!n-m!} On^2 引理：在杨辉三角中的第 n 行 m 列等于 \dbinom{n}{m}。 根据这个引理，我们可以用构造杨辉三角的形式构造组合数。 杨辉三角的构造很简单，就是当前位等于上面的加左上的，也就...

逆元的诞生是源于除法没有同余定理。 逆元的定义：在模意义下，一个数 a 除以 b，等于乘 b 的逆元。 首先我们要知道什么是同余定理。其实就是针对取模的运算的基本原理： 当 a\equiv b\pmod m,c\equiv d\pmod m,m>0 时： a+c\equiv b+d\pmod m\\a-c\equiv b-d\pmod m\\ac\equiv bd\pmod m ...