LeetCode 4003 交替方向的最小路径代价 III - Solution

本题给出 $m \times n$ 网格,每个格子有入口代价和罚金。从 $(0,0)$ 出发,第 $k$ 步移动方向由 $k$ 的奇偶性决定(奇数步只能右/下,偶数步只能左/上),违反规则或原地等待需支付罚金。分析指出朴素 DFS 因方向奇偶交替导致搜索空间巨大,进而将「位置 + 步数奇偶性」纳入状态,转化为 $2mn$ 个节点的隐式图,每条合法移动(含等待)建有权边,跑 Dijkstra 即可求解。文章详细推导了状态设计、转移规则,给出了 C++ 参考实现,并总结了 vis 标记时机、罚金归属、整数溢出等避坑要点。

题解

LeetCode 3518 最小回文排列 II - Solution

利用康托展开 + 可重集排列计数,在 O(n·26·log n) 内求回文串所有不同排列按字典序排序后的第 k 个,通过剪枝提前判断无解情况。

题解

【组合数学】康托展开 学习笔记

介绍康托展开与逆康托展开的原理、公式推导和代码实现,涵盖排列排名计算、第 k 个排列生成,以及配合树状数组优化的 O(n log n) 解法。

学习笔记

代码模板-康托展开

康托展开与逆康托展开代码模板,用树状数组维护未使用数的排名,O(n log n) 求排列字典序排名或还原第 k 个排列。

代码模板

Codeforces 670C Cinema - Solution

每个人有一种语言,每部电影有语音与字幕两种语言,选择「语音听懂人数最多、并列时字幕听懂人数最多」的电影。先离散化语言编号,用数组统计各语言人数后线性比较,O(n+m) 解决。

题解

洛谷 P1955 程序自动分析 - Solution

NOI 2015 约束满足问题,利用并查集维护相等关系的传递性,离散化压缩变量编号后判定不等约束是否冲突,时间复杂度 O(n α(n))。

题解

AtCoder ABC468 E - Sum of Average - Solution

给定序列,求所有连续子段平均值的总和。把「子段和 ÷ 长度」按每个元素的贡献拆分,转化为带模逆元的系数求和,O(n) 一次扫描即可统计全部子段。

题解

LeetCode 4002 统计有效序列数目 - Solution

统计满足给定约束的有效序列数目。按位置依赖关系逐位确定取值,配合组合计数与贪心构造,一次线性扫描完成计数。

题解

从 Obsidian 到 Hexo:本博客网站搭建复盘

记录从零搭建 Hexo + Stellar 博客的完整过程,涵盖三次架构迭代、Obsidian 双链渲染、KaTeX 公式、favicon 配置、busuanzi 访问统计等踩坑经验与最终落地方案。

建站笔记

洛谷 P14361 社团招新 - Solution

CSP-S 反悔贪心题:按「当前选择收益」排序后贪心选取,若后续出现更优解则用堆回退之前的决策,修正为全局最优,时间复杂度 O(n log n)。

题解
1234

本站由 zaochen 使用 Stellar 2.0.0 主题创建。
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议,转载请注明出处。
全站访问量 - 次 · 访客数 - 人 · 本页面浏览 - 次

站内搜索

没有找到内容!