BGN15 纸牌游戏 思路 拿到这题你先想一个问题：Alex 和 Bob 各有两张牌，每人每回合翻一张，总共两回合，翻牌顺序随机——那一共有多少种不同的翻牌方式？ Alex 选先翻哪张有 2 种选法，Bob 也有 2 种，所以总共  种翻牌顺序。 但你再仔细想想，这 4 种顺序的本质是什么？其实就是两张牌怎么"配对"的问题：  配对方式 A：Alex 第一张 vs Bob 第一张，Alex 第二张 vs Bob 第二张 配对方式 B：Alex 第一张 vs Bob 第二张，Alex 第二张 vs Bob 第一张  不管谁先翻谁后翻，最终的对战配对只有这两种。而每种配对方式对...

撞车 思路 题目在说什么？数轴上有  辆车，第  辆车位于 ，速度为 。时刻  时第  辆车在 。如果存在  使得两辆车在同一位置，就会撞车。问最少移除多少辆车才能让剩下的车互不碰撞。 先把所有车按位置从小到大排序。考虑排序后相邻的两辆车 （即 ），它们碰撞的条件是什么？ 碰撞时刻 ，要求 。因为 ，所以需要 ，也就是后面的车速度比前面的车慢，前面的车会被追上。 反过来，如果 ，这两辆车永远不会碰撞（速度相等时因为位置不同也不会碰）。 推广到任意两辆车（不只是相邻的），结论一样：排序后，两辆车不碰撞当且仅当速度是非递减的。 所以问题就变成了：排序后，从速度序列中找一个最长非递减子序列，剩下的车...

牛牛与切割机 思路 题目在说什么？给一个长度为  的序列，在某个位置切一刀，把序列分成左右两个非空连续段，切割代价定义为左段元素和乘以右段元素和，求最小代价。 设总和为 ，在位置  切割后左段和为 ，右段和为 ，代价为 。 枚举所有  个切割位置，用前缀和维护 ，对每个位置计算  取最小值即可。 从数学角度看， 是一个开口向下的抛物线，在  时取最大值。所以最小值出现在  离  最远的地方，也就是切割尽量靠近两端。但由于序列元素可能有各种取值，直接枚举所有位置更稳妥。 代码    C++   Java   Python3   JavaScript   #include <bits/std...

分解质因数 思路 经典的质因数分解问题。给一个正整数 n，把它拆成若干个质因数的乘积，从小到大输出。 核心思路非常简单：从最小的质数 2 开始，能整除就一直除，除完了再试下一个数。为什么不需要专门判断 i 是不是质数？因为当我们试到 i 的时候，所有小于 i 的因子已经被除干净了，所以如果 n 能被 i 整除，i 必然是质数。 一个关键优化：只需要枚举到 。如果循环结束后 n 还大于 1，说明剩下的 n 本身就是一个质因数（最大的那个）。 举个例子：n = 60  i = 2: 60 / 2 = 30, 30 / 2 = 15，输出两个 2 i = 3: 15 / 3 = 5，输出一个 3 i...

Poi 的新加法（Easy Version） 思路 题目定义了一种"二进制只进位加法" ，只做一次进位、不考虑连锁进位。先搞清楚这个运算到底在干嘛。 在标准二进制加法中， 的过程是：先算本位（XOR），再算进位（AND 左移一位），然后把进位加回去，重复直到没有新进位。而这道题的运算只做一轮：算出本位和进位之后就停了，不把进位再加回去继续传播。 但仔细想想，，这其实就等于 ！因为一轮进位恰好就是普通加法。 等等，验证一下样例 2：，？可是答案是 0 啊。 所以这个运算不是"一轮进位加法"，而是只保留进位、丢掉本位。也就是说： $$ 验证样例：  ，对了 ...

小红闯关 思路 题目在说什么？有  个关卡，必须按顺序通过。通过第  关需要  时间。每通过  个关卡（无论是正常通过还是用道具跳过），就获得一个跳关道具。跳关道具可以在任意关卡使用，使用后零时间通过该关。问通过所有关卡的最少时间。 那怎么想这道题呢？ 关键观察 首先，无论怎么选择跳哪些关卡，所有  关都会被通过（要么花时间打，要么用道具跳）。所以第  关（1-indexed）通过后，累计通过了  关，已获得  个道具。 但道具在通过第  关之后才产生，所以在第  关之前，可用的道具数量是 。 于是问题转化为：从  个关卡中选出一个子集  来跳过，最大化 （即省下的时间），同时对所有  都满足...

小红的字符串修改 思路 拿到这道题，先想一下核心问题是什么？给你两个字符串 s 和 t，s 比 t 短（或等长），你要把 s 修改成 t 的某个连续子串，每次修改一个字符的代价是字母表上的"最短环形距离"。问最小总代价是多少？ 什么叫环形距离？比如 a 到 z 的距离不是 25，而是 1——因为可以从 a 往左绕一步到 z。所以两个字符 c1 和 c2 之间的代价是 min(|c1-c2|, 26-|c1-c2|)。 具体做法  枚举 t 中所有长度为 |s| 的子串（滑动窗口） 对每个子串，逐字符和 s 比较，累加环形距离 取所有窗口中代价最小的那个  就是个暴力滑窗，没...

支付宝消费打折 思路 拿到这道题，先想清楚目标是什么？你有 n 件物品，每件只能买一个，有的能用支付宝打九五折，有的不能。你手上有 m 元余额，问最多能买几件？ 那既然要买尽可能多的物品，直觉告诉你应该怎么做？——当然是先买便宜的。贵的往后排，能塞几个塞几个。 关键点：怎么算每件物品的实际花费？  支持优惠的物品（标记为 1）：实际花费 = 原价 × 0.95 不支持优惠的物品（标记为 0）：实际花费 = 原价  然后把所有物品按实际花费从小到大排序，贪心地从最便宜的开始买，直到余额不够为止。 一个细节：浮点数精度问题 0.95 是个小数，直接用浮点运算可能有精度问题。怎么避免？把所有数都乘以...

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

小苯送礼物 思路 这道题说白了就是一个自定义排序问题。小苯要从 n 个粉丝里选 k 个送礼物，怎么选？按"支持力度"来排。 支持力度怎么算？点赞算 1 点，收藏算 2 点，所以一个粉丝的支持力度 = 赞数 + 2 * 收藏数。 那如果两个粉丝支持力度一样呢？题目给了两层 tiebreak：  先比收藏数，收藏多的优先 收藏也一样？编号小的优先  选出前 k 名后，按编号升序输出就行。 具体做法  读入每个粉丝的赞数和收藏数，算出支持力度，记下编号 按照"支持力度降序 → 收藏数降序 → 编号升序"的规则排序 取前 k 个粉丝的编号，排个序输出  就是个排...

mex 思路 这道题乍一看像是模拟题——每轮算个 MEX，然后所有元素减掉它，直到全部相等。但直接模拟肯定超时，因为操作轮数可以达到  级别。关键在于找到规律，跳过大量重复操作。 什么时候无解？ 如果数组里没有 0，那 MEX = 0，减 0 等于啥都没变。除非数组本身已经全部相等（直接输出 0），否则永远不会改变，输出 -1。 目标状态一定是全 0 一旦有元素变成 0，它就永远是 0（因为 ）。所以如果最终要全部相等，只能全部等于 0。 核心观察：用原始数组的去重排序来推导 MEX 假设我们把原始数组排序去重得到 （其中 ）。经过若干轮操作后，累计减去的总量为 ，那么此时数组中出现的不同值就...

魔法棒 思路 拿到这道题，先理清操作到底在做什么。小坤一开始有 1 根魔法棒，每次操作可以选一根魔法棒，把它"分裂"成  根（ 是正整数）。注意：原来那根消失了，变成了  根新的，所以每次操作净增  根。  时净增 0，没意义。 时，能增加的数量依次是  那问题就变成了： 能不能表示成若干个  中元素的和？ 关键推导 最小的两个增量是 3 和 8，它们互质（）。根据 Chicken McNugget 定理（也叫 Frobenius 定理），用 3 和 8 做非负整数组合，不能表示的最大整数是 。也就是说，所有  的非负整数都能用若干个 3 和若干个 8 凑出来。 那小于 1...

斐波那契字符串 思路 题目定义了斐波那契字符串：，，（拼接）。要求统计  中的逆序对数量，即满足  且 ， 的  对数，结果对  取模。 显然不能把字符串构造出来暴力数，因为长度是斐波那契级别增长的。我们需要找递推关系。 ，所以  的逆序对来自三部分：  左半部分  内部的逆序对  右半部分  内部的逆序对  跨越左右的逆序对：左边的 '1' 和右边的 '0' 配对   所以核心递推式： $$ 其中  和  分别是  中 '1' 和 '0' 的个数，它们也满足斐波那契递推：     用样例验证：  ：，。正确！ ：，。正确！  由于有多组查询（ 可达 5000， 可达 ），我们预处理所有  的...

田忌赛马 思路 拿到这道题，第一反应是什么？三匹马对三匹马，田忌可以自由安排出场顺序，问能不能赢至少两局。 那田忌的马一共有多少种出场顺序？3 匹马的全排列，也就是  种。数量这么少，直接暴力枚举所有排列不就行了？ 具体做法  读入齐威王的三匹马速度（顺序固定），以及田忌的三匹马速度 对田忌的马生成所有排列（一共 6 种） 对每种排列，逐局比较：田忌的马速度严格大于齐威王的马才算赢 只要存在某种排列能赢 2 局及以上，输出 Yes；否则输出 No  这题的关键点就一个：严格大于才算赢，等于不算。比如样例 2 里田忌有一匹速度为 3 的马，但另外两匹都是 2，和齐威王的 2 打平，赢不了两局。 ...