二分水位线 —— 最小差值平方和
二分水位线 —— 最小差值平方和 核心思想：当操作次数 k 大到无法逐步模拟时，不去模拟每一次操作，而是二分出所有元素最终被削到的那个”水位线” x，再用剩余次数做微调。 适用信号：贪心策略显然（每次削最大的），但 k 是 1e9 量级 → 把「逐步模拟」换成「二分终点」。 一、题目与关键转化2333. 最小差值平方和 给定 nums1、nums2（长度均为 n）和 k1、k2。可以把 nums1 中任意元素 ±1 至多 k1 次，nums2 同理至多 k2 次，求最小的差值平方和 Σ (nums1[i] - nums2[i])²。 转化 1：k1 和 k2 完全等价设 d[i] = |nums1[i] - nums2[i]|。想把这个差值减 1，有两种走法： 手段 操作 消耗 动 nums1 nums1[i] 朝 nums2[i] 靠一步 k1 减 1 动 nums2 nums2[i] 朝 nums1[i] 靠一步 k2 减 1 两条路对 d[i] 的效果一模一样（都是 d[i] -= 1），所以两个预算可以合并： k = k1 + k2 转化...
分治与主定理 —— a、b、d 与 f(n) 的取法
分治与主定理 —— a、b、d 与 f(n) 的取法 课程：算法设计与分析 · 分治日期：2026-09-16 一、分治三步 步骤 做什么 分（Divide） 把原问题拆成若干规模更小、形式相同的子问题 治（Conquer） 递归求解子问题；规模足够小时直接求解（递归出口） 合（Combine） 把子问题的解合并成原问题的解 核心前提：子问题相互独立（不重叠）+ 合并代价可接受。 递推式的建立T(n) = a · T(n/b) + f(n) 符号 含义 计算 a 本层递归调用了几次 数代码里出现几次递归调用 b 规模缩小的倍数 子问题规模是 n/2 → b = 2；是 n/3 → b = 3 f(n) 本层「分」+「合」的代价 只算本层，不含递归调用 二、f(n) 怎么取：O(1) 还是 O(n)？d 就是本层开销关于 n 的幂次 本层开销 f(n) 幂次 d 典型场景 O(1) d = 0 取中点、比较一次、访问一个节点、移动一个盘子 O(n) d = 1 把 n 个元素过一遍（merge /...
交换后字典序最小 —— 排序分组重分配
交换后字典序最小数组 —— 排序分组重分配 日期: 2026-08-28 难度: 中等 标签: 排序、分组（连通块）、贪心、字典序 题目链接: [2948. 交换后的字典序最小数组] 题目描述正整数数组 nums 和正整数 limit。每次操作可选任意两个下标 i、j，若 |nums[i] - nums[j]| ≤ limit 则可交换这两个元素。返回执行任意次操作后能得到的字典序最小数组。 示例：nums = [1,5,3,9,8], limit = 2 → [1,3,5,8,9] 提示：n ≤ 10^5，nums[i] ≤ 10^9 第一次思路逐位贪心：先排序得到 temp，从前往后扫描，希望每一位都放尽可能小的数： 若 temp[i] == nums[i] 跳过 若 |temp[i] - nums[i]| ≤ limit 直接交换 否则尝试间接交换：找 j > i 使 |temp[j] - nums[i]| ≤ limit 且 |temp[i] - temp[j]| ≤ limit，先换 temp[j] 和 nums[i]，再换 temp[i] 和...
回文排列字典序 —— 枚举首个严格更大位置
回文排列字典序 —— 枚举首个严格更大位置 日期: 2026-08-28 难度: 中等偏难 标签: 贪心、字典序、回文、枚举 题目链接：[3734. 大于目标字符串的最小字典序回文排列] 题目描述给定字符串 s 和目标串 target（长度均为 n），返回字典序最小的字符串，它既是 s 的一个回文排列，又是字典序严格大于 target。不存在则返回空串。 示例：s = "baba", target = "abba" → "baab"（”abba” 等于 target 不算，下一个是 “baab”） 提示：n ≤ 300，小写字母 第一次思路第一反应是逐位贪心：构造回文的前半部分，每一位选”刚好大于等于 target[i]”的最小可用字符。 // 第一版：逐位贪心 >=（卡住）string temp = "";for (int i = 0; i < n / 2; i++) { char tc = target[i]; char rc =...
全体异或判零 —— 最长非零异或子序列
全体异或判零 —— 最长非零异或子序列 日期: 2026-08-15 难度: Medium 标签: 位运算、子序列、数学 题目链接：[3702. 按位异或非零的最长子序列] 题目描述给定数组 nums，返回按位异或结果非零的最长子序列的长度。不存在则返回 0。 示例 1：[1,2,3] → 2（2 ^ 3 = 1） 示例 2：[2,3,4] → 3（2 ^ 3 ^ 4 = 5） 第一次思路第一反应是贪心：从头到尾累加异或，只要当前异或非零就更新答案长度。 class Solution {public: int longestSubsequence(vector<int>& nums) { int n = nums.size(); int res = 0; int temp = nums[0]; for (int i = 1; i < n; ++i) { temp ^= nums[i]; if (temp...
相邻差分组 —— 排序数组连通分量
相邻差分组 —— 排序数组连通分量 日期: 2026-07-09难度: Medium标签: 排序、连通性、分组题目链接: 3532. 针对图的路径存在性查询 I 题目描述有 n 个节点，每个节点 i 有权值 nums[i]（数组已排序）。若 |nums[i] - nums[j]| <= maxDiff，则 i 和 j 之间有无向边。此外，给你一个二维整数数组 queries。对于每个 queries[i] = [ui, vi]，需要判断节点 ui 和 vi 之间是否存在路径。 第一次思路暴力建图 O(n²) → 超时 第一反应是两层循环检查每一对节点，满足条件就加边，然后每次查询 BFS 判连通。建图就是 O(n²)，n 最大 1e5，不出意外的超时。 vector<vector<int>> edge(n);for (int i = 0; i < nums.size(); i++) { for (int j = i + 1; j < nums.size(); j++) { if...
多源BFS与二分答案 —— 最大安全系数路径
多源BFS + 二分答案 —— 最大安全系数路径 日期: 2026-07-1难度: Medium标签: 多源BFS、二分答案、连通性题目链接: 2812. 找出最安全路径 题目简述给定一个 n×n 的 01 矩阵，1 表示小偷，0 表示空。路径的安全系数定义为路径上所有点到任一小偷的最小曼哈顿距离。求从 (0,0) 到 (n-1,n-1) 的所有路径中，安全系数的最大值。 第一次思路读完题首先想到两个方向： 需要算每个格子的安全距离 然后要找一个最大安全系数。 但是有三个地方卡住了： 多源BFS —— 多个小偷怎么一次算完？第一反应是对每个小偷单独 BFS，然后再对每个格子取 min。这显然太慢——小偷数量可能很多，每次 BFS 都是 O(n²)，总复杂度不行。正确做法应该是是多源 BFS：把所有小偷一次性全部入队，BFS 同时从所有源点向外扩散，第一个到达某格子的就是最近的小偷。这和「铺瓷砖」一个原理，同时从所有源头铺，每个格子被铺到的时间就是最短距离。 “消除”不安全的格子 —— 要新建数组吗？提示说「消除所有满足 d[x][y] < v...
3699.锯齿形数组总数
3699. 锯齿形数组的总数 I原题链接 题目信息 难度：算术评级 8（偏难） 标签：动态规划、前缀和、后缀和、滚动数组 第 469 场周赛 Q3 题目理解给定 n、l、r，求长度为 n 的锯齿形数组总数。锯齿形数组需要满足： 每个元素取值 [l, r] 相邻元素不等 任意连续三个不能严格递增或严格递减 条件 3 意味着序列的方向必须交替：上升后必须下降，下降后必须上升。这就是经典 zigzag 序列。 思考过程第一版：暴力 DP（超时 + 超内存）最直觉的想法：用 dp[i][dir][x] 表示长度为 i、以 x 结尾、下一步方向为 dir 的序列数。 dir = 0 → 下一步需要下降（刚刚上升过） dir = 1 → 下一步需要上升（刚刚下降过） 初始化长度为 2 的所有情况（相邻不等即可），然后三重循环向后转移： for (int x = 0; x < range; x++) { for (int y = 0; y < range; y++) { if (x != y) { ...
频率统计与平方扩展 —— 对称子集构造
频率统计 + 平方扩展 —— 对称子集构造 日期: 2026-06-27难度: Medium标签: 哈希表、贪心、数学题目链接: 3020. 子集中元素的最大数量 题目描述给一个正整数数组，选一个子集使其元素能排成 [x, x², x⁴, ..., x^k, ..., x⁴, x², x] 的对称模式，求子集的最大元素数量。 第一次思路第一眼看到提示说用 HashSet，但马上就发现不对——HashSet 去重之后丢掉了每个数出现几次的信息，而这个模式里除了中间元素出现 1 次，其他每个数都需要 2 次（左右对称各一个），所以必须用频率表。 另一个直觉是枚举所有可能的序列长度检查是否能构造，但显然不可行。 最终方案真正的突破来自两个观察： 平方增长极快——1e9 以内最多平方 5 次就到顶，所以每个起点最多扩展几步就结束了，总复杂度很安全。 对称性决定了构造方式——从最小值 x 向中间贪心扩展，每次消耗 2 个当前值，直到遇到只有 1 个的数作为中心，或到底后回退一步。 算法流程 统计频率表 freq 数字 1 单独处理：1 的平方还是 1，所以全 1 序列长度就是 1...
单调性贪心 —— 游乐设施调度
单调性贪心 —— 游乐设施调度 题目链接: Q1 / Q2日期: 2026-06-01难度: Medium标签: 贪心、单调性 题目描述两类游乐设施（陆地、水上），每类各选一个，顺序不限。每个设施有开始时间和持续时间。完成后可以立即开始下一个（如果已开放）或等待。问最早完成时间。 第一次思路（暴力 O(nm)）Q1 数据量小（n,m ≤ 100），直接双层循环枚举所有配对： int earliestFinishTime(...) { int res = INT_MAX; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { // 两种顺序分别算 int t1 = max(landEnd[i], waterStart[j]) + waterDuration[j]; // 先陆地后水上 int t2 = max(waterEnd[j], landStart[i]) +...