-
倍增与 RMQ 问题 学习日记
什么是倍增?倍增,从字面及数学的角度就是 ”成倍增长“ 的意思。这能使线性问题转化为数级处理,优化时间复杂度。 不是人话是不是?听不懂是不是? 看这里。这是指我们在进行递推时,如果状态空间很大,通常的线性递推无法满足时间与空间复杂度的要求,那么我们可... -
简单线性 DP 学习日记
DP 概述DP 问题在 OIer 中很受欢迎,因为每个 DP 问题在某种意义上都是原创的,你必须思考其状态和状态转移方程才能为其发明解决方案。 DP,是一种基于分治,将原问题分解为简单子问题求解复杂问题的方法。 动态规划的耗时往往远少于朴素解法。 动... -
Floyd 算法学习日记
算法用途:Floyd 算法是用于解决两点间最短路径的一种算法,可以处理有向图或负权的最短路问题。 该算法时间复杂度为 ,空间复杂度为 。 算法原理Floyd 算法基于动态规划实现。 Floyd 算法一直在解决一个问题,寻找 的最短路径 (废话)。... -
题解:P11000 [蓝桥杯 2024 省 Python B] 数字串个数
P11000,纪念这个特别的数字,来水一篇。 用 没有任何特殊情况的方法数:。 排除没有 和 的方法。 加上 和 混一起的方法数。 答案为:。 附:计算过程 -
题解:P5948 [POI2003] Chocolate
一眼贪心,为什么呢? 从题面中我们可以看见纵向切一刀横向就多一刀的代价,所以我们把所有代价混一起排序从大到小切割即可。 (结尾附证明) 注:要开 long long,最坏情况约为:,肯定炸 。 代码如下: 1234567891011121314151... -
题解:P10906 [蓝桥杯 2024 国 B] 合法密码
本来以为字符串多大,结果就这点,直接暴力。 枚举起始点,对于每个起始点枚举后面 位有没有能用的即可。 最后答案为 。 附:计算代码 枚举代码如下: 12345678910for (int i = 0; i < n; ++i) { f... -
题解:P10903 [蓝桥杯 2024 省 C] 商品库存管理
cnblogs食用也行 题目大意有一个初始化为 的 长度为 的序列,现有 个操作,每次将区间 中的数量加 ,求如果不做某个操作将会有多少个数量为 的量。 解题思路通过将区间内所有数量增加这句话我们就能很直接的想到差分。 这题我们可以使用差... -
题解:AT_abc140_e [ABC140E] Second Sum
题解思路:双向链表+组合数学(不过你要用单调栈也没人拦着你) 我们现在先抛开题面,先换个思路。 我们现在求:这个数能做多少个区间的次大值。 我们现在设 分别为左边第一个比这个数大的 id,第二个比这个数大的 id,右边第一个比这个数大的 id,第二... -
题解 P9473 [yLOI2022] 西施江南
以此记录初入洛谷的自己写的题解,虽然没通过。 算法概述本题需使用 map 和数论知识。 题意讲解设 是这些数的最大公约数, 是这些数的最小公倍数;求一组数据中的 是否等于 。 暴力做法(44分)这题大家最容易想到的方法就是将 以及 都算出...