尧图网站开发 
“CSP-J第一道模拟题——贪心的小朋友”这个标题我自己看了都想笑——正好就是我前段时间给集训队出的一套模拟卷里的T1。出题那天我的目标特别明确让第一次接触竞赛的孩子也能在第一题拿到分同时又能区分出谁真正理解了“模拟”和“贪心”这两个入门阶段最容易混淆的概念。先说结论CSP-J也就是入门组的第一题这几年越出越务实不考什么高深算法反而是把读题、取模、边界处理这些基本功放到台面上考。很多同学觉得T1简单结果一到考场上不是int溢出就是没考虑余数为0白白丢分。所以这篇文章我把这道“贪心的小朋友”从出题思路、数学推导到完整代码全部拆开讲一遍顺便把这类T1背后的通用套路也梳理出来。不管你是刚学C没多久的选手还是带学生备赛的老师照着这个思路去练都能少踩很多坑。1. 题目整体设计与思路拆解1.1 CSP-J第一题到底在考什么很多同学备考CSP-J时有一个误区以为T1会考什么高深算法于是疯狂刷最短路径、动态规划结果考试时发现第一题就是个“纸老虎”。实际上观察近几年的命题风格就能看出来T1的核心考点一直很稳定就三条能不能读懂题面能不能找到规律能不能把边界处理干净。比如那道经典的《分糖果》题面绕来绕去本质上考的就是“在区间里找一个数让它对n取模的结果最大”。你说它是纯模拟直接遍历区间确实能拿分但数据范围一大就超时。你说它是贪心其实也不完全是它考的是对模运算的理解。这类题目最大的共同点就是不考你知道多少算法考你能不能把一个具体场景抽象成一个数学公式。这其实就是第一题存在的意义——给整场考试定基调。它要告诉所有选手一个信息信息学竞赛不是比谁会背算法模板而是比谁能把问题看透。所以我在设计这套模拟卷时也刻意把T1出成了这个风格表面看是个发糖过程实际上一行公式就能解决表面看涉及“贪心”实际上是让大家理解贪心策略在什么条件下成立。1.2 “贪心的小朋友”题面还原与解读这道题我完整的题面是这样的有n个小朋友按编号1到n排成一队老师手上有m块完全相同的糖果。发糖规则是从1号小朋友开始每次给当前小朋友1块糖然后轮到下一个人发到n号之后再从1号开始新一轮。老师手里的糖发完就停止不要求最后一轮正好发满所有人。发糖开始之前所有小朋友可以自由协商交换位置想怎么换就怎么换换完一次之后再不允许调整。每个小朋友都非常“贪心”都希望自己最终拿到的糖尽可能多。现在给你n、m和某个小朋友的编号k请你回答两个问题在所有人都按最优方式换位的情况下第k号小朋友最多能拿到多少块糖为了让第k号小朋友拿到这个最大值换位后他应该站在队伍中的几号位置如果有多个位置都能达到最优输出位置编号最小的那个。输入只有一行三个整数n、m、k其中1 ≤ k ≤ n ≤ 10^90 ≤ m ≤ 10^18。输出一行两个整数分别是最大糖果数和目标位置编号。这道题第一眼看上去像是个模拟题因为发糖过程描述得很具体。但如果你真开一个数组去模拟每一轮发糖肯定会出事——m最大能到10^18循环1e18次再快的机器也扛不住。所以出题人真正想看的是你能不能跳出模拟的过程直接用数学办法把结果算出来。1.3 解题思路模拟只是起点公式才是终点拿到这种题我的建议永远是先把最朴素的模拟思路写出来再去想优化。这不是浪费时间而是帮助你理解题目过程。朴素地想n个小朋友排成一队老师从头到尾循环发糖那每个小朋友肯定先共同经历完整的若干轮每轮拿1块最后剩下不够一轮的糖果只会按顺序发给队伍开头的那几个位置。这个观察非常关键。它说明了一件事发糖的过程本质上可以拆成两部分第一部分是每个人都拿得到的“保底”第二部分是排在最前面的少数人额外拿到的“奖励”。只要能把这两个数量算清楚就不需要一个一个数糖了。于是解题思路就很清晰了先算m除以n的商和余数。商就是每个人保底拿到的糖数余数就是发完完整轮次后剩下的糖果数。由于剩下来的糖果只能按队伍顺序一个一个发给排在最前面的人只要余数大于0就说明队伍最前面的人能比后面的人多拿1块。到这里所谓“贪心的小朋友”该怎么选位置已经呼之欲出了——往最前面站就行因为只有靠前才有可能触碰到那份“额外奖励”。2. 核心细节解析贪心策略与取模计算2.1 发糖模型的数学本质整除与余数把发糖过程抽象成数学语言就是有m块糖要发给n个人按顺序循环分配第i个位置最终拿到的糖数只可能是两种情况。先用m除以n得到商q和余数rm q × n r其中0 ≤ r n。这个拆分的含义非常直观前q轮发下去每个位置都拿到了q块糖第q1轮只有前r个位置能各拿到1块后面的位置只能眼巴巴看着。所以站在前r个位置的小朋友总糖数是q 1站在第r个位置之后的小朋友总糖数只有q。举个例子n5m12。12除以5商2余2也就是说每个人先拿2块剩下2块只能给队伍前两个位置各加1块。最终位置1和位置2拿到3块位置3、4、5拿到2块。这就完全对应了发糖的实际过程。理解这个小例子之后你会发现整个题目根本没有“模拟”的空间直接算就够了。2.2 贪心策略为什么可行既然题目叫“贪心的小朋友”那绕不开一个问题为什么每个小朋友只要站前面就行不需要考虑其他人怎么选这就是贪心策略成立的条件之一——局部最优能直接导向全局最优而且选择之间没有互相干扰。在这道题里小朋友之间不存在“你拿多了我就拿少了”的零和博弈。实际上只要r 0每个小朋友都只需要把目标定为“站进前r个位置”即可。前r个位置的数量是固定的但第一个位置和第二个位置拿到的糖一样多所以小朋友A站1号、小朋友B站2号还是A站2号、B站1号结果没有任何区别。这个性质让整个问题变得非常温和不需要做什么复杂的博弈分析。反过来如果题目改一下只有拿到最多糖的那个人才算赢其他人都算输那问题立刻就变复杂了因为小朋友之间会产生竞争这时候再用贪心就会出错需要更复杂的策略。这也是我想通过这道题传递的一个小道理贪心不是无脑选最优它要求你证明这个“最优”选下去不会造成后续麻烦。2.3 边界条件与long long的坑这类T1最大的杀手从来不是算法而是边界条件。本题有几个边界必须单独拿出来说第一n1时。队伍只有一个人那无论m是多少所有糖都是这个小朋友的。m/n直接就是m本身余数r恒为0。这时候公式依然成立输出m和1就行不会出错但很多同学在推导时会觉得“每人先分q块再或许多分1块”的表述在n1时有点绕容易自我怀疑。第二r0时。这意味着糖果恰好整除每个人都只拿q块没有人能多拿1块。这时候“最优位置”又该选哪里题目说输出位置编号最小的那一个所以答案就是1号。虽然站在哪里都一样但按题意必须输出1。第三数据范围。n最大10^9m最大10^18这两个数相乘或者取模之后int完全放不下必须用long long。更稳一点的做法是全部声明成long long因为即使答案再大m/n也不会超过10^18long long足够。我见过不少同学因为写着写着把m的类型写成int然后大数据样例直接WA特别可惜。3. 实操过程从模拟到O(1)优化的完整实现3.1 先写一版最直观的模拟代码考试时如果第一眼没看穿规律完全可以先写一版最朴素的模拟保底。我上课时经常跟学生说模拟代码哪怕超时也能帮你理解题目过程而且如果真的时间不够、数据小它还能拿部分分。模拟的思路就是开一个数组或者用计数变量然后从头到尾循环发糖。可以用round表示当前发到第几轮current表示当前轮到哪个位置每发一次糖就判断是否发完。C代码长这样#include bits/stdc.h using namespace std; int main() { long long n, m, k; cin n m k; vectorlong long candy(n, 0); long long remain m; long long pos 0; while (remain 0) { candy[pos]; remain--; pos; if (pos n) pos 0; } // 找到第k号小朋友所在的位置 // 因为允许任意交换实际上我们要看的是换成站哪能拿最多 long long best 0; long long bestPos 1; for (long long i 0; i n; i) { if (candy[i] best) { best candy[i]; bestPos i 1; } } cout best bestPos endl; return 0; }注意看上面这段代码有个致命问题它假装模拟了发糖然后用循环去找最大值的位置。但第k号小朋友到底最大能拿几块根本不用考虑“第k号小朋友”这个输入数据因为自由换位后所有人机会均等。而且m最大是10^18这个while循环发一次糖减一次跑都跑不完。不过这段代码对理解题目有巨大帮助。它清楚地展示了一个事实发糖的顺序就是从位置1开始循环前r个位置天然多拿1块。看到这里数学规律就藏不住了。3.2 用O(1)公式替换模拟拿到满分规律找到之后代码就非常简单了。商q m / n余数r m % n。只要r不为0前r个位置都比别人多1块所以最大糖数一定是q 1如果r等于0最大糖数就是q。最优位置无条件选1号因为位置编号最小的多拿位置就是1。对应的标准满分代码如下#include bits/stdc.h using namespace std; int main() { long long n, m, k; cin n m k; long long base m / n; // 每个人保底拿到的糖数 long long extra m % n; // 发完完整轮次后剩下的糖数 long long ans base; if (extra 0) { ans base 1; // 只要有余数站前排就多1块 } // 最优位置贪心选择最靠前的“多拿位置”也就是1号 long long pos 1; cout ans pos endl; return 0; }代码短得惊人但每一行都有讲究。base和extra都用long long避免溢出。pos直接取1因为题目要求多解时输出位置最小而1号一定是前r个位置之一所以它始终是合法且最小的答案。即使extra等于0站在1号也满足“拿到最大值”的条件输出的位置同样是1不用特判。这个版本时间复杂度是O(1)无论n和m给到多大都能瞬间出结果。从模拟到公式的过程恰恰就是信息学竞赛里最核心的能力把枚举变成推理。3.3 手动推演几个样例验证逻辑光说结论不够我习惯考代码前先手算几组数据这里也带大家过一遍。样例一输入5 12 3。m12n5商2余2。每个人先拿2块剩余2块发给前2个位置各加1块。所以有人最多拿3块位置1一定是最优解。输出应该是3 1。模拟发糖验证位置1拿3块位置2拿3块位置3拿2块位置4拿2块位置5拿2块。正确。样例二输入7 21 4。商3余0糖果正好分完每个人固定拿3块谁都一样。最大糖数3最小位置1。输出3 1。这里特别要提醒有些同学会想“既然余数为0我就输出4 1”把输入的k和位置混在一起这就不对了。k这个输入在本题里其实是个干扰项因为自由换位后它没有任何作用。样例三输入1 1000000000000000000 1。n1只有一个小朋友所有糖都给他。商是1000000000000000000余数0输出那一大串数字和1。这个例子就是专门检验long long的如果用int直接溢出成负数。4. 常见问题与避坑指南4.1 新手最容易踩的四个坑第一坑int溢出。这是最普遍的问题没有之一。n和m都到10^18级别了还有人因为习惯用int导致数据一大就出现乱码一样的结果。我的建议很简单看到数据范围里出现超过10^9的数字直接在读入变量旁边写个注释“long long”。第二坑把k当成必须使用的变量。题目给了k不代表k一定有用。这道题里自由换位导致所有人机会相等k完全不影响答案。有些同学非要写个条件判断“如果k大于r就怎么怎么样”反而把自己绕进去了。竞赛题经常这样输入变量里混着一个干扰项考验你对模型的把握。第三坑余数为0时的位置选择。如果不看题面“多解输出最小位置”很容易随手输出k或者输出r甚至输出n。题目要求的是位置编号最小那就必须是1不需要犹豫。第四坑把问题想复杂往DP或者搜索上靠。第一题很少需要复杂算法当你发现一道T1需要写超过30行代码时大概率是没找到规律。多花两分钟回到题面找找能不能用除法、取模直接算。4.2 历年真题里的同款套路T1通用解法总结这道“贪心的小朋友”并不是我凭空发明的它的骨架和2021年CSP-J第一题《分糖果》几乎同源。那题的大概意思是给一个区间让你选一个数使得它对n取模的结果尽可能大。很多人第一反应是枚举区间里所有数但最优做法是直接判断区间长度是否超过n超过就直接取n-1否则取右端点对n取模。这类题总结下来有一个共性模型题目描述了一个过程但结果只取决于几个关键量比如商、余数、间距、最大最小值。做题顺序应该是先读题找规律再套数学公式最后才考虑循环。如果一道题的数据范围是10^9以上那答案几乎不可能是暴力枚举基本就是O(1)公式或者O(log n)级别的计算。带上这个意识遇到同类型的T1就不会慌了。4.3 考前怎么练T1才算练到位我给学生的建议是不要拿难题练T1而是专门找历年真题的第一题掐表10分钟做完后必须把“我为什么能想到这个公式”写出来。这个复盘过程比刷十道新题还管用。比如做《分糖果》时你要能说出“看到区间范围很大我立刻意识到要分情况讨论而不是枚举”做这道“贪心的小朋友”时你要能说出“我通过拆m q×n r明白了多余糖果只会落到队伍头部”。还可以自己造几组小数据来验证理解。造数据的原则很简单覆盖边界。把n设成1把m设成0把m设成恰好是n的倍数把m设成比n大一点点。这些数据一跑代码里隐藏的问题全都现原形。我遇到很多学生样例过了就以为自己AC了结果考试一结束就发现边界全炸。平时养成自造边界数据的习惯考试时才能稳如老狗。我在实际带比赛的过程中还有一个体会第一题不是用来拉开差距的是用来稳定军心的。很多第一次参加CSP-J的同学开场五分钟做不出T1就开始手心冒汗后面的题全受影响。所以考前务必把这种“看似模拟、实则可O(1)计算”的题练透你会在考场上获得一种“这题我见过”的踏实感。真正站在赛场上时这种心态上的优势往往比多背几个算法模板更值钱。 
“CSP-J第一道模拟题——贪心的小朋友”这个标题我自己看了都想笑——正好就是我前段时间给集训队出的一套模拟卷里的T1。出题那天我的目标特别明确让第一次接触竞赛的孩子也能在第一题拿到分同时又能区分出谁真正理解了“模拟”和“贪心”这两个入门阶段最容易混淆的概念。先说结论CSP-J也就是入门组的第一题这几年越出越务实不考什么高深算法反而是把读题、取模、边界处理这些基本功放到台面上考。很多同学觉得T1简单结果一到考场上不是int溢出就是没考虑余数为0白白丢分。所以这篇文章我把这道“贪心的小朋友”从出题思路、数学推导到完整代码全部拆开讲一遍顺便把这类T1背后的通用套路也梳理出来。不管你是刚学C没多久的选手还是带学生备赛的老师照着这个思路去练都能少踩很多坑。1. 题目整体设计与思路拆解1.1 CSP-J第一题到底在考什么很多同学备考CSP-J时有一个误区以为T1会考什么高深算法于是疯狂刷最短路径、动态规划结果考试时发现第一题就是个“纸老虎”。实际上观察近几年的命题风格就能看出来T1的核心考点一直很稳定就三条能不能读懂题面能不能找到规律能不能把边界处理干净。比如那道经典的《分糖果》题面绕来绕去本质上考的就是“在区间里找一个数让它对n取模的结果最大”。你说它是纯模拟直接遍历区间确实能拿分但数据范围一大就超时。你说它是贪心其实也不完全是它考的是对模运算的理解。这类题目最大的共同点就是不考你知道多少算法考你能不能把一个具体场景抽象成一个数学公式。这其实就是第一题存在的意义——给整场考试定基调。它要告诉所有选手一个信息信息学竞赛不是比谁会背算法模板而是比谁能把问题看透。所以我在设计这套模拟卷时也刻意把T1出成了这个风格表面看是个发糖过程实际上一行公式就能解决表面看涉及“贪心”实际上是让大家理解贪心策略在什么条件下成立。1.2 “贪心的小朋友”题面还原与解读这道题我完整的题面是这样的有n个小朋友按编号1到n排成一队老师手上有m块完全相同的糖果。发糖规则是从1号小朋友开始每次给当前小朋友1块糖然后轮到下一个人发到n号之后再从1号开始新一轮。老师手里的糖发完就停止不要求最后一轮正好发满所有人。发糖开始之前所有小朋友可以自由协商交换位置想怎么换就怎么换换完一次之后再不允许调整。每个小朋友都非常“贪心”都希望自己最终拿到的糖尽可能多。现在给你n、m和某个小朋友的编号k请你回答两个问题在所有人都按最优方式换位的情况下第k号小朋友最多能拿到多少块糖为了让第k号小朋友拿到这个最大值换位后他应该站在队伍中的几号位置如果有多个位置都能达到最优输出位置编号最小的那个。输入只有一行三个整数n、m、k其中1 ≤ k ≤ n ≤ 10^90 ≤ m ≤ 10^18。输出一行两个整数分别是最大糖果数和目标位置编号。这道题第一眼看上去像是个模拟题因为发糖过程描述得很具体。但如果你真开一个数组去模拟每一轮发糖肯定会出事——m最大能到10^18循环1e18次再快的机器也扛不住。所以出题人真正想看的是你能不能跳出模拟的过程直接用数学办法把结果算出来。1.3 解题思路模拟只是起点公式才是终点拿到这种题我的建议永远是先把最朴素的模拟思路写出来再去想优化。这不是浪费时间而是帮助你理解题目过程。朴素地想n个小朋友排成一队老师从头到尾循环发糖那每个小朋友肯定先共同经历完整的若干轮每轮拿1块最后剩下不够一轮的糖果只会按顺序发给队伍开头的那几个位置。这个观察非常关键。它说明了一件事发糖的过程本质上可以拆成两部分第一部分是每个人都拿得到的“保底”第二部分是排在最前面的少数人额外拿到的“奖励”。只要能把这两个数量算清楚就不需要一个一个数糖了。于是解题思路就很清晰了先算m除以n的商和余数。商就是每个人保底拿到的糖数余数就是发完完整轮次后剩下的糖果数。由于剩下来的糖果只能按队伍顺序一个一个发给排在最前面的人只要余数大于0就说明队伍最前面的人能比后面的人多拿1块。到这里所谓“贪心的小朋友”该怎么选位置已经呼之欲出了——往最前面站就行因为只有靠前才有可能触碰到那份“额外奖励”。2. 核心细节解析贪心策略与取模计算2.1 发糖模型的数学本质整除与余数把发糖过程抽象成数学语言就是有m块糖要发给n个人按顺序循环分配第i个位置最终拿到的糖数只可能是两种情况。先用m除以n得到商q和余数rm q × n r其中0 ≤ r n。这个拆分的含义非常直观前q轮发下去每个位置都拿到了q块糖第q1轮只有前r个位置能各拿到1块后面的位置只能眼巴巴看着。所以站在前r个位置的小朋友总糖数是q 1站在第r个位置之后的小朋友总糖数只有q。举个例子n5m12。12除以5商2余2也就是说每个人先拿2块剩下2块只能给队伍前两个位置各加1块。最终位置1和位置2拿到3块位置3、4、5拿到2块。这就完全对应了发糖的实际过程。理解这个小例子之后你会发现整个题目根本没有“模拟”的空间直接算就够了。2.2 贪心策略为什么可行既然题目叫“贪心的小朋友”那绕不开一个问题为什么每个小朋友只要站前面就行不需要考虑其他人怎么选这就是贪心策略成立的条件之一——局部最优能直接导向全局最优而且选择之间没有互相干扰。在这道题里小朋友之间不存在“你拿多了我就拿少了”的零和博弈。实际上只要r 0每个小朋友都只需要把目标定为“站进前r个位置”即可。前r个位置的数量是固定的但第一个位置和第二个位置拿到的糖一样多所以小朋友A站1号、小朋友B站2号还是A站2号、B站1号结果没有任何区别。这个性质让整个问题变得非常温和不需要做什么复杂的博弈分析。反过来如果题目改一下只有拿到最多糖的那个人才算赢其他人都算输那问题立刻就变复杂了因为小朋友之间会产生竞争这时候再用贪心就会出错需要更复杂的策略。这也是我想通过这道题传递的一个小道理贪心不是无脑选最优它要求你证明这个“最优”选下去不会造成后续麻烦。2.3 边界条件与long long的坑这类T1最大的杀手从来不是算法而是边界条件。本题有几个边界必须单独拿出来说第一n1时。队伍只有一个人那无论m是多少所有糖都是这个小朋友的。m/n直接就是m本身余数r恒为0。这时候公式依然成立输出m和1就行不会出错但很多同学在推导时会觉得“每人先分q块再或许多分1块”的表述在n1时有点绕容易自我怀疑。第二r0时。这意味着糖果恰好整除每个人都只拿q块没有人能多拿1块。这时候“最优位置”又该选哪里题目说输出位置编号最小的那一个所以答案就是1号。虽然站在哪里都一样但按题意必须输出1。第三数据范围。n最大10^9m最大10^18这两个数相乘或者取模之后int完全放不下必须用long long。更稳一点的做法是全部声明成long long因为即使答案再大m/n也不会超过10^18long long足够。我见过不少同学因为写着写着把m的类型写成int然后大数据样例直接WA特别可惜。3. 实操过程从模拟到O(1)优化的完整实现3.1 先写一版最直观的模拟代码考试时如果第一眼没看穿规律完全可以先写一版最朴素的模拟保底。我上课时经常跟学生说模拟代码哪怕超时也能帮你理解题目过程而且如果真的时间不够、数据小它还能拿部分分。模拟的思路就是开一个数组或者用计数变量然后从头到尾循环发糖。可以用round表示当前发到第几轮current表示当前轮到哪个位置每发一次糖就判断是否发完。C代码长这样#include bits/stdc.h using namespace std; int main() { long long n, m, k; cin n m k; vectorlong long candy(n, 0); long long remain m; long long pos 0; while (remain 0) { candy[pos]; remain--; pos; if (pos n) pos 0; } // 找到第k号小朋友所在的位置 // 因为允许任意交换实际上我们要看的是换成站哪能拿最多 long long best 0; long long bestPos 1; for (long long i 0; i n; i) { if (candy[i] best) { best candy[i]; bestPos i 1; } } cout best bestPos endl; return 0; }注意看上面这段代码有个致命问题它假装模拟了发糖然后用循环去找最大值的位置。但第k号小朋友到底最大能拿几块根本不用考虑“第k号小朋友”这个输入数据因为自由换位后所有人机会均等。而且m最大是10^18这个while循环发一次糖减一次跑都跑不完。不过这段代码对理解题目有巨大帮助。它清楚地展示了一个事实发糖的顺序就是从位置1开始循环前r个位置天然多拿1块。看到这里数学规律就藏不住了。3.2 用O(1)公式替换模拟拿到满分规律找到之后代码就非常简单了。商q m / n余数r m % n。只要r不为0前r个位置都比别人多1块所以最大糖数一定是q 1如果r等于0最大糖数就是q。最优位置无条件选1号因为位置编号最小的多拿位置就是1。对应的标准满分代码如下#include bits/stdc.h using namespace std; int main() { long long n, m, k; cin n m k; long long base m / n; // 每个人保底拿到的糖数 long long extra m % n; // 发完完整轮次后剩下的糖数 long long ans base; if (extra 0) { ans base 1; // 只要有余数站前排就多1块 } // 最优位置贪心选择最靠前的“多拿位置”也就是1号 long long pos 1; cout ans pos endl; return 0; }代码短得惊人但每一行都有讲究。base和extra都用long long避免溢出。pos直接取1因为题目要求多解时输出位置最小而1号一定是前r个位置之一所以它始终是合法且最小的答案。即使extra等于0站在1号也满足“拿到最大值”的条件输出的位置同样是1不用特判。这个版本时间复杂度是O(1)无论n和m给到多大都能瞬间出结果。从模拟到公式的过程恰恰就是信息学竞赛里最核心的能力把枚举变成推理。3.3 手动推演几个样例验证逻辑光说结论不够我习惯考代码前先手算几组数据这里也带大家过一遍。样例一输入5 12 3。m12n5商2余2。每个人先拿2块剩余2块发给前2个位置各加1块。所以有人最多拿3块位置1一定是最优解。输出应该是3 1。模拟发糖验证位置1拿3块位置2拿3块位置3拿2块位置4拿2块位置5拿2块。正确。样例二输入7 21 4。商3余0糖果正好分完每个人固定拿3块谁都一样。最大糖数3最小位置1。输出3 1。这里特别要提醒有些同学会想“既然余数为0我就输出4 1”把输入的k和位置混在一起这就不对了。k这个输入在本题里其实是个干扰项因为自由换位后它没有任何作用。样例三输入1 1000000000000000000 1。n1只有一个小朋友所有糖都给他。商是1000000000000000000余数0输出那一大串数字和1。这个例子就是专门检验long long的如果用int直接溢出成负数。4. 常见问题与避坑指南4.1 新手最容易踩的四个坑第一坑int溢出。这是最普遍的问题没有之一。n和m都到10^18级别了还有人因为习惯用int导致数据一大就出现乱码一样的结果。我的建议很简单看到数据范围里出现超过10^9的数字直接在读入变量旁边写个注释“long long”。第二坑把k当成必须使用的变量。题目给了k不代表k一定有用。这道题里自由换位导致所有人机会相等k完全不影响答案。有些同学非要写个条件判断“如果k大于r就怎么怎么样”反而把自己绕进去了。竞赛题经常这样输入变量里混着一个干扰项考验你对模型的把握。第三坑余数为0时的位置选择。如果不看题面“多解输出最小位置”很容易随手输出k或者输出r甚至输出n。题目要求的是位置编号最小那就必须是1不需要犹豫。第四坑把问题想复杂往DP或者搜索上靠。第一题很少需要复杂算法当你发现一道T1需要写超过30行代码时大概率是没找到规律。多花两分钟回到题面找找能不能用除法、取模直接算。4.2 历年真题里的同款套路T1通用解法总结这道“贪心的小朋友”并不是我凭空发明的它的骨架和2021年CSP-J第一题《分糖果》几乎同源。那题的大概意思是给一个区间让你选一个数使得它对n取模的结果尽可能大。很多人第一反应是枚举区间里所有数但最优做法是直接判断区间长度是否超过n超过就直接取n-1否则取右端点对n取模。这类题总结下来有一个共性模型题目描述了一个过程但结果只取决于几个关键量比如商、余数、间距、最大最小值。做题顺序应该是先读题找规律再套数学公式最后才考虑循环。如果一道题的数据范围是10^9以上那答案几乎不可能是暴力枚举基本就是O(1)公式或者O(log n)级别的计算。带上这个意识遇到同类型的T1就不会慌了。4.3 考前怎么练T1才算练到位我给学生的建议是不要拿难题练T1而是专门找历年真题的第一题掐表10分钟做完后必须把“我为什么能想到这个公式”写出来。这个复盘过程比刷十道新题还管用。比如做《分糖果》时你要能说出“看到区间范围很大我立刻意识到要分情况讨论而不是枚举”做这道“贪心的小朋友”时你要能说出“我通过拆m q×n r明白了多余糖果只会落到队伍头部”。还可以自己造几组小数据来验证理解。造数据的原则很简单覆盖边界。把n设成1把m设成0把m设成恰好是n的倍数把m设成比n大一点点。这些数据一跑代码里隐藏的问题全都现原形。我遇到很多学生样例过了就以为自己AC了结果考试一结束就发现边界全炸。平时养成自造边界数据的习惯考试时才能稳如老狗。我在实际带比赛的过程中还有一个体会第一题不是用来拉开差距的是用来稳定军心的。很多第一次参加CSP-J的同学开场五分钟做不出T1就开始手心冒汗后面的题全受影响。所以考前务必把这种“看似模拟、实则可O(1)计算”的题练透你会在考场上获得一种“这题我见过”的踏实感。真正站在赛场上时这种心态上的优势往往比多背几个算法模板更值钱。