yyx的个人主页

欢迎来到 yyx 的个人博客在这里你可以访问博主自制的游戏资源及算法资源祝你访问愉快！！

状压 DP一、原理介绍状态压缩动态规划（状压 DP） 是一种将集合或状态用二进制位进行压缩表示的动态规划方法。它适用于 维度较小（通常 n≤20）但需要记录多个元素“选/不选”或“存在/不存在”等信息的组合优化问题。 通过将每个元素映射到一个二进制位，可以用一个整数表示一个子集或状态，从而在 DP 中进行高效的转移。 常用位运算操作 操作 代码 含义 将第 $i$ 位设为 1 mask | (1 << i) 选中元素 i 将...

线段树原理介绍线段树 是一种基于分治思想的二叉树数据结构，用于高效处理区间修改和区间查询问题。它将一个长度为 $n$ 的数组划分为若干个线段，每个节点代表一段区间的聚合信息（如和、最值等）。 核心思想 建树(build)：将整个数组递归地一分为二，直到每个叶子节点只包含一个元素。每个节点的值由其左右子节点合并得到。 懒标记的pushup和pushdown：当一次区间修改完全覆盖某个节点时，不继续向下更新子节点，而是打上一个”懒标记”，等将来需要访问其子节点时再下传（pu...

残梦孤域——当你坠入破碎的梦境，每一层都是心灵深处未被照见的角落。 “他最近总是在做梦。”一模一样的走廊，永远找不到出口的迷宫；熟悉到令人发指的家，却藏着说不清的违和感；无数条岔路在面前铺展，每一声脚步都牵扯着不同的记忆碎片……这不是偶然的幻象，而是一座精心构筑的 “孤域”——由残破梦境拼凑而成的心理迷宫。 🌀 第一层梦境：无尽迷宫只有真正理解迷宫逻辑的人，才能推开那扇通往更深层意识的门。 🪞 第二层梦境：孪生之屋你回到了“家”。一切陈设都和记忆中一样——却...

最小生成树（Kruskal 算法）原理介绍最小生成树：在一个带权无向连通图中，找到一棵连接所有顶点的树，使得边的权值之和最小。 Kruskal 算法核心思想Kruskal 算法基于贪心策略，按照边权从小到大依次选择边，若该边连接的两个顶点尚未连通（即加入后不会形成环），则将其加入生成树，直到选出 n-1 条边为止。 算法步骤： 将所有边按权值从小到大排序。 初始化并查集，每个顶点各自为一个集合。 遍历排序后的边： 若边的两个端点不在同一集合，则加入生成树，并合并两个集...

KMP 字符串匹配算法原理介绍KMP 算法是一种高效的字符串匹配算法，其核心思想是利用已经匹配过的部分避免主串指针回溯，将时间复杂度由朴素匹配的 O(n*m) 降至 O(n+m)。 next 数组的定义next[i] 表示模式串 P[0 ... i] 这个子串中，最长的相等前缀和后缀的长度（前缀不能为整个子串）。 例如：P = "ababc" next[0] = 0（单字符无真前后缀） next[1] = 0（”ab” 无相等前后缀） next...

最近公共祖先 LCA（倍增法）原理介绍最近公共祖先 问题：在一棵有根树中，求两个节点 u 和 v 的公共祖先中深度最深的那个节点。 倍增法 是解决 LCA 问题的高效在线算法，时间复杂度 O(n log n) 预处理，O(log n) 单次查询。 核心思想 预处理深度：DFS 计算每个节点的深度 dep[u] 和直接父节点 p[0][u]。 倍增祖先：令 p[k][u] 表示节点 u 向上走 2^k 步到达的祖先。状态转移：p[k][u] = p[k-1][ p[k-1...

二分法原理介绍二分法是一种在有序序列中快速定位元素的高效算法，时间复杂度为 O(log n)。 常规二分查找可以回答“某个值是否存在”，但更多时候我们需要知道第一个大于等于 target 的位置或第一个大于 target 的位置，这就是 STL 中 lower_bound 和 upper_bound 的功能。 lower_bound(begin, end, target)：返回第一个 >= target 的元素的迭代器。 upper_bound(begin, e...

前缀和与差分原理介绍一维前缀和前缀和是一种预处理技巧，可以 O(1) 时间查询任意区间的和。 定义原数组 a[1..n]，前缀和数组 s[i] = a[1] + a[2] + ... + a[i]。查询区间 [l, r] 的和：sum(l, r) = s[r] - s[l-1]。 一维差分差分是前缀和的逆运算，可以 O(1) 时间对区间进行批量加减，最后通过一次前缀和还原结果数组。 定义差分数组 d，使得 a[i] = d[1] + d[2] + ... + d[i]。...