myblog-Ruochen

摘要： 按照过题顺序总结。 再也不写线段树了。 F - 斐波那契数列 tag：小数高精度，快速幂，矩阵。 讲一讲怎么得来的矩阵。 正所谓矩阵乘法是第一个矩阵的行乘第二个矩阵的列，写成柿子就是（方阵的乘法） \[\sum_{k=1}^{n} C_i,_j = A_i,_k \times B_k,_j \]则如 阅读全文

摘要： 罚时吃饱了。 20260625 A：Floyd 没有初始化 \(0\) 号点。 20260625 C： 罚时一：如果不连通就不用增加答案。 罚时二：没改过来。 20260625 E： 罚时一：一开始用的 Dijkstra，似乎是写挂了。 罚时二：太顽固了，还在写 Dijkstra。 20260625 阅读全文

摘要： 概念补充 非严格次小值：最小值和次小值可以一样长。 严格最小值：最小值和次小值不可以一样长。 非严格次短路：一张图中非严格次小的路径。 严格次短路：一张图中严格次小的路径。 单元次短路求解方法 方法一：魔改 Dijkstra 用两个距离数组，分别记录最短路和次短路。 当最短路可以更新时，那么次短路就 阅读全文

摘要： 笑点分析：每道题都有人过，但是没人 AK。 真的很简单嘛？上次简单树上问题还是在上次吧！ 我竟然能在 18min A 掉蓝？水蓝吧。 同 RMX，J 题 1500 是思维，300 是数据结构，还有 200 被吃掉了，非常细丝鼻孔。 该过题顺序总结。 trick 总结： 一颗子树的 dfn 是连续的。 阅读全文

摘要： A - Maximum Increase 题意：给定一个 \(n\) 个整数组成的数组，找到给定数组中最长的递增子数组的长度。 Tag：DP，线段树，模拟。 象征性的写个 DP。 思路：设 \(dp_i\) 表示以 \(i\) 结尾的长度，显然，如果 \(a_i > a_{i-1}\)，就一定可以 阅读全文

摘要： 一. 区间 dp 概念：区间类动态规划是线性动态规划的扩展，它在分阶段地划分问题时，与阶段中元素出现的顺序和由前一阶段的哪些元素合并而来有很大的关系。 性质： 合并：即将两个或多个部分进行整合，当然也可以反过来； 特征：能将问题分解为能两两合并的形式； 求解：对整个问题设最优值，枚举合并点，将问题分 阅读全文

摘要： \(20pts\)：\(m = 1\) 因为只要选一条，所以直接选直径即可。 \(40pts\)：\(b_i = a_i + 1\) 链的情况直接二分答案即可。 \(55pts\)：\(a_i = 1\) 菊花的情况只有两种： 单独一条链 和另一条链合并 可以二分长度，搜索时可以用一个 \(mult 阅读全文

摘要： 分数总结 题目 期望分数 实际分数 挂分分数 A - 音乐节拍器 100pts 100pts 0pts B - 连续打卡 100pts 100pts 0pts C - 抓取卡牌 100pts 55pts 45pts D - 子树染色 100pts 100pts 0pts E - 勇闯迷宫 I don 阅读全文

摘要： 一笔画问题 在哥尼斯堡市区，普雷戈利亚河上有 \(7\) 座桥把河中心小岛和河岸连接起来。 当时有人提出了一个问题：一个行者怎样才能不重复、不遗漏地一次走完七座桥？ 当时巨佬欧拉证明了这个问题，所以一笔画问题也称为欧拉路。 欧拉路&欧拉回路 定义 欧拉路是经过图中每条边恰好一次的路径，欧拉回路是经过 阅读全文

摘要： 概念 0-1 背包 有 \(N\) 件物品和一个容量为 \(M\) 的背包。第 \(i\) 件物品的重量是 \(W_i\)，价值是 \(D_i\)。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。 我们设 \(dp_i,_j\) 表示选了前 \(i\) 个，重量为 \(j 阅读全文