1. 这道题到底在考什么1.1 从“小明种苹果”说起题目背景与核心任务“小明种苹果续”是 CCF-CSP 认证考试 2019 年 9 月场次的第二道编程题。如果你参加过 CSP 认证或者正在准备应该对“小明”这个系列不陌生——从种苹果、种苹果续到买菜、放学小明几乎成了 CSP 第一题、第二题的固定主角。这道题延续了第一题“小明种苹果”的设定但难度上了一个台阶从简单的模拟统计变成了需要处理状态标记和环形相邻判断的问题。先把题目意思用大白话说清楚。有 n 棵苹果树排成一排每棵树在一轮操作中会经历若干次“疏果”和一次“统计”。具体来说每棵树对应的那一行输入第一个数字是这棵树的操作次数后面跟着一串整数。如果某个整数是正数表示这棵树重新统计了当前剩余的苹果数如果是负数或零表示疏果也就是去掉了这么多苹果。关键点在于如果在一棵树的操作序列中某次重新统计得到的苹果数量小于上一次统计的数量说明这棵树发生了苹果掉落因为疏果只会让苹果变少如果统计值反而比之前小那中间必然有自然掉落。题目要我们输出三个数所有树最后剩下的苹果总数 T、发生苹果掉落的树的棵数 D、以及连续三棵都发生掉落的组数 E。注意这个 E 是环形计数的也就是说第 n 棵、第 1 棵、第 2 棵这样跨过末尾的组合也要算进去。我当年第一次做这道题的时候觉得前两个输出挺简单第三个 E 才是真正的坑。因为“环形”这个条件很容易被忽略很多人写完发现样例过了但提交只有 60 分大概率就是 E 算错了。1.2 为什么这道题值得单独拿出来讲你可能会想一道 CSP 第二题而已至于写一篇完整的题解吗我的看法是这道题是理解“模拟题中状态管理”的绝佳范本。它不像第一题那样纯粹走个循环就完事也不像后面的动态规划、图论那样需要复杂算法它考察的是一种很实在的能力——把现实规则准确地翻译成代码逻辑并且处理好边界情况。具体来说这道题涉及几个在工程中非常常见的模式用布尔数组标记状态、环形数组的索引取模、以及在一维数据上做相邻判断。这些技巧在后端开发、数据处理、甚至游戏逻辑里都会反复出现。所以把它吃透不只是为了考试拿分更是练一种“把规则写成代码”的基本功。另外这道题有一个很典型的陷阱如何判断一棵树是否掉落。题目说的是“统计值小于上次统计值”但很多人的第一反应是“只要出现负数就说明掉了”这是完全错误的。疏果是正常操作不掉苹果的树也会疏果。真正判断掉落的依据是统计值的变化。这个逻辑如果没理清楚D 和 E 都会错。2. 解题思路的完整拆解2.1 输入数据的结构分析我们先仔细看一下输入格式。第一行是一个整数 n表示苹果树的棵数。接下来 n 行每行描述一棵树的操作序列。每行的第一个整数 m 表示这棵树有多少个操作数后面跟着 m 个整数。这里有个细节需要注意每行的第一个数 m 本身不算操作它只是告诉你后面有几个数。所以真正要处理的是后面那 m 个整数。我用一个具体的例子来说明3 3 73 -8 -6 2 76 -5 3 80 -6 -15第一棵树有 3 个操作数73、-8、-6。73 是正数表示第一次统计时有 73 个苹果-8 表示疏掉 8 个-6 表示再疏掉 6 个。这棵树没有发生掉落因为只有一次统计73没有后续统计值来比较。第二棵树有 2 个操作数76、-5。同样只有一次统计没有掉落。第三棵树有 3 个操作数80、-6、-15。也只有一次统计没有掉落。所以这个例子的输出应该是 T (73-8-6) (76-5) (80-6-15) 59 71 59 189D 0E 0。但如果输入变成这样3 4 73 -8 -6 60 2 76 -5 3 80 -6 -15第一棵树有 4 个操作数73、-8、-6、60。第一次统计 73然后疏了 8 和 6剩余应该是 73-8-6 59但最后统计值是 60这不对60 比 59 大说明我算错了。实际上重新统计的意思是“当前树上实际有多少苹果”而不是“疏果后的理论值”。如果统计值是 60而之前是 73疏了 14 个理论上应该是 59但实际是 60这不可能。所以更合理的理解是统计值直接覆盖当前苹果数而掉落判断是看这次统计值是否小于上次统计值。让我重新理一下逻辑。正确的理解应该是维护一个变量current表示当前树上的苹果数。遇到正数 x 时如果current已经被初始化过即之前有过统计并且 x current则说明发生了掉落然后更新current x。遇到负数或零 y 时current yy 是负数所以是减少。用这个逻辑重新看第一棵树初始 current 未初始化。遇到 73current 未初始化直接设 current 73。遇到 -8current 73 - 8 65。遇到 -6current 65 - 6 59。遇到 60current 已初始化且 60 59不60 59所以不掉落更新 current 60。最终这棵树剩余 60 个。等等这里有个问题如果统计值 60 大于理论值 59说明什么说明我之前的疏果计算可能有问题或者统计值就是权威的。题目没有说统计值一定小于等于理论值它只说“如果统计值小于上次统计值则发生掉落”。所以 60 59 的情况下不掉落直接以 60 为准。这个逻辑我反复确认过是符合题目描述的。关键在于统计值是权威的它直接覆盖当前苹果数掉落判断只比较相邻两次统计值。2.2 三个输出量的计算逻辑搞清楚输入处理之后三个输出量的计算就清晰了。T最后剩下的苹果总数每棵树处理完后把最终的 current 累加起来就是 T。这个最简单没什么坑。D发生掉落的树的棵数用一个布尔数组drop[n]来标记每棵树是否发生过掉落。在处理每棵树的过程中一旦检测到掉落就把drop[i]设为 true。最后统计 true 的个数就是 D。E连续三棵都掉落的组数这是最容易出错的地方。题目要求的是“连续三棵都发生掉落”的组合数而且是环形的。也就是说如果第 n 棵、第 1 棵、第 2 棵都掉落这算一组。如果第 n-1 棵、第 n 棵、第 1 棵都掉落也算一组。用代码表达就是对于 i 从 0 到 n-1如果drop[i] drop[(i1)%n] drop[(i2)%n]则 E 加一。这里的%n就是取模运算用来实现环形索引。比如 n5i3 时(31)%54(32)%50正好对应第 4、5、1 棵。这个逻辑看起来简单但有一个隐藏的坑当 n 3 时E 应该为 0。因为不可能有三棵不同的树连续掉落。如果 n1 或 n2即使 drop 数组全是 true也不应该计数。不过题目通常保证 n 足够大但严谨起见还是加个判断比较好。还有一个细节如果所有树都掉落E 应该等于 n。因为对于每个 idrop[i]、drop[i1]、drop[i2] 都为 true所以有 n 组。这个在 n3 时特别明显三棵树都掉落E3因为 (0,1,2)、(1,2,0)、(2,0,1) 都是连续三棵。2.3 为什么用布尔数组而不是计数器有人可能会想我能不能不用数组直接用一个变量记录连续掉落的长度比如遍历的时候维护一个consecutive计数器遇到掉落就加一遇到不掉落就清零然后判断是否达到 3。这个思路在非环形的情况下是可行的但在环形情况下会很麻烦因为你需要处理跨过末尾的情况。用布尔数组的好处是先把所有树的状态确定下来然后再统一处理环形判断。这样逻辑清晰不容易出错。而且布尔数组占用的空间很小n 最多也就 1000 左右CSP 第二题的数据规模通常不大完全不用担心内存问题。我在实际做题时习惯先把所有树处理完把 drop 数组填好然后再单独写一个循环算 E。这样代码结构清晰调试也方便。如果一边处理输入一边算 E很容易因为状态还没确定而算错。3. 代码实现与关键细节3.1 完整代码框架与逐行解析下面是我自己写的 C 实现风格偏向清晰易读适合考试时快速写出并且不容易出错。#include iostream #include vector using namespace std; int main() { int n; cin n; vectorbool drop(n, false); long long T 0; for (int i 0; i n; i) { int m; cin m; long long current -1; // -1 表示尚未初始化 bool dropped false; for (int j 0; j m; j) { long long x; cin x; if (x 0) { if (current ! -1 x current) { dropped true; } current x; } else { current x; } } T current; drop[i] dropped; } int D 0; for (int i 0; i n; i) { if (drop[i]) D; } int E 0; if (n 3) { for (int i 0; i n; i) { if (drop[i] drop[(i1)%n] drop[(i2)%n]) { E; } } } cout T D E endl; return 0; }这段代码有几个关键点值得展开说。第一current初始化为 -1用来表示“尚未进行过统计”。为什么不用 0因为 0 可能是一个合法的统计值虽然题目中苹果数通常为正但严谨起见还是用 -1 更安全。当遇到第一个正数时current -1直接赋值不做掉落判断。第二current用long long而不是int。虽然 CSP 第二题的数据规模通常不会超过 int 范围但苹果总数累加可能会比较大用 long long 更保险。这是一个习惯问题考试时多写几个字符不会浪费时间但能避免溢出导致的 WA。第三drop数组用vectorbool而不是bool[]。vectorbool是 C 标准库的特殊特化每个元素只占一个 bit空间效率高。不过它也有一些坑比如不能取地址但在这个场景下完全够用。如果你不习惯用vectorbool用vectorint或者普通的bool数组也完全可以。第四E 的计算中(i1)%n和(i2)%n实现了环形索引。当 i n-1 时(n-11)%n 0(n-12)%n 1正好对应第 1 棵和第 2 棵。这个取模技巧在处理环形数组时非常常用值得记住。3.2 输入处理的注意事项这道题的输入有一个容易踩坑的地方每行的第一个数 m 是操作数个数但它本身不是操作。我在第一次做的时候差点把 m 也当成一个操作数处理了。后来仔细读题才发现m 只是告诉你后面有几个数。另外输入中可能有多个正数。比如一棵树可能先统计一次疏果再统计一次再疏果再统计一次。每次统计都要和上一次统计比较。所以current的更新逻辑必须是遇到正数时先判断是否掉落再更新current。顺序不能反否则比较的就是同一个值了。还有一个细节如果一棵树只有一次统计那么它不可能发生掉落。因为掉落需要至少两次统计来比较。这个逻辑在代码中自然满足第一次遇到正数时current -1不会触发掉落判断。3.3 环形判断的边界情况环形判断的边界情况主要有两个。第一个是 n 3 的情况。如果 n 1那么(i1)%n和(i2)%n都会等于 i也就是说判断的是drop[i] drop[i] drop[i]这显然不对。所以必须加if (n 3)的判断。虽然题目通常保证 n 足够大但养成处理边界的习惯是好的。第二个是当所有树都掉落时E 应该等于 n。这个在前面已经分析过了。用取模的方式计算结果自然就是 n不需要特殊处理。第三个是当 n 3 且只有两棵树掉落时E 应该为 0。因为连续三棵都掉落需要三棵不同的树只有两棵掉落时不可能满足。用取模方式计算比如 drop [true, true, false]i0 时 drop[0]drop[1]drop[2] truetruefalse falsei1 时 drop[1]drop[2]drop[0] truefalsetrue falsei2 时 drop[2]drop[0]drop[1] falsetruetrue false。所以 E0正确。4. 常见错误与调试技巧4.1 为什么你的 D 和 E 总是对不上这是这道题最高频的问题。很多人写完代码样例过了但提交上去 D 或 E 不对。根据我的经验原因通常集中在以下几个地方。错误一把疏果当成掉落。这是最典型的误解。题目说的是“统计值小于上次统计值”才算掉落而不是“出现负数”就算掉落。疏果是正常操作不掉苹果的树也会疏果。如果你把负数当成掉落信号D 会偏大。错误二忘记更新 current。有些人检测到掉落后忘记把 current 更新为新的统计值导致后续比较用的是旧值。比如 current73遇到 60检测到掉落但 current 还是 73下次遇到 50又检测到掉落50 73但实际上 50 60 才是正确的比较。这个错误会导致 D 偏大。错误三E 的计算没有取模。有些人写 E 的时候直接判断drop[i] drop[i1] drop[i2]没有处理 i1 和 i2 超出 n-1 的情况。这样当 i n-2 或 n-1 时会访问越界或者漏算。正确的做法是用(i1)%n和(i2)%n。错误四n 3 时没有特判。虽然题目通常保证 n 足够大但如果你写的是通用代码最好加上if (n 3)的判断。否则当 n 1 时E 可能会被错误地算成 1。错误五T 的计算用了 int。如果苹果总数很大int 可能会溢出。虽然 CSP 第二题的数据规模通常不会让 int 溢出但用 long long 更保险。4.2 用样例和自造数据验证CSP 官方通常会提供样例输入和输出。以 201909-2 为例官方样例是这样的4 4 74 -7 -12 -5 5 73 -8 -6 59 -4 5 76 -5 -10 60 -2 5 80 -6 -15 59 0输出应该是222 1 0我来手动验证一下。第一棵树74然后 -7、-12、-5最终 74-7-12-5 50。没有第二次统计不掉落。第二棵树73-8、-6然后 5959 73-8-6 5973-8-6 5959 不小于 59所以不掉落。然后 -4最终 59-4 55。第三棵树76-5、-10然后 6076-5-10 6160 61掉落然后 -2最终 60-2 58。第四棵树80-6、-15然后 5980-6-15 5959 不小于 59不掉落。然后 0最终 590 59。T 50 55 58 59 222。D 1只有第三棵树掉落。E 0只有一棵树掉落不可能有三棵连续。和官方输出一致。除了官方样例我建议自己造几组边界数据。比如 n3 且三棵树都掉落的情况3 3 50 -10 30 3 60 -20 30 3 70 -30 30第一棵树50-1030。50-104030 40掉落。最终 30。第二棵树60-2030。60-204030 40掉落。最终 30。第三棵树70-3030。70-304030 40掉落。最终 30。T 90D 3E 3因为三棵树都掉落环形组合有三种。再比如 n4 且只有第 4、1、2 棵掉落的情况4 3 50 -10 30 3 60 -20 30 2 70 -10 3 80 -30 40第一棵掉落第二棵掉落第三棵不掉落只有一次统计第四棵掉落80-305040 50。drop [true, true, false, true]。E 的计算i0: drop[0]drop[1]drop[2] truetruefalse falsei1: drop[1]drop[2]drop[3] truefalsetrue falsei2: drop[2]drop[3]drop[0] falsetruetrue falsei3: drop[3]drop[0]drop[1] truetruetrue true。所以 E1。这个例子验证了环形判断的正确性。4.3 常见问题速查表问题现象可能原因排查方法D 偏大把疏果当成掉落检查掉落判断是否只比较统计值D 偏小忘记更新 current检查每次遇到正数是否更新了 currentE 偏小没有取模检查 i1 和 i2 是否用了 %nE 偏大n3 时没有特判加 if (n3) 判断T 错误current 初始化不当检查 current 是否用 -1 表示未初始化运行错误数组越界检查取模是否正确n 是否可能为 0提示这道题的输入规模通常不大n 最多几百到一千每棵树的操作为几十个。所以 O(n*m) 的暴力模拟完全够用不需要考虑优化。把精力放在逻辑正确性上而不是性能优化。5. 从这道题延伸出的编程思维5.1 状态标记模式的实际应用这道题用布尔数组标记每棵树是否掉落然后基于这个标记做后续判断。这种“先标记后处理”的模式在实际开发中非常常见。举个例子在电商系统中你可能需要标记哪些订单是“异常订单”比如超时未支付、退款、投诉等然后基于这些标记做后续的统计和风控。如果一边遍历订单一边做判断逻辑会变得很复杂但如果先遍历一遍把所有异常订单标记出来然后再统一处理代码会清晰很多。再比如在游戏开发中你可能需要标记哪些怪物是“精英怪”然后基于这个标记计算掉落奖励。同样的思路先标记后处理。这种模式的核心价值在于分离关注点第一遍只负责确定状态第二遍只负责基于状态做计算。两遍的逻辑互不干扰调试起来也方便。5.2 环形数组的处理技巧环形数组的取模技巧是这道题的另一个亮点。(i1)%n和(i2)%n这种写法在处理环形缓冲区、循环队列、环形链表等场景时都会用到。比如在实现一个环形缓冲区时写入指针和读取指针都需要用取模来循环。在实现约瑟夫环问题时也需要用取模来处理环形索引。甚至在一些游戏逻辑中比如“贪吃蛇”的移动蛇头超出边界后从另一边出现也是用取模来实现的。这个技巧的关键在于把线性索引映射到环形空间。公式很简单就是index % n但要用对地方。比如在这道题中我们需要判断“连续三棵”所以需要i、(i1)%n、(i2)%n三个索引。如果是判断“连续两棵”就只需要i和(i1)%n。5.3 模拟题的通用解题框架这道题是一道典型的模拟题。模拟题的通用解题框架可以总结为三步第一步理解规则。把题目描述的现实规则翻译成明确的逻辑条件。比如“统计值小于上次统计值”就是掉落的条件“连续三棵都掉落”就是 E 的条件。第二步设计数据结构。选择合适的数据结构来存储中间状态。比如这道题用了布尔数组来存储掉落标记用 long long 来存储当前苹果数。第三步按规则实现。按照规则一步步实现注意边界情况和特殊输入。比如 n3 的情况、只有一次统计的情况、所有树都掉落的情况。这个框架适用于大多数模拟题包括 CSP 中的其他题目。我个人的经验是模拟题不难但容易出错。出错的原因通常不是算法不会而是规则没理解清楚或者边界没处理好。所以做模拟题时一定要多读几遍题目把规则用自然语言写下来然后再翻译成代码。6. 一些实战中的经验之谈6.1 考试时的代码风格建议CSP 认证考试是有时间限制的通常 4 小时做 5 道题。第二题属于中等难度建议在 30-40 分钟内完成。所以代码风格要偏向“快速写出且不易出错”而不是“优雅但复杂”。我的建议是变量名用简短的英文单词比如n、m、T、D、E、drop、current。不要用太长的变量名浪费时间。但也不要太短比如a、b、c容易搞混。输入输出用cin和cout就够了不需要用scanf和printf。虽然cin和cout稍慢但 CSP 第二题的数据规模通常不会卡这个。如果你担心性能可以在main函数开头加ios::sync_with_stdio(false); cin.tie(0);这个习惯很好几乎不增加代码量。数组大小要留有余量。比如 n 最多 1000你可以开 1005 的数组。这样即使题目数据稍微超出预期也不会越界。6.2 调试时的实用技巧如果你写完代码发现样例过了但提交不对可以试试以下调试技巧。技巧一打印中间状态。在处理每棵树的时候打印出current的变化和dropped的值。这样你可以清楚地看到每棵树的处理过程快速定位问题。技巧二构造小规模测试数据。比如 n3每棵树只有两个操作数。手动计算预期输出然后和程序输出对比。小规模数据更容易手动验证。技巧三检查取模运算。如果 E 不对重点检查(i1)%n和(i2)%n的计算。你可以单独写一个小循环打印出每个 i 对应的三个索引看看是否正确。技巧四检查 current 的初始化。如果 D 不对重点检查current是否用 -1 初始化以及第一次遇到正数时是否正确处理。6.3 这道题对后续题目的启发“小明种苹果续”虽然是一道独立的题目但它涉及的一些技巧在后续题目中会反复出现。比如“环形判断”这个技巧在后面的题目中可能会以“环形数组”、“循环队列”等形式出现。再比如“状态标记”这个模式在涉及多条件判断的题目中非常常见。我个人的经验是CSP 的前两道题通常是“打基础”的题目考察的是基本的编程能力和逻辑思维。把这些题目吃透后面的难题才有基础。所以不要觉得第二题简单就跳过认真做一遍把每个细节都搞清楚对后续的解题能力提升很有帮助。另外这道题也提醒我们读题要仔细。题目中的每一个条件都有用比如“环形”这个条件如果忽略了E 就会算错。再比如“统计值小于上次统计值”这个条件如果理解成“出现负数”D 就会算错。所以做模拟题时宁可多花几分钟读题也不要急着写代码。最后分享一个我自己的习惯做完一道题后我会把解题思路和踩过的坑简单记下来。比如这道题我会记“掉落判断看统计值变化不是看负数E 要取模n3 要特判。”这样下次遇到类似的题目翻一下笔记就能快速回忆起来。这个习惯坚持下来解题速度和正确率都会有明显提升。
