myblog-Ruochen

摘要： 生成树 生成树，就是在一个无向连通图中选择 \(n - 1\) 条边，使得这 \(n-1\) 条边构成了一棵树。 最小生成树 假设每一条边有边权，边权和最小的生成树就是最小生成树（MST）。 求法 1. Prim 这是一个点核心的算法。 每次选择点权最小的点，在扩展到邻居节点，这和 dijkstra 阅读全文

摘要： 树上启发式合并总结 概念 树上启发式合并，俗称 DSU on tree，是一种离线处理子树内的一种方法，时间复杂度大约为 \(O(n\log_2n)\)。 一般用于树上数颜色问题。 DSU 其实是并查集的英文缩写，那么这个是树上并查集吗？不对，这一个算法是基于并查集的启发式合并，也就是把小的集合并到 阅读全文

摘要： 20251206 - 并查集总结 如果要求出两个东西是否在集合里，怎么办？ 把它存在图里，再离线处理。 Tarjan 巨佬提出了并查集。 查找 如果要判断两个人是否是同一个省的人，可以问问你们的代表人物是谁？ 如果相同，就是同一个省的。 所以，记录每一个元素的父亲，再每次向上找即可。 递归版： in 阅读全文

摘要： 20251201 - 换根dp总结 换根 dp，就是先预处理出一些信息，然后再转移。 一般的可以先考虑子树内的答案，在扩展到字树外。 扩展到字树外可以先考虑根节点到他的子节点的转移，在扩展到其他的点。 例题 P1395 会议 这道题可以先求出以 1 号点为根的子树的大小，那么子树外的大小就是 n - 阅读全文

摘要： 20251124 - 月度检测 总结 题号 实际分数 应得分数 罚时 A AC AC 0 B AC AC 0 C AC AC 0 D WA AC null E AC AC -2 F null AC null G null null/AC null H null null null 后面不用看了！ n 阅读全文

摘要： 树的基本概念 树是一种典型的非线性数据结构，是一种特殊的图，最大的特点就是没有环，所以他有许多良好的性质（比如可以 dp）。更绝的是，考的题目一般都很难！ 树的直径 树的直径是指树中任意两点间的最长距离。 如何求出直径 方法零： 枚举每一个点，记录每一个点到其他点的距离，再求最大值。 时间复杂度：\ 阅读全文

摘要： 前言 怎么又有 ABB 啊，连考三次，罚时吃饱了！ Manacher，俗称马拉车，是一个可以线性的求出一个串的最长回文子串。 如何求解最长回文子串呢？ 马拉车 方法零： 首先枚举字符串的左端点和右端点，在判断区间是否是回文串。 时间复杂度：\(O(n^3)\) 空间复杂度：\(O(n)\) bool 阅读全文

摘要： 前言 为什么此次题单不叫字符串 hash 呢？ 应该搞点 [哈希表](P11615 【模板】哈希表 - 洛谷) 的！ 概念 哈希，就像是把一个很大的东西，映射到一个小盒子里，这个盒子就是哈希表。 字符串哈希，顾名思义，就是把很 long 的字符串，映射到很 short 的范围里。: 当然，不保证正确 阅读全文

摘要： 前言 我今天生日！！！ 由来 KMP 算法，是由 Knuth、Pratt 和 Morris 三位巨佬发布的一个算法。 他可以在线性（说人话就是 \(O(n + m)\) ）时间复杂度内在字符串中查找子串。 思想 朴素算法： 枚举每一个元素，然后从这一位开始不断向后比较，每次比较失败之后都要从上一次匹 阅读全文

摘要： 考试情况： Problem T1 T2 T3 T4 all want scores 100pts 100pts 40pts 0pts 240pts scores 100pts 100pts 0pts 0pts 200pts 前言： 今天太难了！！！ T1 出题人的良心馈赠！ 就是一个简单的诈骗贪心和 阅读全文