看到 P8627 [蓝桥杯 2015 省 A] 饮料换购熟悉蓝桥杯的朋友应该会心一笑——这是省赛里少见的“送分题”。但别急着得意我身边很多同学在这道题上翻过车有人把简单模拟写成了死循环有人算出了错误的总瓶数还有人明明 AC 了却看不懂题解里的数学公式。这道题表面考的是循环模拟本质上却把“模拟”和“数学”两条路摆在台面上让你自己选。今天这篇就把它彻底拆开从最笨的模拟到最巧的公式带你把每一步为什么这么做都吃透。不管你是刚接触蓝桥杯的新手还是想提升竞赛思维的选手这题都值得花二十分钟认真琢磨。1. 题目到底在考什么从模拟到数学的思维台阶1.1 原题回溯饮料换购的规则和陷阱题目大意是乐羊羊饮料厂搞活动3 个瓶盖可以换 1 瓶饮料小明买了 n 瓶全部喝完并参与换购问最终一共能喝多少瓶。n 的范围是 1 到 10000。注意“不允许赊账”——也就是说你的瓶盖数不足 3 个时不能预支瓶盖去换饮料。这个条件看起来普通却是很多人第一次写模拟时忽略的。另外还有一个隐蔽陷阱换来的那瓶饮料喝完以后它的瓶盖也是你的要继续参与后续换购。很多人只算了一次兑换就收工比如 n4如果只换一次得到 5 瓶但实际先喝 4 瓶有 4 个盖换 1 瓶喝完又 1 个盖总瓶数还是 5没区别但到 n5 就有区别了5 盖换 1 瓶剩 2 盖喝完新瓶又得 1 盖总共 3 盖还能再换 1 瓶最终喝 7 瓶。只算一次兑换的人会得到 6 瓶这就是读题不细造成的失分。1.2 为什么说这题是“模拟数学”的经典组合模拟和数学是算法竞赛中两种最基本的解决问题方式。模拟的好处是贴近生活“我手里有多少个瓶盖就换多少瓶”无需推导照着规则写循环就行正确性容易保证。数学的好处是效率极高公式一出来 O(1) 解决还能加深对问题本质的理解。P8627 的特殊之处在于它同时欢迎这两种解法n 最大只有 10000模拟法完全能跑甚至你一次换 1 瓶的写法都能 AC但如果你只会模拟遇到 n 变成 10^18 的同类型题就会傻眼。所以教练常拿这道题当教学案例让选手自己去发现“换一瓶净消耗 2 个瓶盖”这个关键点。接下来两种解法我都给你你自己感受一下思维层面的差异。2. 模拟法实现跟着规则走稳赚不赔2.1 模拟的代码思路和初版写法模拟的写法有很多种最直观的是维护两个变量total 表示已经喝掉的总瓶数caps 表示当前手里有多少个瓶盖。初始 total ncaps n。进入循环只要 caps 还大于等于 3就说明还能换。一次换多少瓶我见过不少人写成while (caps 3) { caps - 3; total; caps; }这是最朴素的“一次换一瓶”逻辑上没错也能过这道题但循环次数约等于兑换次数n10000 时大约要循环几千次虽然也没压力但不够优雅。更聪明的做法是每次用整数除法一次换一批while (caps 3) { int newBottles caps / 3; total newBottles; caps caps % 3 newBottles; }这里的caps % 3是拿 3 个瓶盖换一瓶后剩下的零头newBottles是换来的新瓶喝完新产生的瓶盖。顺序不能反先算剩余零头再加新瓶盖。很多新手会写成caps newBottles caps % 3其实是一样的但如果你先加了再取模就会把已经用掉的瓶盖也算进去结果错得离谱。完整代码如下C 和 Python 各一份#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; int total n; // 已经喝掉的总瓶数 int caps n; // 当前手里的瓶盖数 while (caps 3) { int newBottles caps / 3; total newBottles; caps caps % 3 newBottles; // 剩余零头 新瓶盖 } cout total endl; return 0; }n int(input()) total caps n while caps 3: new_bottles caps // 3 total new_bottles caps caps % 3 new_bottles print(total)2.2 模拟法的关键细节和易错点每次循环的核心是“换来的新瓶喝完又产生瓶盖”。有人问newBottles 是还没喝的饮料为什么就直接算进 caps 里因为题目要求把所有饮料都喝完所以换来的饮料必然会被喝完它们的盖子必然入手。这一步在逻辑上是提前记账不是赊账因为我们手里的瓶子确实是真实存在的只是还未喝。这里要注意和题目“不允许赊账”区分开不允许赊账是指你不能凭空预支 3 个瓶盖去换一瓶还没到手的饮料但已经换来的饮料喝完产生的瓶盖是实实在在属于你的可以直接用于下一轮。手动模拟一下 n3total3, caps3进入循环new1, total4, caps011循环结束输出 4。完全正确。另一个易错点是循环条件写成caps 0或while(caps ! 1)这样会导致死循环或漏算。因为当 caps 小于 3 时兑换无法进行必须停下来。你可以在循环开头打印 caps 调试但提交时记得删掉调试代码。蓝桥杯评测只看输出调试信息会造成什么结果不用我多说吧。我在课上让学生做过一个对比实验一次换一瓶的写法和一次换多瓶的写法在 n10000 时运行时间差别不大但放到 n10^8 就能明显拉开差距。作为竞赛选手应该养成用数学运算减少循环次数的好习惯。2.3 模拟法的复杂度一次换多瓶的模拟每次循环后 caps 会变成caps % 3 caps / 3近似等于原值的 2/3 再取整也就是说瓶盖数是指数级下降的。n10000 时循环次数大概是 log_{3/2}(10000) ≈ 23 次完全可以忽略。而一次换一瓶的写法循环次数等于兑换次数大约 (n-1)/2n10000 时约 5000 次虽然也能过但显然不是最优。时间复杂度方面一次换多瓶是 O(log n)一次换一瓶是 O(n)空间复杂度都是 O(1)。这道题数据范围不大两种写法都能过但如果是 n10^9一次换一瓶的写法会超时一次换多瓶的模拟依然轻松数学公式更是秒出。所以我建议你从这道题开始就养成“能用除法绝不用单步循环”的意识。3. 数学法推导三行代码干掉一个循环3.1 从模拟到公式的推导过程如果你已经接受了模拟不妨再往上走一步能不能直接算出答案设最终一共喝了 S 瓶。这 S 瓶中最初买的 n 瓶显然是其中一部分剩下的 S-n 瓶全部来自兑换。每兑换 1 瓶饮料需要付出 3 个瓶盖但这 1 瓶饮料喝完又会给你 1 个瓶盖所以净消耗是 2 个瓶盖。初始你手里有 n 个瓶盖对应最初买的 n 瓶所有这些瓶盖最终要么被兑换时消耗掉要么在结束时报废在手里剩余瓶盖数 r 一定小于 3。于是我们可以建立等式初始瓶盖数 n 2 * (S - n) r其中 r 是最终剩余瓶盖数0 ≤ r 3。为了让 S 最大等价于让 r 尽可能小但 r 的取值受限于兑换过程。更直接的推导是观察每次兑换净消耗 2 个瓶盖所以能够进行的兑换次数 k floor((n - 1) / 2)。为什么是 n-1 而不是 n因为最后一次兑换前你至少得有 3 个瓶盖而兑换结束后会留下至少 0 个瓶盖。从 n3 开始验证n3k1n4k1n5k2n6k2。n1、2 时 k0。规律就是 k(n-1)//2。所以最终答案 Sn(n-1)//2。这个推导可能有点抽象换个角度理解你手里的瓶盖数每经过一次兑换就相当于少了 2 个。你最多能兑换多少次就是看 n 个瓶盖能经历多少次“减 2”还剩下至少 3 个。从 n 开始每减 2直到小于 3这个次数就是 (n-3)/2 向下取整再加 1化简一下就是 (n-1)/2 向下取整。n10 时(10-3)/23.5 向下取整 3加 1 得 4正好是兑换次数。3.2 数学法的代码实现代码就直观多了C 直接输出n (n - 1) / 2注意整数除法会截断刚好符合向下取整。Python 用//。完整提交代码#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; cout n (n - 1) / 2 endl; return 0; }n int(input()) print(n (n - 1) // 2)对比模拟法几十行的循环这个简直像在开挂。但别高兴太早数学法最怕的就是推导错误。建议在考试时如果时间允许先用模拟法验证几个小数据再套数学公式双保险。我见过有同学直接套公式n n / 2结果 n3 时算出 4.5 或 4如果整除但实际是 4n5 时算出 7若用整除 527碰巧对了但 n4 时算出 6实际是 5于是提交就 WA。所以那个“-1”不是可有可无的。3.3 推广到每 m 个瓶盖换 1 瓶把规则从“3 个瓶盖换 1 瓶”推广到“m 个瓶盖换 1 瓶”公式会变成 S n (n-1)//(m-1)。推导方式完全一样每换一瓶净消耗 m-1 个瓶盖因为付出 m 个、回来 1 个。为什么是 n-1 而不是 n 或 n-m1我们可以严格推设兑换次数为 k最终剩余瓶盖 r则有 n k*(m-1)r且 0 ≤ r m。结束兑换时手里瓶盖数不足以再换一瓶但每换一次至少会留下 1 个瓶盖因为换来的饮料喝完会给你 1 个盖所以 r 的取值范围其实是 1 到 m-1。为了让 k 最大r 应尽可能小但 r 的最小可能值是 1。于是 n-1 k*(m-1) (r-1)其中 r-1 的范围是 0 到 m-2。因此 k floor((n-1)/(m-1))。验证 m4n1 -1n2-2n3-3n4-54 盖换 1剩 1 盖喝 1 得 1 盖共 2 盖S5公式 4(3)//35对。n7m47 盖换 1剩 314再换 1剩 112S9公式 7(6)//39正确。这个公式在 m1 时对所有 n 成立。可以当作结论记住但考试时还是建议现推因为你不知道题目会不会加额外限制比如“最多兑换 k 次”或“换来的饮料不给瓶盖”。4. 实战完整代码和手动模拟4.1 两种解法的完整代码下面给出两份可以直接提交的代码。注意输入只有一行一个整数输出一行一个整数没有多余空格和换行。C 用标准 IOPython 用 input() 足够。这里我建议竞赛选手用 scanf/printf 或 cin/cout 记得取消同步ios::sync_with_stdio(false); cin.tie(nullptr);蓝桥杯的评测机性能一般养成这个习惯没坏处。整合注释版如下#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; // 模拟版一次换多瓶 int total n; int caps n; while (caps 3) { int t caps / 3; total t; caps caps % 3 t; } cout total endl; // 数学版直接输出下面的结果 // cout n (n - 1) / 2 endl; return 0; }n int(input()) # 模拟版 total caps n while caps 3: t caps // 3 total t caps caps % 3 t print(total) # 数学版 # print(n (n - 1) // 2)建议你在本地把两个版本都跑一遍输入同样的数据比较输出是否一致。这是检验数学推导正确性的好办法。4.2 手动模拟 n10 的完整过程为了让你彻底看明白兑换过程我以 n10 为例走一遍完整流程。初始买 10 瓶喝完后手里 10 个瓶盖total10。第一轮10 个瓶盖10/33换 3 瓶。用掉 9 个盖剩 1 个盖。喝掉 3 瓶total13又得 3 个盖手里共 4 个盖。第二轮4 个瓶盖4/31换 1 瓶。用掉 3 个盖剩 1 个盖。喝掉 1 瓶total14又得 1 个盖手里共 2 个盖。此时 23停止。最终喝了 14 瓶。用数学公式10 (10-1)/2 10414一致。这个手算过程也可以作为答题时的验证手段。轮次初始瓶盖可换瓶数剩余瓶盖喝完后新瓶盖当前瓶盖累计喝瓶数010---1010110313413241112144.3 用极端数据验证拿边界数据测试n1 时只有 1 瓶没有瓶盖兑换答案 1模拟和数学都是 1。n2 时2 个瓶盖不够换答案 2。n3 时3 个瓶盖换 1 瓶喝掉后又有 1 个盖答案 4。n10000 时数学公式给出 10000499914999。你可以用模拟跑一遍结果一定一致。这些手测数据在比赛时很重要写完代码先自测几个别急着交能避免低级失误。我曾在集训时让学生专门写一个暴力模拟一次换一瓶来验证数学公式他们发现两组数据从 n1 到 n10000 完全吻合这才彻底放心。这种验证习惯比任何解题技巧都值钱。5. 常见问题与赛场避坑5.1 读题不清搞错瓶盖还是空瓶很多变体题会把“瓶盖”改成“空瓶”比如 3 个空瓶换 1 瓶。注意规则变了你用空瓶换来的新饮料喝完会产生新的空瓶这个和瓶盖模型本质相同都是“消耗 m-1 个”。但如果题目说的是“每 3 个瓶盖换 1 瓶换来的饮料不再参与兑奖”那公式完全不同模拟条件和数学推导都要改。所以读题时先圈出“瓶盖”“空瓶”“是否继续参与”这几个词。蓝桥杯的题面一般不长重复读两遍不会耽误太多时间但能避免最冤枉的失分。5.2 模拟时先加后换还是先换后加前面提到正确的顺序是先算能换几瓶更新 total然后caps caps % 3 newBottles。有些同学写成caps (caps newBottles) % 3看起来好像差不多实际错得离谱。比如 n5第一轮 new1若用(51)%30认为剩余 0 个盖下一轮循环结束total6正确剩余应该是5%31213还能再换 1 瓶total7。这个错误非常隐蔽建议在纸上多走几轮再写代码。我还见过一种错误写法先用caps - 3再total再caps这种一次换一瓶的写法只错在忘记考虑一次换多瓶的批量操作但最小规模下没问题。问题在于循环次数多且容易手滑把写成--导致死循环。所以能用整除批量处理就别用单步自增。5.3 整数溢出和除法细节本题 n≤10000int 完全足够甚至 long long 都多余。但如果你习惯了写竞赛代码建议把整数类型统一用 long long防止变体题数据范围扩大。除法方面C 的 int 除法是向零取整对正数来说就是向下取整Python 的//也是向下取整两者在这个题里一致。注意不要用浮点数比如(n-1)/2.0再转 int多此一举还可能踩精度坑。5.4 蓝桥杯的评测环境和提交注意事项蓝桥杯的 OJ 使用标准输入输出不需要文件操作。提交代码时选择正确的语言版本C 选 C14 或 C17 都行Python 选 Python 3。有的同学本地跑没问题提交就 CE多半是头文件写错或代码末尾少写 return 0。我建议把模板记熟C 用#include bits/stdc.hPython 用input()读一行。另外蓝桥杯省赛是实时评测但不会告诉你每个测试点的结果所以自测务必充分不要依赖评测反馈。一个实用技巧在本地把题目给的样例跑通后再额外造几个边界数据比如 n 的最小值 1、最大值 10000、以及容易出错的 3、4、5、6。全部通过再提交能大幅提高 AC 概率。6. 延伸从这道题看竞赛中的“模拟数学”思维6.1 什么时候选择数学公式什么时候用模拟竞赛中经常遇到“模拟能过但写得啰嗦”“数学高效但难推导”的抉择。我的一般原则是数据范围小且规则复杂先用模拟保平安数据范围大或规则有明显数学结构优先推公式两者都能用时选自己最有把握的。P8627 这种题模拟和数学都简单但数学推导需要先想清楚“净消耗”模型模拟则几乎不会出错。考场上有时候不是要用最漂亮的解法而是要用最稳的解法。如果你推公式推一半卡住了立刻回头用模拟不要死磕。场景推荐方案原因n≤1000规则复杂模拟容易实现不易漏细节n≤10^6规则简单模拟或数学模拟 O(n) 可接受n≤10^18数学模拟必然超时数学推导不自信模拟正确性优先6.2 几道类似题目和变体这种“消耗 x 换 y”的模型在 OJ 上很常见比如某些模拟题里“空瓶换水”“瓶盖换饮料”还有“瓶盖换购但不允许赊账”的变体。如果你把 m 变成 4、5甚至限制兑换上限解法思路不变要么循环累加要么推净消耗。很多看似不同的题本质上都是同一个数学模型多做几道就能形成条件反射。建议自己改造题目把 n 改成 10^18m 改成 4看能不能用数学公式秒杀这样才算真正掌握。比如你还可以试试这个变体每 4 个瓶盖换 1 瓶但换来的饮料喝完后瓶盖可以继续用n10 答案是多少用公式10 (10-1)//3 13。模拟一下10 盖换 2 瓶用 8 盖剩 2 盖喝 2 瓶得 2 盖共 4 盖再换 1 瓶剩 1 盖喝 1 瓶得 1 盖共 2 盖总 13 瓶。对上了。6.3 对蓝桥杯备赛的建议蓝桥杯省 A 组的题目通常由易到难第一题或第二题往往是这种“小模拟”但千万不要轻视。一个很常见的现象是简单的题因为读题不仔细或手误反而比难题更容易失分。我的建议是养成“先手算样例、再写代码、最后自测边界”的习惯。P8627 就是完美的训练素材用 20 分钟把它吃透比盲目刷十道难题更有价值。你可以把这道题讲给别人听如果你能讲清楚“为什么净消耗 2 个瓶盖”说明你是真的懂了。我记得第一次在集训队讲这道题时有个学生用数学公式写出了 O(1) 的代码但他解释不清楚为什么是 (n-1) 而不是 n。我说你回去再推一遍第二天他跑过来告诉我他模拟了 n3、4、5 才明白是因为最后一次兑换后至少还要留 1 个瓶盖。这种“先模拟后数学”的过程其实就是竞赛思维成长的缩影。最后再分享一个小技巧拿到任何模拟题先别急着敲键盘想想每一步操作会对什么变量造成什么影响把影响写出来你会发现很多题都有数学规律。P8627 只是个开始希望你通过它爱上这种“从模拟到数学”的顿悟感。