yyx的个人主页

🎂 生日快乐，cc！ 🎉 ✨ 致独一无二的你在这个特别的日子里，我想把全世界的温柔都打包送给你。 遇见一个像你这样合拍、真诚又有趣的人，真的花了很久很久才攒够的运气。 🌈 回忆是闪闪发光的碎片我们曾一起—— 在深夜闲聊，聊那些不切实际的梦想 因为一部烂片笑到岔气，也因为一句歌词红了眼眶 分享生活中的趣事，吐槽各种不快 “世间最美好的事，莫过于有几个头脑和心地都很正直的朋友。”而你就是其中之一。 🌟 关于你，我想说你是那种会 记住别人随口一提的小愿望，然后默默实现的人；一边吐槽“你好幼稚”，一边认认真真陪我玩那些无聊的小游戏的人；也是那种即便看透生活的不易，却依然选择热烈去爱的 勇敢者。 木目在心上，单人在耳旁 🎁 生日愿望清单（我来替你许几个，嘻嘻） 健康平安 —— 这是所有快乐的基础，身体要倍儿棒！ 发财暴富 —— 不求大富大贵，但求买东西不用看价签，奶茶想加什么料加什么料。 被爱包围 —— 亲情、友情、爱情，所有真心都流向你。 永远做自己 —— 不必为谁改变，你本来的样子就足够迷人。 自由如风 —— 去想去的地方，做想做的事，成为想成为的人。 ...

状压 DP一、原理介绍状态压缩动态规划（状压 DP） 是一种将集合或状态用二进制位进行压缩表示的动态规划方法。它适用于 维度较小（通常 n≤20）但需要记录多个元素“选/不选”或“存在/不存在”等信息的组合优化问题。 通过将每个元素映射到一个二进制位，可以用一个整数表示一个子集或状态，从而在 DP 中进行高效的转移。 常用位运算操作 操作 代码 含义 将第 $i$ 位设为 1 mask | (1 << i) 选中元素 i 将第 $i$ 位设为 0 mask & ~(1 << i) 移除元素 i 检查第 $i$ 位是否为 1 mask & (1 << i) 判断元素 i 是否存在 翻转第 $i$ 位 mask ^ (1 << i) 切换元素 i 的状态 检查是否有连续的 1 mask & (mask >> 1) 若结果为 0 则无相邻的 1（常用于棋盘问题） 去掉最低位的 1 mask & (mask - 1) lowbit 操作，常用于枚举...

线段树原理介绍线段树 是一种基于分治思想的二叉树数据结构，用于高效处理区间修改和区间查询问题。它将一个长度为 $n$ 的数组划分为若干个线段，每个节点代表一段区间的聚合信息（如和、最值等）。 核心思想 建树(build)：将整个数组递归地一分为二，直到每个叶子节点只包含一个元素。每个节点的值由其左右子节点合并得到。 懒标记的pushup和pushdown：当一次区间修改完全覆盖某个节点时，不继续向下更新子节点，而是打上一个”懒标记”，等将来需要访问其子节点时再下传（push 操作）。这样可将区间修改的复杂度从 $O(n)$ 降至 $O(\log n)$。 查询：同样递归进行，若当前节点完全在查询区间内，直接返回其存储的值；若与查询区间无交集，直接返回 0；否则继续向下递归并合并左右结果。 时间复杂度 建树：O(n) 单次区间修改/查询：O(\log n) 空间：O(4n)（通常开原数组大小的 4 倍） 适用场景 区间加减、乘除 区间求和、最值、GCD 区间染色、覆盖问题 更复杂的双 lazy 标记（先乘后加等） 以下附上代码： 12345678910111213...

残梦孤域——当你坠入破碎的梦境，每一层都是心灵深处未被照见的角落。 “他最近总是在做梦。”一模一样的走廊，永远找不到出口的迷宫；熟悉到令人发指的家，却藏着说不清的违和感；无数条岔路在面前铺展，每一声脚步都牵扯着不同的记忆碎片……这不是偶然的幻象，而是一座精心构筑的 “孤域”——由残破梦境拼凑而成的心理迷宫。 🌀 第一层梦境：无尽迷宫只有真正理解迷宫逻辑的人，才能推开那扇通往更深层意识的门。 🪞 第二层梦境：孪生之屋你回到了“家”。一切陈设都和记忆中一样——却处处透着异样。这是一场紧张诡谲的 找不同 挑战：找出每一个差异，揭开那段被刻意掩埋的往事。 🪢 第三层梦境：岔路选择梦境的背面是一条铺满分岔的小径，每一条都通往不同版本的结局。没有小地图，没有回头路。你将在有限的信息中做出抉择，你的选择不仅决定剧情的走向，更将剖开主角内心深处不同的创伤与渴望。多条剧情线、多重结局，拼凑出完整的“残梦”。 《残梦孤域》 是一款融合探索、解谜与叙事选择的心理梦境游戏。在这里，你或许能感受到不同层次的梦境体验。 梦在等你醒来，或更深地迷失。 🔗 下载资源体验，一同坠入残梦。 下...

最小生成树（Kruskal 算法）原理介绍最小生成树：在一个带权无向连通图中，找到一棵连接所有顶点的树，使得边的权值之和最小。 Kruskal 算法核心思想Kruskal 算法基于贪心策略，按照边权从小到大依次选择边，若该边连接的两个顶点尚未连通（即加入后不会形成环），则将其加入生成树，直到选出 n-1 条边为止。 算法步骤： 将所有边按权值从小到大排序。 初始化并查集，每个顶点各自为一个集合。 遍历排序后的边： 若边的两个端点不在同一集合，则加入生成树，并合并两个集合。 若已在同一集合，则跳过（避免成环）。 若最终选出的边数等于 n-1，则成功构建最小生成树；否则图不连通，不存在生成树。 时间复杂度：排序 O(m log m)，并查集操作近似 O(m α(n))，总复杂度约为 O(m log m)。 与 Prim 算法的对比： Kruskal 适合稀疏图（边少），因为主要操作是排序。 Prim 适合稠密图（边多），可用堆优化至 O((n+m) log n)。 以下附上代码: 1234567891011121314151617181920212223242526272...

KMP 字符串匹配算法原理介绍KMP 算法是一种高效的字符串匹配算法，其核心思想是利用已经匹配过的部分避免主串指针回溯，将时间复杂度由朴素匹配的 O(n*m) 降至 O(n+m)。 next 数组的定义next[i] 表示模式串 P[0 ... i] 这个子串中，最长的相等前缀和后缀的长度（前缀不能为整个子串）。 例如：P = "ababc" next[0] = 0（单字符无真前后缀） next[1] = 0（”ab” 无相等前后缀） next[2] = 1（”aba” 前缀 “a”，后缀 “a”） next[3] = 2（”abab” 前缀 “ab”，后缀 “ab”） next[4] = 0（”ababc” 无相等前后缀） 当匹配失败时，next[i-1] 告诉我们可以跳过多少个字符继续匹配，避免主串指针回退。 算法流程 构建 next 数组通过双指针 i（后缀末尾）和 j（前缀长度）遍历模式串，若不匹配，j 回退到 next[j-1]。 匹配过程主串指针 i 和模式串指针 k 依次比较，失配时 k 回退到 next[k-1]，匹配成功时记录起始位置...

最近公共祖先 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][u] ]（先向上走 2^(k-1) 步到 pp，再从 pp 向上走 2^(k-1) 步） 查询 LCA： 先将较深的节点上提到与另一节点同深度，使用二进制拆分。 若此时两节点相同，直接返回。 否则从大到小尝试同时向上跳，保持两者不相遇，最终它们的父节点就是 LCA。 算法复杂度 预处理：O(n log n) 单次查询：O(log n) 空间：O(n log n)（存储 p[k][u] 数组） 以下附上代码: 123456789101112131415161718192021222324252627282...

二分法原理介绍二分法是一种在有序序列中快速定位元素的高效算法，时间复杂度为 O(log n)。 常规二分查找可以回答“某个值是否存在”，但更多时候我们需要知道第一个大于等于 target 的位置或第一个大于 target 的位置，这就是 STL 中 lower_bound 和 upper_bound 的功能。 lower_bound(begin, end, target)：返回第一个 >= target 的元素的迭代器。 upper_bound(begin, end, target)：返回第一个 > target 的元素的迭代器。 二分法中最关键的一步就是check()函数的编写，能写出check函数剩下的套模版就行了。 以下附上代码: bool check(ll mid) { return mid > target; // 条件：当前 mid 值大于目标值 } ll l = 1, r = n; // 假设答案的左右边界 while (l <= r) { ll mid = (l + r) / 2; if ...

前缀和与差分原理介绍一维前缀和前缀和是一种预处理技巧，可以 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]。若要对区间 [l, r] 每个元素加 x，只需： 12d[l] += x;d[r+1] -= x; 二维前缀和在矩阵中快速求子矩阵和。 定义 s[i][j] 为原矩阵 a 从 (1,1) 到 (i,j) 的子矩阵元素和。递推公式: 1s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j] 查询以 (x1, y1) 为左上角，(x2, y2) 为右下角的子矩阵和: 1sum = s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[...

快速幂算法原理介绍快速幂是一种高效计算 大整数幂取模 的算法。朴素计算 base^exp 的时间复杂度为 O(exp)，当指数极大时（例如 exp=10^9）会严重超时。快速幂利用 分治 思想，将时间复杂度降为 O(log exp)。 核心思想根据指数的奇偶性进行二分递推： 若 exp 为偶数：base^exp = (base^2)^(exp/2) 若 exp 为奇数：base^exp = base × (base^2)^((exp-1)/2) 每次将指数减半，底数平方，从而将线性次数的乘法降为对数次。 取模运算在实际应用中，幂的结果往往大到无法存储，因此通常结合 模运算 进行。模运算满足：(a × b) % mod = [(a % mod) × (b % mod)] % mod，可以在每一步乘法后立即取模，防止溢出。 以下附上代码： typedef long long ll; // 快速幂：计算 (base^exp) % mod ll qpow(ll base, ll exp, ll mod) { ll res = 1; base %= mod;...