BGN64 硬币凑钱 思路 题目要求：银行有面值为 1 元、5 元、7 元的硬币，每种数量无限，求凑出  元所需的最少硬币数。 这是一道非常经典的完全背包 / 硬币找零问题。 第一反应可能是贪心 —— 尽量多用大面值硬币。但这里贪心是不对的！比如 ，贪心会先用 1 个 7 元，剩下 3 元只能用 3 个 1 元，总共 4 枚。但实际上 2 个 5 元就搞定了，只要 2 枚。 所以我们需要用动态规划。 状态定义 设  表示凑出金额  所需的最少硬币数。 转移方程 对于每个金额 ，我们尝试用每种硬币 ： $$ 初始值 （凑出 0 元不需要硬币），其余初始化为一个很大的值。 举个例子，：  （一个 ...

BGN46 复杂的最大公约数 思路 题目要求：给定两个整数  和 ，输出它们的最大公约数（GCD）。 求最大公约数，最经典的方法是什么？没错，就是辗转相除法（欧几里得算法）。 核心思想其实很简单：，不断地用较大的数对较小的数取模，直到其中一个变成 0，另一个就是答案。 举个例子，：    三步就搞定了，比暴力枚举快多了。 注意数据范围 这道题有个坑点：输入的数可能非常大，超出 int 的范围。C++ 需要用 long long 来存储。 Java 这边稍微麻烦一些 —— 测试数据中甚至出现了超出 long 范围的巨大数字。但观察发现，题目的判定逻辑是按照 C/C++ 的 long long 语...

BGN48 矩形游戏 思路 题目说的是一个石子游戏：起初有  颗石子，每次操作把石子排成  的矩形（），然后只留下一行（ 颗），其余全丢掉。反复操作直到剩 1 颗，把过程中每次的石子数（包括初始的  和最后的 ）加起来，求最大得分。 说白了，每次操作就是把当前数  替换成它的一个真因子 （因为 ，所以 ）。我们要选择一条从  到  的因子链，使得链上所有数的和最大。 该除以谁？ 假设当前是 ，我们要选一个大于 1 的因子  把它除掉，变成 。想让总和尽可能大，那每一步保留的值就要尽可能大 —— 也就是  要尽可能小。 最小能取多少？就是  的最小质因子。 所以最优策略就是：每次都除以当前数的最...

几乎是质数 思路 题目在说什么？给定正整数 ，求区间  中恰好有两个不同质因子的数的个数。比如  有两个不同质因子，是"几乎是质数"； 只有一个质因子，不算； 有三个，也不算。 那怎么高效统计每个数有多少个不同的质因子呢？ 关键观察 暴力对每个数做质因数分解是 ，太慢。换个角度想：与其"对每个数找它的质因子"，不如对每个质数，标记它是谁的因子。 这就是埃氏筛的思路：枚举每个质数 ，把  这些倍数的"不同质因子计数"都加 1。筛完之后，计数恰好为 2 的就是答案。 怎么判断  是质数？如果  还没被任何更小的质数标记过（计数为 0），那...

最大公因数与最小公倍数 思路 给两个正整数，求它们的最大公因数（GCD）和最小公倍数（LCM）。 最大公因数 用欧几里得算法（辗转相除法）：，当  时 。 最小公倍数 有公式：。 为了防止溢出，先除再乘：a / gcd * b。 代码    C++   Java   Python3   JavaScript   #include <iostream> using namespace std; int main() { long long a, b; cin >> a >> b; long long x = a, y = b; while (y) { long...

BGN83 完美异或 思路 题目要求构造一个长度为  的非递减数组，使得所有元素的异或和是  的因子。如果无法构造就输出 -1。 先想想，有没有什么万能的构造方法？ 关键观察 我们可以用大量的 1 来"填充"数组，然后在末尾放一个较大的数来调整异或和。 具体来说：前  个元素都是 1，最后一个元素设为 。数组自然是非递减的（只要 ）。 那异或和是多少呢？ 个 1 异或在一起：  如果  是偶数（即  是奇数）：异或和为 0，总异或和就是  如果  是奇数（即  是偶数）：异或和为 1，总异或和就是   分情况构造  为奇数时： 前面  个 1 异或得 0，令 ，总异或和 ，...

BGN41 判断质数 思路 题目很直白：给你一个正整数 ，判断它是不是质数，是的话输出 Yes，否则输出 No。 那什么是质数？大于 1 的整数，且只能被 1 和自身整除。 怎么判断呢？最朴素的方法是从 2 遍历到 ，看有没有能整除  的数。但这样太慢了，有没有更快的办法？ 试除法优化 关键观察：如果  有一个因子 （），那  也是  的因子。 和  这两个因子，至少有一个 。 所以我们只需要从 2 枚举到  就够了。如果在这个范围内没有找到任何因子， 就是质数。 注意数据范围 这道题有个小坑：输入数据可能超过 int 的范围（测试用例中出现了 274876858367 这样的大数）。所以 C...

BGN27 谐距下标对 思路 先想一个问题：什么叫"谐距"？题目说的是下标 ，满足 ，也就是两个元素的"值的差"恰好等于"下标的差"。你可以理解成：如果把数组画在坐标系上，这两个点刚好在同一条斜率为 1 的直线上。 那怎么找这样的下标对呢？暴力枚举所有  肯定能做，但  在数据量大的时候就扛不住了。 关键转化 把条件  移项一下： $$ 发现了吗？只要定义 ，那问题就变成了：数组  中有多少对相等的元素？ 这就是经典的"计数相同元素对数"问题了。用哈希表统计每个值出现的次数 ，每个值贡献  对，加起来就是答案。 举...

BGN77 构造数列 思路 这题让你构造一个长度为  的数组，前一半是互不相同的偶数，后一半是互不相同的奇数，且两半的和相等。 先想一个关键问题：前半部分的和与后半部分的和，奇偶性能对上吗？ 取最小的  个偶数和奇数来分析：   个偶数的和一定是偶数（偶数之和必为偶数）  个奇数的和呢？ 个奇数相加，当  为偶数时和为偶数， 为奇数时和为奇数  不管你怎么换数字，只要保持偶数/奇数的身份不变，奇偶性就不会变。所以：  当  是奇数时（即 ），偶数和是偶数、奇数和是奇数，两者永远不可能相等，输出 NO 当  是偶数时（即 ），两边的和奇偶性相同，有可能构造出来  那  呢？，是奇数情况，直接 N...

BGN75 构造三角形 思路 题目给了四个正整数 ，要我们从三个区间 、、 各取一个数 ，使得它们能构成一个非退化三角形。 三角形的核心条件就是任意两边之和大于第三边。由于 （因为区间本身就是递增的），最紧的约束一定是 。 那怎么让  最容易满足呢？很自然的想法：让  和  尽量大， 尽量小。   最大取   最大取   最小取   所以直接取 。 验证一下三角形条件：  ，因为 ，所以  恒成立 ✓  ✓  ✓（同第一条）  三个条件全部满足，而且不需要任何特判。题目保证有解，我们的构造也确实总是合法的，完美！ 构造题就是这样，找到一个巧妙的取值方式，比暴力枚举优雅多了。 代码    C++...

BGN73 构造数对 思路 这题看起来条件挺多，我们来逐个拆解。要找一对正整数  满足：   （b 整除 a）    条件这么多，别慌，先想想有没有什么特殊构造能一把全满足。 关键观察：取 。 验证一下：   ✓  ✓（自己整除自己） ，当  时成立 ✓ ，当  时成立 ✓  所以只要 ， 就是一组合法解。 那  呢？此时  和  都只能取 ，但  不满足 ，所以无解，输出 。 就是这么简单，构造题的核心就是找到一个巧妙的构造方式，不用暴力搜索。 代码    C++   Java   Python3   JavaScript   #include <iostream> using ...

构造数独 思路 题目要求构造一个  的非负整数矩阵，使得每行每列的和都等于 。 最直接的想法：先均匀分配，再处理余数。 设 ，。如果所有格子都填 ，那么每行每列的和是 ，还差 。 怎么把每行每列各补上  呢？只需要在每行恰好选  个格子加 1，同时保证每列也恰好被选中  次。 用循环移位就能优雅地搞定：第  行把列 （下标对  取模）的格子加 1。这样每列  恰好在  行中被选中（因为是循环的），行列对称性完美满足。 最终每个格子的值： $$ 整个构造 ，非常简洁。 代码    C++   Java   Python3   JavaScript   #include <bits/stdc...

交换到最大 思路 操作的本质是：选一个非首位、非零的数字，减 1 后和左邻交换。反复操作就是把一个数字  往左移  步，代价是值减少 ，到达后变成 （需要 ）。 关键观察：数字最大是 9，所以任何数字最多只能左移 9 步。 这意味着对于结果的第  位，候选人只来自剩余数字序列中的前 10 个元素。贪心策略很自然：  从左到右确定每一位 对当前位，查看剩余序列中前 10 个数字（偏移量 ） 选「到达值 」最大的那个放到当前位 从序列中删掉被选中的数字  当一个数字被移到前面时，它经过的那些数字会自然右移一位，维持相对顺序不变——这和链表中"删除节点"的效果完全一致。 用链表维...

九倍平方数 思路 拿到这道题先想想，一个数能被 9 整除有什么等价条件？没错，就是各位数字之和能被 9 整除。 题目允许我们把某一位数字 （）替换成 。那每个数字替换后会变成什么？  ，：替不替都一样 ：数字和多了 2 ：数字和多了 6（等价于 mod 9 减了 3） ：不能操作，只能保持原样  所以问题转化成：设原始数字和为 ，有  个 2 和  个 3，每个 2 可以选择给总和加 2，每个 3 可以选择给总和加 6。问是否存在 ， 使得： $$ 关键优化  最多只有 9 种取值（ 就能覆盖所有可能）， 同理。所以不管 、 多大，只需要枚举到  和  就够了。 算法流程：  遍历字符串统计数...