MyAlgorithmProblems 算法题库与研究笔记¶
在线阅读 / Website · 研究成果 / Research · 新增成果与网站维护 / Contributing
共 192 道题，按主题排列。每题提供中英文题面与题解、C++17 标准程序、样例，以及可重复生成测试输入的 Python 3 脚本。具有多种解法的题目在题解中说明首选、并列或备用方案及其适用条件。
题目使用与评测说明见评测环境与性能。Grox、Spode 系列的英文题记来源见Spore 题记来源。
192 algorithm problems with Chinese and English statements and editorials, C++17 solutions, and reproducible Python test generators. Research notes include amortized analysis of translation matching in induced grid forests and obstructions to extending such forests to trees.
研究成果 / Research results¶
下表链接到结论摘要、精确假设、证明和复核方法。这里的 n 是网格边长，N 是道路顶点数，m 是移动次数。
The entries below give precise assumptions, result summaries, proofs, and reproducibility instructions. Here n is the board side length, N the number of road vertices, and m the number of moves.
| 问题 / Question | 结论 / Result | 阅读入口 / Start here |
|---|---|---|
| 四邻接网格森林的平移匹配 / Translation matching in four-neighbor grid forests | 候选列表算法的总检查次数 W ≤ (5n−3)N，时间 O(n²+m+nN)，从而 O(n³+m) / Cubic upper bound; matching worst-case lower bound when m ≥ n−1 | 中文 · English |
| 诱导网格森林能否补点扩充成树 / Can an induced grid forest be extended to a tree by adding vertices? | 固定位置、保留全部四邻接边时不一定能；存在 Θ(n) 棵、每棵 Θ(n) 个顶点的两两障碍族 / Counterexamples with linearly many large components | 中文 · English |
| 只允许四个对角方向 / Diagonal-only adjacency and movement | 奇偶拆分保留 W ≤ (5n−3)N 与 O(n³+m)；补树障碍可迁移 / Parity reduction preserves the cubic bounds and tree-extension obstructions | 中文与完整证明 · English with proof |
| 同时允许正交与对角方向 / Eight-neighbor adjacency and movement | 秩四方向词保留原收费证明、W ≤ (5n−3)N 和三次方最坏量级 / Rank-four direction words preserve the exact check bound and cubic worst-case order | 中文与完整证明 · English with proof |
| 四邻接与八邻接均允许路径障碍 / Four- and eight-neighbor forests with blocked edges | 按实际开放边修改算法与交域，仍有 W ≤ (5n−3)N 和 O(n³+m)；附验证报告 / Edge-aware filtering and intersections retain the exact cubic bound, with reproducible evidence | 中文与完整证明 · English with proof |
全部研究材料 / Research directory · 结论与状态索引 / Machine-readable result index · Agent 阅读导航 / Agent reading guide · 引用 / How to cite
题目目录¶
| 主题 | 题目 | 题面 | 题解 |
|---|---|---|---|
| 算术 | 星际订单：加速度 | 中文 · English | 中文 · English |
| 自动机 | 地牢房间的行为等价 | 中文 · English | 中文 · English |
| 位运算 | 动态二进制约束计数 | 中文 · English | 中文 · English |
| 位运算 | 异星工厂：信号网络 | 中文 · English | 中文 · English |
| 组合计数 | 叶子不区分的建树顺序 | 中文 · English | 中文 · English |
| 组合计数 | 二的幂拆分计数 | 中文 · English | 中文 · English |
| 组合计数 | 有限跨度的管道 | 中文 · English | 中文 · English |
| 组合计数 | 多类配对的 DNA 双链计数 | 中文 · English | 中文 · English |
| 组合计数 | Grox的序列一 | 中文 · English | 中文 · English |
| 组合计数 | Grox的序列二 | 中文 · English | 中文 · English |
| 组合计数 | Grox的序列四 | 中文 · English | 中文 · English |
| 组合计数 | Grox的序列五A | 中文 · English | 中文 · English |
| 组合计数 | Grox的序列五B | 中文 · English | 中文 · English |
| 组合计数 | 指定叶子数的建树顺序 | 中文 · English | 中文 · English |
| 组合计数 | 某不科学的单调序列计数 | 中文 · English | 中文 · English |
| 组合计数 | 某不科学的单调序列的首项加权和 | 中文 · English | 中文 · English |
| 组合计数 | 某不科学的多重前缀求和 | 中文 · English | 中文 · English |
| 组合计数 | 按顺序连成树 | 中文 · English | 中文 · English |
| 组合计数 | DNA 双链序列计数 | 中文 · English | 中文 · English |
| 组合计数 | 圣辇船直营菓子工房的补货 | 中文 · English | 中文 · English |
| 组合计数 | 犀牛坦克 | 中文 · English | 中文 · English |
| 组合计数 | 平方和球柱的容量 | 中文 · English | 中文 · English |
| 组合计数 | 平方和球柱 | 中文 · English | 中文 · English |
| 组合计数 | DNA 双链长度区间计数 | 中文 · English | 中文 · English |
| 组合计数 | 子格计数 | 中文 · English | 中文 · English |
| 组合计数 | 没有全黑直线的棋盘 | 中文 · English | 中文 · English |
| 构造 | 交换之后的复原 | 中文 · English | 中文 · English |
| 构造 | 较小权不完美非匹配 | 中文 · English | 中文 · English |
| 数据结构 | 分批更新的矩形最大值 | 中文 · English | 中文 · English |
| 数据结构 | 限长传送带 | 中文 · English | 中文 · English |
| 数据结构 | 土罐的序列 | 中文 · English | 中文 · English |
| 数据结构 | 催化序列 | 中文 · English | 中文 · English |
| 数据结构 | 贸易 | 中文 · English | 中文 · English |
| 数据结构 | 契约召唤 | 中文 · English | 中文 · English |
| 数据结构 | 饼干交换大会 | 中文 · English | 中文 · English |
| 数据结构 | 晶块链表 | 中文 · English | 中文 · English |
| 数据结构 | 可修改序列的单调栈 | 中文 · English | 中文 · English |
| 数据结构 | 这题是你自己出的 | 中文 · English | 中文 · English |
| 数据结构 | 老Y的线段树 | 中文 · English | 中文 · English |
| 数据结构 | 保留形状的二叉搜索树 | 中文 · English | 中文 · English |
| 数据结构 | 格兰之森 | 中文 · English | 中文 · English |
| 数据结构 | 区间中位数 | 中文 · English | 中文 · English |
| 数据结构 | 区间最值 | 中文 · English | 中文 · English |
| 数据结构 | 分批操作的向前弹跳 | 中文 · English | 中文 · English |
| 数据结构 | 直线上的容量运输 | 中文 · English | 中文 · English |
| 数据结构 | 抽奖插件 | 中文 · English | 中文 · English |
| 数据结构 | 最小值加权的区间和 | 中文 · English | 中文 · English |
| 数据结构 | 纳米电脑主机 | 中文 · English | 中文 · English |
| 数据结构 | 心灵突击队 | 中文 · English | 中文 · English |
| 数据结构 | 用多个栈实现队列 | 中文 · English | 中文 · English |
| 数据结构 | 小Y的线段树 | 中文 · English | 中文 · English |
| 数据结构 | 异星工厂：机器人指令平台 | 中文 · English | 中文 · English |
| 数据结构 | 选择后缀元素的排序 | 中文 · English | 中文 · English |
| 数据结构 | 简单合并 | 中文 · English | 中文 · English |
| 数据结构 | 插火把 | 中文 · English | 中文 · English |
| 数据结构 | 真空内爆弹 | 中文 · English | 中文 · English |
| 数据结构 | 变量列表 | 中文 · English | 中文 · English |
| 数据结构 | 端倪发生器 | 中文 · English | 中文 · English |
| 动态规划 | 优选猫咪 | 中文 · English | 中文 · English |
| 动态规划 | 不同顺子的牌组划分 | 中文 · English | 中文 · English |
| 动态规划 | 菁英战斗兵 | 中文 · English | 中文 · English |
| 动态规划 | 有限体力的路线计数 | 中文 · English | 中文 · English |
| 动态规划 | 基因突变 | 中文 · English | 中文 · English |
| 动态规划 | 限量补给的旅程 | 中文 · English | 中文 · English |
| 动态规划 | 种西瓜 3 | 中文 · English | 中文 · English |
| 动态规划 | 最优二叉检索树 | 中文 · English | 中文 · English |
| 动态规划 | 剪羊毛 | 中文 · English | 中文 · English |
| 动态规划 | 牌组前缀的可行划分 | 中文 · English | 中文 · English |
| 动态规划 | 无标号容器分配 | 中文 · English | 中文 · English |
| 动态规划 | 升级工具箱 | 中文 · English | 中文 · English |
| 博弈 | 可修改环上的边权游戏 | 中文 · English | 中文 · English |
| 计算几何 | 游耕者（昼） | 中文 · English | 中文 · English |
| 计算几何 | 游耕者（夜） | 中文 · English | 中文 · English |
| 计算几何 | 星际订单：交集分类 | 中文 · English | 中文 · English |
| 计算几何 | 星际订单：矩形相交 | 中文 · English | 中文 · English |
| 计算几何 | 麦田选址 | 中文 · English | 中文 · English |
| 图论 | 自动接线器 | 中文 · English | 中文 · English |
| 图论 | 转动的字节 | 中文 · English | 中文 · English |
| 图论 | 修桥笑传之坚决不用第一版方案 | 中文 · English | 中文 · English |
| 图论 | 神经突击车 | 中文 · English | 中文 · English |
| 图论 | 超时空军团 | 中文 · English | 中文 · English |
| 图论 | 覆盖所有道路的巡检 | 中文 · English | 中文 · English |
| 图论 | 多棵树中的共同连通集 | 中文 · English | 中文 · English |
| 图论 | 下坡路线计数 | 中文 · English | 中文 · English |
| 图论 | 加密数据包与网络清空 | 中文 · English | 中文 · English |
| 图论 | 滴嘟hia的能指循环 | 中文 · English | 中文 · English |
| 图论 | 拨号关系的补全 | 中文 · English | 中文 · English |
| 图论 | 种西瓜 2 | 中文 · English | 中文 · English |
| 图论 | 种西瓜 | 中文 · English | 中文 · English |
| 图论 | 终点和起点 | 中文 · English | 中文 · English |
| 图论 | 红石计算机 | 中文 · English | 中文 · English |
| 图论 | 两类最短路查询 | 中文 · English | 中文 · English |
| 图论 | 异星工厂：简单火车 | 中文 · English | 中文 · English |
| 图论 | Spode经学院 | 中文 · English | 中文 · English |
| 图论 | 异星工厂：科技树 | 中文 · English | 中文 · English |
| 图论 | 恐怖机器人 | 中文 · English | 中文 · English |
| 图论 | 旅游安排 | 中文 · English | 中文 · English |
| 图论 | 两色徽章 | 中文 · English | 中文 · English |
| 图论 | 白雪公主 | 中文 · English | 中文 · English |
| 图论 | 地狱门 | 中文 · English | 中文 · English |
| 贪心 | 数位合并的最大值与最小值 | 中文 · English | 中文 · English |
| 贪心 | 编辑城镇与模拟币 | 中文 · English | 中文 · English |
| 贪心 | 编辑城镇与模拟币2 | 中文 · English | 中文 · English |
| 贪心 | 编辑城镇与模拟币3 | 中文 · English | 中文 · English |
| 贪心 | 编辑城镇与模拟币4 | 中文 · English | 中文 · English |
| 贪心 | 编辑城镇与模拟币5 | 中文 · English | 中文 · English |
| 贪心 | 树上设备的拆除顺序 | 中文 · English | 中文 · English |
| 交互 | 子串询问恢复排列 | 中文 · English | 中文 · English |
| 线性代数 | Grox的序列六 | 中文 · English | 中文 · English |
| 线性代数 | Grox的序列七 | 中文 · English | 中文 · English |
| 线性代数 | 病毒狙击手 | 中文 · English | 中文 · English |
| 逻辑 | 异星工厂：测试电路板 | 中文 · English | 中文 · English |
| 逻辑 | 识别符号格 | 中文 · English | 中文 · English |
| 逻辑 | 作物解锁条件 | 中文 · English | 中文 · English |
| 数论 | 农务署 | 中文 · English | 中文 · English |
| 数论 | 某不科学的等差等比加权和 | 中文 · English | 中文 · English |
| 数论 | 某不科学的立方盒中的最大公约数累计 | 中文 · English | 中文 · English |
| 数论 | 某不科学的多项式加权几何和的修改 | 中文 · English | 中文 · English |
| 数论 | 装备增幅 | 中文 · English | 中文 · English |
| 数论 | 使徒卢克的密码 | 中文 · English | 中文 · English |
| 数论 | 数据恢复 | 中文 · English | 中文 · English |
| 数论 | 某不科学的下降阶乘与二项式求和 | 中文 · English | 中文 · English |
| 数论 | Grox的序列三 | 中文 · English | 中文 · English |
| 数论 | 猜公因子 | 中文 · English | 中文 · English |
| 数论 | 老yd与并查集 | 中文 · English | 中文 · English |
| 数论 | 某不科学的单调序列的最大公约数之和 | 中文 · English | 中文 · English |
| 数论 | 某不科学的多重等比求和 | 中文 · English | 中文 · English |
| 数论 | 烤墨鱼的置换 | 中文 · English | 中文 · English |
| 数论 | 简单分析 | 中文 · English | 中文 · English |
| 数论 | 简单统计 | 中文 · English | 中文 · English |
| 数论 | 红石钟 | 中文 · English | 中文 · English |
| 优化 | 战斗属性的升级计划 | 中文 · English | 中文 · English |
| 优化 | 世纪轰炸机 | 中文 · English | 中文 · English |
| 优化 | 力场护盾 | 中文 · English | 中文 · English |
| 优化 | 坐地铁 | 中文 · English | 中文 · English |
| 优化 | 乘客需要多运动 | 中文 · English | 中文 · English |
| 优化 | 直线上的服务站 | 中文 · English | 中文 · English |
| 优化 | 时间管理与多人运动 | 中文 · English | 中文 · English |
| 优化 | 红心女王的扑克士兵 | 中文 · English | 中文 · English |
| 优化 | 短板翻盘 | 中文 · English | 中文 · English |
| 语法分析 | 带短路规则的运算器 | 中文 · English | 中文 · English |
| 语法分析 | 整数运算器 | 中文 · English | 中文 · English |
| 排列 | 排列的字典序跳转 | 中文 · English | 中文 · English |
| 概率与期望 | 网格生存概率 | 中文 · English | 中文 · English |
| 概率与期望 | 随机分析：概率 | 中文 · English | 中文 · English |
| 概率与期望 | 随机分析：期望 | 中文 · English | 中文 · English |
| 概率与期望 | 剑与暴击 | 中文 · English | 中文 · English |
| 概率与期望 | 唯一特征的命中期望 | 中文 · English | 中文 · English |
| 递归 | 积木塔 | 中文 · English | 中文 · English |
| 递归 | 分数次幂递推 | 中文 · English | 中文 · English |
| 递归 | 递归训练：最大值 | 中文 · English | 中文 · English |
| 调度 | 共用充电器 | 中文 · English | 中文 · English |
| 搜索 | 花园的点击系数 | 中文 · English | 中文 · English |
| 选择算法 | 生成序列中的预算选择 | 中文 · English | 中文 · English |
| 选择算法 | 最接近中位数的数 | 中文 · English | 中文 · English |
| 模拟 | 字符 X | 中文 · English | 中文 · English |
| 模拟 | 一类四邻接网格图森林的匹配问题 | 中文 · English | 中文 · English |
| 模拟 | 异星工厂：搅拌机 | 中文 · English | 中文 · English |
| 模拟 | 连续内存中的字符串函数 | 中文 · English | 中文 · English |
| 模拟 | 横版场域论 | 中文 · English | 中文 · English |
| 排序 | 地精排序 | 中文 · English | 中文 · English |
| 字符串 | 合成大星星 | 中文 · English | 中文 · English |
| 字符串 | 糖果括号 | 中文 · English | 中文 · English |
| 字符串 | 吃糖果 | 中文 · English | 中文 · English |
| 字符串 | 克隆缸 | 中文 · English | 中文 · English |
| 字符串 | 旋涡数 | 中文 · English | 中文 · English |
| 字符串 | 动态树中的路径独立性 | 中文 · English | 中文 · English |
| 字符串 | 再来一小段 | 中文 · English | 中文 · English |
| 字符串 | 魔法面包 | 中文 · English | 中文 · English |
| 字符串 | 非交叉的1212子序列 | 中文 · English | 中文 · English |
| 字符串 | 纸老虎序列 | 中文 · English | 中文 · English |
| 字符串 | 告示牌识别 | 中文 · English | 中文 · English |
| 字符串 | 疯狂的串串 | 中文 · English | 中文 · English |
| 字符串 | 异星工厂：分拣流水线 | 中文 · English | 中文 · English |
| 树 | 祖先子树的分层统计 | 中文 · English | 中文 · English |
| 树 | 二叉树遍历 | 中文 · English | 中文 · English |
| 树 | 菱形衣架的排列 | 中文 · English | 中文 · English |
| 树 | 动态目录树 | 中文 · English | 中文 · English |
| 树 | 大圣诞树 | 中文 · English | 中文 · English |
| 树 | 庆典计划 | 中文 · English | 中文 · English |
| 树 | 粉碎者 | 中文 · English | 中文 · English |
| 树 | 哈根农场 | 中文 · English | 中文 · English |
| 树 | 无限二叉树上的距离 | 中文 · English | 中文 · English |
| 树 | 字典序最大的树标号 | 中文 · English | 中文 · English |
| 树 | 挖地铁 | 中文 · English | 中文 · English |
| 树 | 护林员 | 中文 · English | 中文 · English |
| 树 | 心灵终结仪 | 中文 · English | 中文 · English |
| 树 | 光棱坦克 | 中文 · English | 中文 · English |
| 树 | 心灵支配树 | 中文 · English | 中文 · English |
| 树 | 香料航线 | 中文 · English | 中文 · English |
| 树 | 砍树 | 中文 · English | 中文 · English |
| 树 | 树上的容限路径 | 中文 · English | 中文 · English |
使用题目文件¶
std.cpp 是标准程序。另有实现时，alternative.cpp 或 alternative-<method>.cpp 及对应双语题解说明它的算法与适用范围；部分取舍方案不满足当前完整数据的时限，题解会明确标注。
先在本机以 C++17 编译程序，再在题目目录执行：
python tests/generate.py --out-dir <输出目录> --std <已编译的标准程序路径>
省略 --std 时只生成输入；--case <用例编号> 可只生成指定用例。编号、参数与固定种子见 tests/plan.json。生成结果和可执行文件可放在题库的 build/ 目录。带特殊评测的题目在题解中说明检查器用法。
参考时限与性能数据见评测环境与性能。部署到其他评测环境时，重新测量标准程序的最慢用例中位耗时，乘以题面标注的倍率（默认 2），再按 0.5 秒向上取整。
在题库根目录运行 python tools/check_statements.py，可检查双语样例、数据分组、数学转义、文档链接与图片引用。