- 博客(17)
- 收藏
- 关注
RSS订阅原创 【动态规划】5 从一次函数出发推导斜率优化dp
本文通过例题《任务安排》介绍了斜率优化的方法。首先给出动态规划解法，时间复杂度O(n³)。通过费用提前计算的优化，将状态转移方程转化为直线方程形式，利用决策点的几何性质进行优化。重点分析了决策点之间的斜率关系，说明需要维护单调递增的斜率序列，通过单调队列实现O(n)时间复杂度的优化。最终方案通过比较相邻点斜率来维护队列，确保每次取最优决策点。该过程避免了精度问题，通过不等式变形直接比较斜率值。
2025-05-23 22:40:28
954
原创 【数论】5 & Atcoder Beginner Contest383 D题题解
Atcoder Beginner Contest383 D题题解
2024-12-07 22:43:04
871
原创 Atcoder Beginner Contest 374 D题题解
Atcoder Beginner Contest 374 D题题解。本题很考验功底，主要靠暴力求解，但是需要掌握全排列，二进制枚举等技巧，还需要进行转化。总之是一道练习暴力求解的好题。
2024-10-06 09:00:00
970
原创 【图论】1 （最小生成树&虚拟点思想）C.戴森球计划 题解
题解：C.戴森球计划。一道练习最小生成树和虚拟点思想的好题。这道图论题在CSP-J模拟赛放了T3，感觉略难（最小生成树和虚拟点思想略有超纲），但不引进“虚拟点思想”的70分给的很足。总体来说是一道练习最小生成树和虚拟点思想的好题。
2024-10-04 23:00:36
1375
原创 【动态规划】3 Atcoder Beginner Contest369 D题题解
Atcoder Beginner Contest369 D题题解主要用到的是dp优化的思路，当然也有别的优化方法，但是这种思路的时间复杂度显然是比较优的 $O(n)$ ，也可以尝试 $O(n \log n)$ 解决。整体难度【普及/提高-】左右，可能在CSP-J第2.3题或CSP-S第1题。
2024-08-31 22:40:40
1196
原创 【数论】3 洛谷[COCI2016-2017#6] Savrsen题目讲解
洛谷[COCI2016-2017#6] Savrsen题目讲解，是一道数论的题目，考虑优化并结合埃氏筛法进行解决
2024-08-31 10:45:43
939
原创 Atcoder Beginner Contest 367 D题题解
Atcoder Beginner Contest 367 D题题解。这是一道练习暴力优化思想好题，用到了前缀和思想，桶思想，但是都需要加以优化和变形。尤其是整体修改用变量记录的思想，在信息学奥赛中是一种很好的优化方式，但不要忘了对单个值修改时需要减去记录的变量。
2024-08-18 00:31:10
1003
1
原创 【滑动窗口/双指针2】Atcoder Beginner Contest366 E题题解
Atcoder Beginner Contest366 E题题解，讲解一道滑动窗口和双指针的题目，思路清晰，很适合新手阅读。
2024-08-13 00:39:22
1082
2
原创 【数论】2 同余问题（同余方程 中国剩余定理 拓展欧几里得定理等）学习笔记
Tips：本篇博客仅简单介绍同余问题的基本类型以及代码实现，仅供参考了解，以算法用途为主且参考意义较大声明：未完待续······上次修改日期：2024-7-26 14:10 第1版。
2024-07-26 14:07:51
793
原创 【数论】1 矩阵快速幂（斐波那契）
讲述数论中的矩阵快速幂，用来优化递推或动态规划的复杂度，能大大增加程序在一定时间内的处理能力，其中还包含矩阵以及快速幂实现的相关数学内容
2024-07-25 12:55:56
1572
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人