你好，我是 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 模拟赛被打爆了。 题意 其实就是一张图其实也可以是一个森林，每一个节点都有一个可删除的目标可能是自己，问最少与最多可以删掉几个点。 思路 先将问题转换为求最小与最大存活人数。 注意到每一个点都有一个想删除的目标，所以可以想到之间的有着连锁的关系。每一个点处理后都会影响整一张图。...