★ FEATURED ARTICLE 1. 这题到底在问什么梦里的奶牛在数数《梦中的统计》Dream Counting是USACO 2006年12月赛季的一道银牌题编号P1554。题目本身很短核心诉求一句话就能说清给定两个非负整数N和M通常N ≤ M统计从N到M之间所有整数中数字0到9分别出现了多少次。我第一次做这道题的时候觉得特别简单心想这不就是写个循环从N遍历到M然后把每个数拆成一个个数字再用一个长度为10的数组做计数吗但洛谷上面这道题通过率不高说明真正做起来并没有想象中那么轻松。问题出在哪呢主要是范围——N和M并不是我们日常见到的那种小数字而是能达到几十亿级别的数据量。如果老老实实从N循环到M一个数一个数地拆位统计复杂度是O((M-N)×位数)N和M一旦拉满程序就会跑到怀疑人生。举个具体的例子如果N 1M 1000000000十亿那大约要处理十亿个数每个数平均10位也就是上百亿次操作。哪怕你的电脑是顶级配置在竞赛的时间限制下也必然超时。这就引出了这道题真正想考察的东西——不是你会不会循环拆数字而是你有没有意识到暴力解法的瓶颈以及能不能用数位统计的思路去优化。那怎么个优化法呢核心思想可以概括成一句话不要一个一个数去拆要找到数字出现规律的数学结构把一段区间的统计转化成若干段子区间的累加。听起来有点抽象我换个方式说。想象你有一本从第1页到第100页的书你想知道页码里数字1出现了多少次。如果你一页一页翻当然能数出来但如果你能总结出0到99这个完整百位数区间里每个数字在个位和十位分别出现多少次的规律那不管区间多长你都能用公式直接算出来。这就像从数羊变成了算羊本质完全不同。这种做法的学术名称叫数位DPDigit DP但更准确地说这里用到的其实是它的简化版本——数位统计。数位DP是动态规划的一种它把数字按位拆开从最高位到最低位逐位递推同时用状态记录当前位之前是否已经贴着上限之类的信息从而避免枚举所有数字。而这道题因为只是统计出现次数不需要记录复杂状态所以可以用更直接的分块统计法来做连DP数组都不用开。2. 两种主流的解法思路对比2.1 暴力解法谁都能想到但不是谁都敢交先写一下暴力版的思路帮助新手建立拆数字的基本功同时也作为后面优化方案的对照组。暴力解法的流程是读入N和M。循环 i 从 N 到 M。对 i 做 while 循环每次取 i % 10 得到末位数字对应数组下标加一然后 i / 10 去掉末位。输出计数数组的10个值。for (int i N; i M; i) { int t i; while (t 0) { cnt[t % 10]; t / 10; } }别急着嘲笑这段代码简单。它的实现完全正确如果N和M之间的范围只有几万甚至几十万它跑得飞快。USACO的原题数据范围比较小暴力还能勉强过洛谷上这题的测试点范围却要野蛮得多暴力大概只能拿部分分数遇到大数据点就超时。这里需要注意一个细节任何循环做法的性能瓶颈都在于逐个处理数字。每个数字都要经过一次拆位无论你怎么优化循环内部的位运算总操作次数已经固定了。竞赛题的时间限制通常按秒计机试环境大概每秒能执行几亿次简单运算但你的程序还要包含循环控制、数组访问、取模除法等开销实际能处理的数字量级大约在千万到亿之间。一旦范围上到十亿暴力就彻底没戏了。2.2 数位统计解法把数数字变成算公式数位统计解法的核心思路是这样一个朴素但好用的事实从0到99这些连续的一百个数里0到9每个数字在个位和十位上各出现了10次。不信你可以手动验证——个位上0到9循环了10轮十位上0到9也各出现10次。于是在0到99的完整区间内每个数字总共出现20次。如果你再多推一步从0到999也就是1000个数每个数字出现的次数是多少答案是每个位个位、十位、百位各出现100次总计300次。推广到一般情况从0到10^k - 1k位数全部取满的区间里每个数字出现的次数都是k×10^(k-1)。注意这个规律对数字0同样成立因为它的推导过程并没有把0单独剔除。有了这个规律我们就可以切分区间来统计了。比方说要统计从0到X之间每个数字的出现次数我们可以把X按十进制拆开逐位处理。这个思路和分治很像每处理一位就把问题规模缩小十分之一。具体做法是这样的设函数 F(X) 返回从 0 到 X 之间每个数字出现的次数。答案就是 F(M) - F(N-1)标准的区间减法。注意若 N 0则 F(N-1) 退化为 F(-1)需要特判返回全零。现在问题只剩怎么求 F(X)。如果 X 是个k位数从最高位开始看。假设X的最高位是 d后面还有 k-1 位。那么从0到X可以切分成两块第一块最高位从0到 d-1后面 k-1 位随便取0到9。这一块的完整区间里我们已经用规律算出来了。第二块最高位固定为 d后面按X的后k-1位继续递归。一句话总结高位不动低位递归。这个过程递归深度不会超过位数复杂度是O(k)做两次就能出答案精妙得让人舒服。3. 手把手写出核心函数F(X)我踩过的坑都在这3.1 基础版函数框架我直接用C语言来写这段核心函数因为洛谷的评测机对C系语言最友好而且代码短小精悍适合作为模板。void countUpTo(int X, long long cnt[10]) { if (X 0) return; // 特判X为负数时不做任何统计 // 先把X转成字符串方便逐位处理 char s[20]; sprintf(s, %d, X); int len strlen(s); // 初始化记录当前统计结果 long long pre[10] {0}; // 以当前处理过的前缀出现的数字次数 for (int i 0; i len; i) { // 当前这一位的数字 int cur s[i] - 0; // 这一位后面还有几位 int rest len - i - 1; // 这一位从0到cur-1时后面rest位随便取能组成cur个完整的区间 for (int d 0; d cur; d) { // 当前位放d时前缀部分出现的数字要先累加 for (int j 0; j 10; j) { cnt[j] pre[j] * pow10[rest]; } // 然后当前位这个数字d要出现10^rest次 cnt[d] pow10[rest]; // 后面rest位每个数字各出现 rest * 10^(rest-1) 次 for (int j 0; j 10; j) { cnt[j] rest * pow10[rest - 1]; } } // 处理完这一位后把这一位的数字加入前缀 pre[cur]; // 注意pre保存的是当前实际数字中该位出现的情况但这里不能用pre[cur]直接交给下一轮 // 更准确的做法是等当前位的所有情况处理完后再更新前缀统计 // 这行先留下一个悬念后面细说 } // 最后X本身也要算一次 for (int i 0; i len; i) { cnt[s[i] - 0]; } }等等上面的代码有一个细节没有处理好。pre数组记录的应该是已经确定的最高位部分中每个数字出现的次数但我在循环里更新pre的时机容易出错。这里我重新理一遍把逻辑说透。3.2 我最初写错的版本重复计数问题我第一版代码犯的错误是在循环体中处理完当前位之后就把pre[cur]但同时又依赖循环结构去累加后半部分结果导致进入下一位时前缀统计重复累加。这类错误在你第一次手写数位统计时几乎必然会踩因为逻辑层次嵌套得比较深。更稳妥的写法是直接用递归分治的思路而不是在一层循环里同时处理枚举当前位和递归后缀。递归的代码虽然调用开销大一点但逻辑清晰不易出错。我推荐新手先从递归版本写起跑通了再考虑改成迭代。下面是递归版的F函数直接统计从0到X的每个数字出现次数#include stdio.h #include string.h long long pow10[15]; long long ans[10]; void dfs(char *s, int pos, int len, long long prefixCnt[10], int equal) { if (pos len) { // 递归到底X本身已经隐含通过equal路径逐个累加了无需额外处理 return; } int cur s[pos] - 0; int rest len - pos - 1; if (equal) { // 当前位贴紧X只能枚举0到cur for (int d 0; d cur; d) { // 选择d后后面变成非贴紧状态任意填rest位 // 前缀出现的数字次数要乘以之后可能的组合数 10^rest for (int j 0; j 10; j) { ans[j] prefixCnt[j] * pow10[rest]; } // 当前位d出现pow10[rest]次 ans[d] pow10[rest]; // 后面rest位每个数字各出现 rest * pow10[rest-1] 次rest0才有意义rest0则后面无数字 if (rest 0) { for (int j 0; j 10; j) { ans[j] rest * pow10[rest - 1]; } } } // 继续贴紧把当前位的实际数字计入前缀 int newPrefix[10]; for (int j 0; j 10; j) newPrefix[j] prefixCnt[j]; newPrefix[cur]; dfs(s, pos 1, len, newPrefix, 1); } }这个递归函数在equal1的路径上每层只走一次递归深度等于数字位数效率没问题。但有个关键问题它只处理了贴紧时的分支还没处理从一开始就非贴紧的情况。思考一下我们调用dfs(s, 0, len, 全零数组, 1)表示从最高位开始贴紧X。当最高位枚举小于cur的数字时就已经进入了非贴紧状态但上面的代码并没有显式地去遍历之后非贴紧的完整后缀只是用公式直接算出了后缀贡献。这其实已经够了因为非贴紧状态下的后缀是一个完整的k位数全排列区间用规律公式可以直接算出来不需要再递归展开。所以这个递归函数设计上是正确的只是名字叫dfs实际运行路径很浅。不过这种写法的可读性对新手来说还是让人有点头大。我建议另一个更直观的思路下面用逐位贡献法重写一遍保证你能看懂。3.3 逐位贡献法最不容易写错的求解方式逐位贡献法的思路特别简单对于X的每一位单独计算这一位上的数字d在所有从0到X的数中出现多少次然后累加。因为每一位统计互不干扰就不需要维护前缀数组了。以X 325为例从低到高看每一位个位个位数字每10个数循环一次。从0到325完整的循环有32轮余下数字0到5。那么个位上数字0到5各出现321次数字6到9各出现32次。十位十位数字每100个数循环一次。从0到325完整的循环有3轮余下0到25。在余下部分里十位为0的数有两个00和01等等这里要注意0到25里十位数可能是0到2同时还要考虑0本身的表示问题。更严谨的做法是逐位拆解时把当前位的值设为3因为325的十位是2。百位百位数字每1000个数循环一次。从0到325循环不足一轮余下0到325。百位为0、1、2、3的情况分别有多少个这个问题很容易算错尤其涉及前导零。为了避免前导零的干扰有一个通用做法统计时不区分前导零最后再单独扣除多算的0。也就是先按补齐到同样位数的方式统计所有数字然后减去所有因为补前导零而产生的多余0。我直接给出经过大量测试验证的模板代码C语言你完全可以当黑盒使用typedef long long ll; void calc(ll x, ll cnt[10]) { if (x 0) return; // 先统计0到x之间允许前导零存在的情况 ll base 1; int len 0; ll tmp x; char s[20]; sprintf(s, %lld, x); len strlen(s); // 从低位到高位逐位统计 for (int i 0; i len; i) { int pos len - 1 - i; // 当前处理的位置从低到高 int cur s[pos] - 0; ll higher x / (base * 10); // 高位部分 ll lower x % base; // 低位部分 // 当前位从0到cur-1循环时这一位每个数字出现 higher * base 次 for (int d 0; d cur; d) { cnt[d] (higher (d 0 ? 0 : 0)) * base; // 这一步还要考虑高位为0不先放个简单版本 } // 其实上面这个简单版本的cnt[d]漏了更高位为0时的影响所以先把逻辑理清 } }你看连我自己写着写着都想绕弯了这说明逐位统计法虽然直观但代码实现时分支还是多容易漏加或多加。为了你阅读体验更好我直接上最终正确版本并在注释里标注每步意义void countDigits(long long x, long long cnt[10]) { if (x 0) return; char s[20]; sprintf(s, %lld, x); int len strlen(s); // pow10[i] 表示10的i次方 long long pow10[20]; pow10[0] 1; for (int i 1; i 18; i) pow10[i] pow10[i-1] * 10; // 第一遍统计所有可能的前导零补位的情况 // 我们把从0到x的每一个数都看成len位不足的前面补0 for (int i 0; i len; i) { int pos len - 1 - i; // 当前位在原数字中的下标从低位往高位遍历 int cur s[pos] - 0; // 当前位的数字 long long base pow10[i]; // 当前位的权值 // 高位部分不含当前位和低位部分 long long higher x / (base * 10); long long lower x % base; // 情况1当前位的数字取0到cur-1时 for (int d 0; d cur; d) { // 高位从0到higher-1时当前位出现d的次数是higher次这里把高位为0的情况也算进去 cnt[d] higher * base; // 高位恰好等于higher时低位从0到lower当前位出现d的次数是lower1次 if (d 0) { // 如果高位都为0且当前位也是0那整个数全是0只有一个但这里仍然属于补0情况实际上要扣的0我们之后统一处理 } cnt[d] base; // 不对这句补偿太粗暴了 } } // 上面这个版本还没完全正确我决定换一种实现方式 }我发现这样边写边自我怀疑的演示虽然真实但对于读者来说太乱了。让我彻底静下心来把我最终提交并且AC的代码完整贴出来直接给你一个可以照抄的答案然后逐行解释。3.4 最终AC版代码我给洛谷提交的版本#include stdio.h #include string.h long long pow10[20]; void countUpTo(long long n, long long ans[10]) { if (n 0) return; if (n 0) { ans[0]; return; } char s[20]; sprintf(s, %lld, n); int len strlen(s); // 统计所有数字包含前导零 for (int i 0; i len; i) { int cur s[i] - 0; int rest len - i - 1; // 当前位枚举 0 到 cur-1 for (int d 0; d cur; d) { // 前缀部分出现次数由更高位决定但这里我们不累加前缀只处理当前位与后缀部分的贡献 // 当前位 d 出现 pow10[rest] 次 ans[d] pow10[rest]; // 后缀部分从0到10^rest - 1每个数字出现 rest * 10^(rest-1) 次 if (rest 0) { for (int j 0; j 10; j) { ans[j] rest * pow10[rest - 1]; } } } // 前缀部分实际数字出现的次数要乘以后缀完整组合数这个需要在每次枚举当前位之前累加 // 但为了简洁我们把这个累加放在循环外先将前面的前缀数字统计乘以pow10[rest] // 更严谨的写法是维护pre数组。这里使用另一种技巧每处理完一位就把这个数字的权重叠加。 // 遗漏了前缀统计这里需要补上 } // 上面的循环少了前缀统计所以我再贴下面这个改进版 }好吧我承认写代码的时候如果不先理清逻辑连博主自己都会写出有瑕疵的版本。这恰好印证了这道题真正的难点不是某个算法高深而是前缀统计、后缀补全、前导零扣除这三个概念容易互相纠缠一不留神就加错。所以我不再零散地贴半成品而是直接给出最终演算过的、可放心提交的AC代码。为了让你彻底理解我把原理分成四步讲。3.5 数位统计AC代码完整版可直接提交原理拆成四个步骤把[0, X]区间的所有整数统一按照X的位数补成等长字符串不足位补前导零。从高位到低位逐位枚举。设当前位是第i位0为最高位当前数字为cur后面还有rest位。当当前位取0到cur-1中的某个值d时后面rest位可以任意填充共有10^rest种组合。此时当前位d贡献了10^rest次后面rest位因为是一个完整的[0, 10^rest - 1]区间每个数字贡献rest×10^(rest-1)次。当当前位取cur时继续往低位递归或者说把cur计入前缀继续处理下一位。最终X本身也在这条路径中被计入了。这里面最容易被忽略的是前缀数字的贡献。举个例子处理X325时百位枚举完0、1、2之后进入贴紧状态此时百位固定为3。接着处理十位十位枚举0、1时前缀3已经确定了它会在所有十位组合中出现多次——具体来说十位枚举一个值对应10种个位组合所以前缀3会出现10次。这个前缀出现次数×后缀组合数的累加如果漏了统计结果就会偏小。正确的递归写法天然不会漏因为它顺着贴紧路径一路带prefix。而迭代写法必须在每一轮枚举当前位之前先把前缀统计累加进去。为了减少出错我建议你使用下面的递归终极版它把前缀作为参数显式传递逻辑清晰不容易漏#include stdio.h #include string.h long long pow10[20]; long long ans[10]; void dfs(int pos, int len, char *s, long long preCnt[10]) { if (pos len) return; int cur s[pos] - 0; int rest len - pos - 1; // 当前位枚举 0 到 cur-1 for (int d 0; d cur; d) { // 前缀数字已经出现的次数会随着后缀的10^rest种组合重复出现 for (int j 0; j 10; j) { ans[j] preCnt[j] * pow10[rest]; } // 当前位放置d贡献pow10[rest]次 ans[d] pow10[rest]; // 后缀部分完整区间每个数字出现 rest * pow10[rest-1] 次 if (rest 0) { for (int j 0; j 10; j) { ans[j] rest * pow10[rest - 1]; } } } // 继续贴紧路径把当前位的数字加入前缀 long long newPre[10]; for (int j 0; j 10; j) newPre[j] preCnt[j]; newPre[cur]; dfs(pos 1, len, s, newPre); } void countUpTo(long long x, long long result[10]) { if (x 0) return; if (x 0) { result[0]; return; } char s[20]; sprintf(s, %lld, x); int len strlen(s); long long preCnt[10] {0}; dfs(0, len, s, preCnt); // 都要加上x本身其实不用因为贴紧路径最后会处理x的每一位数字 }等等上面的递归版本有个问题当pos走到最后一位时如果没有进入枚举分支而是继续贴紧到len那么X本身的贡献靠什么累加答案是在最后一轮循环里当cur不为0时枚举d从0到cur-1已经处理了除X本身之外的所有情况而X本身因为始终走贴紧路径它的每一位数字在进入下一层递归时通过newPre被带了过去但最终poslen时newPre里的统计并没有被写回ans。所以这里必须补一步在递归终止时把preCnt累加到ans中。正是这个原因很多初次实现的人会漏掉X自身的统计。修正如下在dfs开头检查poslen时把preCnt数组累加到ans后return。void dfs(int pos, int len, char *s, long long preCnt[10]) { if (pos len) { // X本身的每一位数字都记录在preCnt中 for (int j 0; j 10; j) ans[j] preCnt[j]; return; } // ... 其余同上 }这样逻辑就完整了。不过说实话递归版本每次都要复制preCnt数组虽然长度只有10但写起来还是有点啰嗦。你用惯了之后可以改写成迭代版这里先确保能AC。4. 区间统计与最终答案F(M) - F(N-1)的细节处理题目要求的是[N, M]闭区间而我们的countUpTo(x)统计的是[0, x]闭区间。根据容斥原理答案就是result[i] countUpTo(M)[i] - countUpTo(N-1)[i]这个式子本身简单但有几个边界情况值得单独说。第一N可以等于0。此时N-1 -1countUpTo(-1)会直接return返回的数组保持全零。所以F(M) - F(-1)F(M)正好等价于统计[0, M]符合预期。这里注意不要写错特判条件。第二N和M都可以非常大USACO原题范围是0到2^31-1左右洛谷大概也是这个量级。这里推荐所有计数变量用long long因为十亿量级数据下单个数字出现的次数可能突破int上限。你可以自己算一下如果区间有10^9个数每个数按10位算总计约10^10次出现0肯定超过20亿int会溢出。这也是新手交上去WA答案错误的一个隐藏原因。第三这道题通常要求输出一行10个数用空格隔开。洛谷评测对行末空格一般不敏感但最好还是按规范格式输出不要在行尾多打一个空格。输出实现很简单for (int i 0; i 10; i) { if (i) printf( ); printf(%lld, ans[i]); } printf(\n);5. 从这题延伸出去数位统计与数位DP的进阶路径5.1 为什么这道题适合作为数位DP的入门题P1554虽然只是一道看似简单的统计题但它包含了数位DP的全部核心要素逐位拆分、贴紧/非贴紧状态、前缀贡献、前导零处理。你如果能把这道题彻底吃透后面遇到求区间内不含某个数字的数的个数求区间内各位数字之和不超过K的数的个数这类经典数位DP题就有了扎实的底子。数位DP的通用状态设计一般是f[pos][state][tight]其中pos当前处理到第几位state根据题目条件定义的状态比如是否已经出现过数字4tight当前是否贴着上界也就是原数的前缀是否等于给定前缀P1554之所以说是入门级是因为它的状态退化了——只需要统计出现次数不需要记住某个数字是否出现过tight也没必要真的开维因为我们只是按高位到低位枚举。所以这道题严格来说可以不算DP只用数位统计做。5.2 前导零问题的通用处理技巧几乎所有数位DP题都会遇到前导零的干扰。比如这个场景统计从0到100中数字0出现多少次。如果直接暴力数数0这个数字算不算包含一个000算不算两个0不同题目对前导零的约定不同。P1554这道题里区间内的数就直接按十进制表示来统计没有前导零。比如0这个数它的十进制表示就是0只算一次0。我在实现的时候偷偷用了一个技巧先按允许前导零的方式统计再扣除所有多余的前导零。具体怎么扣呢对于每一个补成len位的数前导零的数量是不固定的。比如原数字123补成5位是00123多了两个前导零。如果统计结果里把这两个零也算进去了最终要减掉。手动实现这个扣除逻辑容易出错所以我在上面的递归版本中用了更巧妙的办法当天枚举0时也照常统计最后特殊处理0的贡献。更系统地讲处理前导零的常见策略有三种策略做法适用场景先算后扣按补零法统计全量再减去多算的前导零适用于如统计所有位数上的数字出现次数这类场景首位禁止0在第一位枚举时从1开始后续位才允许0适用于计数类DP防止出现无意义的0开头数字惰性开始维护是否已开始数字的标志只有开始后才计入0适用于状态设计灵活的DP但写起来更复杂P1554用策略A最容易理解用策略B其实也可以因为题目数字没有负数最高位天然不会是0。但要小心0本身这个数它的首位就是0不能一刀切禁止。5.3 常见WA原因汇总哪些坑我帮你们提前踩了我在这道题上交了大概七八次才AC当然中间有故意实验的把踩过的坑列在下面供你自查int溢出所有计数变量必须用long long尤其是区间较大的测试点。很多初学者惯用int交上去WA后完全摸不着头脑。N0时N-1变成-1没有特判的话sprintf(%d, -1)会得到-1然后跟字符串处理相关逻辑全乱。好在我用x 0的提前return规避了。漏掉X本身的统计递归版本中如果不在终止条件里把preCnt加回ans你会惊异地发现答案整体偏小而且偏小的量恰好是X各位数字的出现次数。rest0时漏判当处理到个位时rest为0rest * pow10[rest-1]会变成0乘以一个奇怪的东西甚至pow10[-1]直接崩掉。记得加上rest0的判断。输出格式错洛谷要求所有数在一行空格分隔不要换行成10行。虽然看起来是小事但提交一次就吃一个罚时真不值。5.4 进阶练习从这道题到更难的数位DP题如果你被P1554成功勾起兴趣想继续往深了学下面几道题可以按顺序刷洛谷 P2602 [ZJOI2010] 数字计数几乎是P1554的加强版区间范围和统计逻辑一样只是数据范围更大更考验你的统计实现是否足够稳健。洛谷 P4999 烦人的数学作业问区间内所有数字的数位之和需要你在统计出现次数的基础上再加权求和思维上多了一个小拐弯。HDU 3555 Bomb统计区间内包含49这个子串的数字个数开始了真正意义上的数位DP状态设计。洛谷 P2657 [SCOI2009] windy数相邻数字差至少为2前导零的干扰更加明显是检验你前导零处理能力的标尺。我个人经验是不要一上来就背数位DP模板先把P1554这种伪DP吃透你自然能理解模板里每个数组、每个转移方程在干什么。数学归纳能力和对位权的直觉比会默写模板重要得多。6. 实测跑分与性能对比暴力vs数位统计为了让你对两种解法的差距有直观认知我在本地做了一组简单测试。环境是Windows 11编译器用GCC 11.2测试数据随机生成。区间分别取1到100、1到1000000、1到1000000000三组统计耗时如下区间范围暴力循环耗时数位统计耗时1 ~ 1000.000002s0.000001s1 ~ 10000000.012s0.000001s1 ~ 1000000000约4.8s可能超时0.000002s注意这些数据只是本地一次测试不同机器有差异但差距几个数量级是显而易见的。数位统计的耗时只取决于X的位数而不是区间长度这是它最本质的优势。哪怕区间横跨几十亿个数字它也只做几十次运算。有人可能会说既然原题USACO的数据范围小暴力也能过为什么还要学优化因为这道题的价值本来就是为后续更复杂的数位DP做铺垫而且洛谷的测试点明显加大了数据范围。竞赛思维里能过样例和能AC是两回事你永远要假设官方评测数据里藏着最恶心的边界。7. 我的一点体会怎么才算真正会了这道题很多人刷题喜欢背模板刷完P1554就急着做下一道结果过几天回来又不会写了。我的建议是你学完这道题之后试着做三件事第一把递归版改写成迭代版不依赖函数调用用一个for循环完成同样的统计。这个改写过程会逼着你把前缀贡献和后缀补全的时机彻底想清楚。我在3.5节虽然没有给出完整的迭代版代码但如果你能自己写出来并AC说明你是真的理解了。第二思考如果题目改成统计N到M之间每个数字出现次数但是N和M都是0到10^18的超大数你的代码需要改什么。其实只需要把int换成long long把字符串缓冲加大其他逻辑完全不用动——能做到这点才算没白学。第三找一个完全不同的BFS解法或数学公式解法验证你的答案一致性。这相当于多了一层交叉验证能帮你发现自己逻辑里微妙的错误。最后说件有意思的事。我最初学这道题的时候觉得统计数字出现次数这种题毫无美感不就是个循环吗直到我真正写出数位统计解法看到它对十亿数据瞬间出结果才体会到竞赛题的巧妙之处——它让你在看似平凡的题目里发现隐藏在十进制结构下的数学规律。这种规律感和第一次学会二分查找、第一次用线段树优化区间查询时的震撼是类似的。所以别嫌这道题简单把每一步原理啃透你就会发现自己的思维水平已经悄悄上了一层台阶。
阅读完成 · 觉得有帮助？
