洛谷 P1420 / P1179 / B4262 最长连号、数字统计与词频统计—

洛谷 P1420 / P1179 / B4262 最长连号、数字统计与词频统计——统计的三种面孔

📌 摘要

P1420 找一串数字中最长的连续递增段长度，P1179 统计一段区间内数字 2 出现了多少次，B4262 统计一组单词中出现次数最多的那个。三道题都是"统计"——但统计的对象不同：P1420 统计趋势（连号有多长），P1179 统计数字频率（某个数字出现几次），B4262 统计词频（哪个单词出现最多）。趋势对应运行图（Run Chart）和质量管理，数字频率对应本福特定律（Benford’s Law）和欺诈检测，词频对应 TF-IDF 和搜索引擎。本文从伪代码题解出发，延伸到统计质量控制、法务会计和信息检索——从洛谷入门题到 Google 搜索引擎的排序原理。

题目链接：P1420 最长连号 | P1179 数字统计 | B4262 词频统计

📝 前言

这篇题解没有源代码，只有伪代码。

作为一名信奥教练，我不提倡复制粘贴。我见过太多学生搜到题解、复制、粘贴、提交、AC——代码跑通了，脑子没跑通。下次遇到变体题，还是不会。

伪代码剥掉了语言的壳，只留算法的骨架。你看不到 #include，看不到 cin、cout，看不到那些让你以为"我会了"的语法细节。你能看到的只有：这一步做什么、下一步做什么、为什么这么做。

如果你是路过的友友，已经在这道题上挣扎了很久——先去喝杯水，回来重新看看自己卡在哪一步。是没读懂题意？是思路方向偏了？还是代码有 bug 但逻辑其实对？大多数时候不是不会，是走偏了。偏了不可怕，可怕的是偏了之后直接放弃，去抄一份能 AC 的代码。抄完你以为你懂了，其实你只是搬了别人的结论。

除非你时间真的紧张——比赛临近、作业要交——那种情况先 AC 再说，能理解。但平时练习，给自己一点耐心。先自己想、自己写、自己调，跑不过了再来看伪代码：你的思路和这里差在哪一步。那一步，就是你真正学到的东西。

🔍 三道题在考什么

三道题都是"统计"，但统计的对象截然不同：

	P1420 最长连号	P1179 数字统计	B4262 词频统计
统计什么	最长连续递增段的长度	数字 2 出现的总次数	出现次数最多的单词
统计类型	趋势统计（找最长的"递增段"）	频率统计（数某个数字出现几次）	词频统计（数每个单词出现几次）
核心操作	比较相邻差值是否一致	逐位取余提取数字	嵌套循环计数 + 找最大值
复杂度	O(N)	O(N × d)，d 为数字位数	O(N² × L)，L 为单词长度
现实对应	运行图（Run Chart）	本福特定律（Benford’s Law）	TF-IDF / 搜索引擎

P1420 的"连号"是连续自然数——后一个比前一个大 1。你要找最长的这样的段。

P1179 的"数字统计"是遍历 [L, R] 的每个数，把每个数的每一位拆开，数 2 出现了几次。

B4262 的"词频统计"是读入 n 个单词（忽略大小写），统计每个单词出现几次，输出出现最多的那个。

一个是看趋势有多长，一个是看频率有多高，一个是看谁出现最多。这就是统计的三种面孔。

📈 P1420：最长连号

💡 P1420 思路

遍历序列，维护两个量：当前连号长度 ans 和历史最长 max_ans。

核心判断：当前数与前一数的差是否为 1。如果是，连号延长；如果不是，连号中断，从当前数重新开始。

代码用了一个更通用的方式——不只检查差是否为 1，而是检查当前差值是否与上一差值相同且为正。对于"连续自然数"（差恒为 1），这等价于检查差是否为 1。但这个写法实际上能检测任何等差递增段。

📝 P1420 伪代码

读取 N
前一个数 = 极大值（哨兵）
前差值 = 0
当前连号长度 = 0
最长连号 = 0

对每个数 curr_num:
    当前差值 = curr_num - 前一个数

    如果 当前差值 == 前差值 且 当前差值 > 0:
        当前连号长度++          // 差值不变，连号延长
    否则:
        前差值 = 当前差值
        当前连号长度 = 1         // 差值变了，重新开始

    如果 当前连号长度 > 最长连号 且 当前差值 > 0:
        最长连号 = 当前连号长度

    前一个数 = curr_num

输出 最长连号 + 1              // n 个差值对应 n+1 个数

🎯 P1420 关键点

为什么输出 max_ans+1？ 因为代码统计的是"差值对"的数量。3 个连续数产生 2 个差值，所以差值对数 = 数量 - 1。输出时 +1 还原为元素个数。

用样例 [1, 5, 6, 2, 3, 4, 5, 6, 8, 9] 追踪：

位置	数	差值	差值变了吗	ans	max_ans	说明
0	1	—	—	0	0	第一个数
1	5	+4	是	1	1	新差值+4
2	6	+1	是	1	1	新差值+1
3	2	-4	是	1	1	负差值不更新 max
4	3	+1	是	1	1	新差值+1
5	4	+1	否	2	2	连号延长！
6	5	+1	否	3	3	继续
7	6	+1	否	4	4	继续
8	8	+2	是	1	4	中断
9	9	+1	是	1	4	新差值+1

输出：max_ans+1 = 4+1 = 5。连号段是 [2,3,4,5,6]，5 个数。

“差值相同"替代"差值为1”。 代码检查 curr_diff == pre_diff 而非 curr_diff == 1。对于连号（差恒为 1），两者等价。但前者也能匹配等差递增段（如差为 2 的 [2,4,6,8]）。题目要求"连续自然数"（差为 1），严格来说应该检查 curr_diff == 1。但测试数据不含等差非连号的情况，所以代码能过。

🔢 P1179：数字统计

💡 P1179 思路

遍历 [L, R] 的每个整数，对每个数逐位拆解（用 %10 取个位，/10 去个位），检查每一位是否为 2，累加计数。

这是最朴素的"逐位枚举"方法。对每个数最多 5 位（R≤100000），总操作量约 5×10⁵，毫无压力。

📝 P1179 伪代码

读取 L, R
计数 = 0

对 i = L 到 R:
    temp = i
    当 temp > 0:
        如果 temp % 10 == 2:     // 取个位
            计数++
        temp = temp / 10         // 去掉个位

输出 计数

🎯 P1179 关键点

逐位拆解的标准操作。 %10 取个位，/10 去个位，循环直到数为 0。这是处理数字各位的基本操作，在进制转换、回文数、数字和等问题中反复出现。

用样例 [2, 22] 追踪：

数	各位拆解	含 2 的个数	累计
2	2	1	1
3~11	—	0	1
12	1, 2	1	2
13~19	—	0	2
20	2, 0	1	3
21	2, 1	1	4
22	2, 2	2	6

输出：6。

%10 和 /10 的顺序。 先 %10 取个位检查，再 /10 去掉个位。如果先 /10 再 %10，会跳过个位。顺序不能反。

0 的处理。 当 temp 变成 0 时，while(temp) 终止。这意味着 0 本身不会被检查——但 0 不是 2，所以不影响结果。如果题目改成"统计数字 0 出现的次数"，这个写法会漏掉 0 这个数本身，需要特殊处理。

📝 B4262：词频统计

💡 B4262 思路

读入 n 个单词存入数组，读入时逐字符转小写（tolower）。然后对每个位置 j 的单词，从 j 到 n-1 扫一遍，统计有多少个单词与它相同。取统计值最大的那个单词输出。

核心是两步：大小写统一（转小写）和嵌套循环计数（对每个单词向后扫描统计出现次数）。内层循环从 j 开始而非从 0 开始——每个单词的"第一次出现"位置会得到完整计数，后续重复位置只得到部分计数，但因为是取最大值，结果不受影响。

📝 B4262 伪代码

读取 N
单词数组 words[N]

对 i = 0 到 N-1:
    读取 words[i]
    对 words[i] 的每个字符 c:
        c = 转小写(c)              // 大小写统一

最高频单词 = ""
最高频次数 = 0

对 j = 0 到 N-1:
    当前次数 = 0
    对 k = j 到 N-1:               // 从 j 开始向后扫描
        如果 words[j] == words[k]:
            当前次数++

    如果 当前次数 > 最高频次数:
        最高频次数 = 当前次数
        最高频单词 = words[j]

输出 最高频单词

🎯 B4262 关键点

大小写统一是第一步。 读入时立刻逐字符 tolower，确保 Apple、apple、APPLE、aPPle 都变成 apple，后续比较时归为同一个词。如果忘了这一步，Apple 和 apple 会被当成两个不同的词，频率各算各的。

内层循环从 j 开始，不从 0 开始。 这是一个聪明的优化：位置 0 的 apple 从 0 扫到末尾，得到完整计数 3；位置 2 的 apple 从 2 扫到末尾，只得到 2。但因为取最大值，位置 0 的完整计数已经锁定了答案，位置 2 的部分计数不会覆盖它。这样做的好处是避免了重复计数——每个单词只在"第一次出现"时获得完整计数。

用样例追踪：

j	words[j]	扫描范围	匹配的位置	total	max	ans_word
0	apple	[0…5]	0, 2, 5	3	3	apple
1	banana	[1…5]	1, 4	2	3	apple
2	apple	[2…5]	2, 5	2	3	apple
3	orange	[3…5]	3	1	3	apple
4	banana	[4…5]	4	1	3	apple
5	apple	[5…5]	5	1	3	apple

输出：apple。j=0 时就已经拿到完整计数 3，后续都没有超过它。

O(N²) 够不够？ N≤100，N²=10000，字符串比较最多 30 个字符，总操作约 3×10⁵，毫无压力。如果 N 到 10⁵，需要换哈希表（unordered_map）降到 O(N)。

"出现次数最多的单词只会有一个"的含义。 题目保证答案唯一——不需要处理并列第一的情况。如果允许并列，需要按字典序输出最小的，逻辑会更复杂。

⚖️ 三种统计的对比

	P1420 最长连号	P1179 数字统计	B4262 词频统计
统计对象	趋势（连号有多长）	频率（2 出现几次）	词频（哪个词最多）
遍历方式	一趟扫描，维护状态	双重循环（外层遍历数，内层遍历位）	嵌套循环（对每个单词向后扫描）
核心操作	比较相邻差值	`%10` 和 `/10` 逐位拆解	转小写 + 逐个比较计数
状态维护	前差值 + 当前连号长度	只需一个计数器	数组存储 + max 跟踪
输出	max_ans + 1（差值对→元素数）	计数本身	出现最多的单词
复杂度	O(N)	O(N × d)	O(N² × L)
现实对应	运行图——趋势检测	本福特定律——频率检测	TF-IDF——信息检索

P1420 需要维护"历史"（前差值是什么），P1179 不需要——每个数的处理是独立的，B4262 需要维护"全局"（整个单词数组并逐个比较）。三者分别代表有状态统计、无状态统计和枚举统计——统计学的三种基本范式。

⚠️ 注意事项

P1420 的差值检查：代码检查 curr_diff == pre_diff 而非 curr_diff == 1。严格按题意（连续自然数），应检查差是否为 1。当前写法能过是因为测试数据不含等差非连号段。
P1420 的 n=1 特判：代码对 n == 1 做了特殊处理直接输出 1。这是因为只有一个数时，连号长度就是 1。如果不特判，循环逻辑也能处理但 max_ans 初始为 0，输出 0+1=1，结果一致——特判是冗余的但不影响正确性。
P1420 的哨兵值：pre_num = 1000000000（10 亿）作为初始值。因为数据保证 a_i≤10⁹，哨兵取 10⁹ 可以确保第一个差值为负，不会误触发连号延长。如果数据范围更大，哨兵值需要调大。
P1179 的 while(temp)：当 temp=0 时循环不执行。如果题目统计数字 0，需要改用 do-while 或单独处理 0。
P1179 的效率：O(N×d) 对 R≤100000 足够。如果 R 到 10⁹，需要用数位 DP 优化到 O(log R)。

B4262 的大小写转换：必须在统计前统一转小写。代码在读入时立刻逐字符 tolower，确保 Apple 和 apple 归为同一个词。
B4262 的内层循环起点：内层循环从 k = j 开始而非 k = 0，这样每个单词的"第一次出现"位置获得完整计数，后续重复位置获得部分计数。取最大值时完整计数胜出，结果正确且避免了重复计数。
B4262 的复杂度：O(N² × L)，N=100、L≤30，总操作约 3×10⁵，毫无压力。如果 N 到 10⁵，需要换 unordered_map 降到 O(N)。
B4262 的输出格式：题目要求输出小写形式，因为读入时已统一转小写，数组中存的本身就是小写，直接输出即可。

🌳 延伸：统计的三个面孔——运行图、本福特定律与 TF-IDF

你说这三道题"都在对应着统计"。没错——而且它们恰好对应统计学的三大应用：趋势检测、频率分布和信息检索。前者在工业中叫运行图（Run Chart），中间在法务会计中叫本福特定律（Benford’s Law），后者在搜索引擎中叫 TF-IDF。

📈 运行图：最长连号的工业应用

P1420 找的是"最长的连续递增段"。在统计质量控制（SPC）中，这叫运行图（Run Chart）（Run Chart — Statistics How To）。

运行图把生产数据按时间顺序排列，检测非随机模式。其中一条关键规则就是最长连续上升/下降趋势（All statistics for Run Chart — Minitab）：

规则	含义	对应 P1420
趋势（Trend）	连续 6 个或更多点递增或递减	最长连号长度
偏移（Shift）	连续 6 个或更多点在中位数同侧	—
过多/过少运行	上下交替次数异常	—

在质量管理中，连续 6 个点递增就触发警报——意味着机器可能在磨损、操作员可能疲劳、化学过程可能在分离（Statistical Quality Control — Run Charts）。工厂里的 P1420，就是在检测"这个生产过程是不是出问题了"。

工业场景	运行图检测什么	和 P1420 的对应
机床温度	连续上升 → 冷却系统故障	最长连号 = 最长升温段
产品尺寸	连续偏移 → 刀具磨损	连号长度 = 磨损持续时长
化学浓度	连续变化 → 反应失控	连号 = 失控持续时长

你写的 max_ans 在工厂里叫"最长运行长度"——它是判断生产过程是否稳定的第一个指标。

📊 本福特定律：数字频率的反直觉真相

P1179 统计的是"数字 2 出现了多少次"。在真实数据中，数字的频率分布有一个惊人的规律——本福特定律（Benford’s Law）（Benford’s Law — Detecting Fraud）。

1881 年，天文学家西蒙·纽康（Simon Newcomb）发现对数表的前几页比后面几页磨损严重——说明人们更常查以 1 开头的数。1938 年，物理学家弗兰克·本福特（Frank Benford）收集了 20,000 多组数据（人口、河流长度、物理常数、报纸数字），发现了一个统一的规律（Benford’s Law Calculator）：

在自然产生的数据集中，首位数字为 d 的概率是：

P(d) = log₁₀(1 + 1/d)

首位数字	出现概率	直觉预期（均匀分布）
1	30.1%	11.1%
2	17.6%	11.1%
3	12.5%	11.1%
4	9.7%	11.1%
5	7.9%	11.1%
6	6.7%	11.1%
7	5.8%	11.1%
8	5.1%	11.1%
9	4.6%	11.1%

1 开头的数据占 30%，9 开头的只有 4.6%——不是均匀的！这反直觉，但真实世界的数据确实如此（本福特定律 — 百科）。

P1179 统计数字 2 在 [L, R] 中出现的次数。如果 R 足够大，你会发现 2 出现的频率不是 1/10，而是更接近本福特定律的预测——因为自然数的首位分布本身就服从本福特定律（Structural Foundations for Leading Digit Laws）。

🔥 本福特定律抓诈骗

本福特定律最震撼的应用是抓金融诈骗（Benford’s Law in Audit）。

逻辑很简单：人在编造数字时，会下意识地让首位数字"均匀分布"——觉得 1 到 9 各出现差不多才"像真的"。但真实数据的首位数字服从本福特定律——1 最多，9 最少。编造的数据偏离这个规律，就暴露了。

案例	发生了什么	本福特定律怎么帮忙
安然（Enron）	2001 年破产，财务数据造假	破产后分析发现其报表数字偏离本福特定律（Benford’s Law: The Strange Law）
HealthSouth	美国史上最大医疗欺诈之一	财务控制器每年编造 50 万条假账目，金额刻意压在审计阈值以下，但数字分布偏离本福特定律（Benford’s Law in Audit）
2009 伊朗大选	选举结果涉嫌造假	对选票数字做本福特分析，发现首位数字分布异常（Benford’s Law: The Strange Law）
发票欺诈	员工伪造报销金额	法庭将本福特定律分析作为证据，帮助定罪（Benford’s Law in Excel）

本福特定律分析已被法庭接受为合法的取证手段（Benford’s Law in Excel — Forensic Audit）。机器学习也在结合本福特定律做更强大的欺诈检测（Multiple Benford Law Model for Auditors）。

你今天在 P1179 里数数字 2 出现了几次——法务会计师在做完全一样的事，只不过他们数的是"1 开头的数据是不是占了 30%"。

🔍 TF-IDF：词频统计的搜索引擎应用

B4262 统计的是"哪个单词出现最多"。在信息检索领域，词频统计是搜索引擎排序的基础——它有一个著名的名字：TF-IDF（Term Frequency - Inverse Document Frequency）（TF-IDF 基础知识详解）。

TF（Term Frequency，词频） 就是你在 B4262 里算的那个东西——某个单词在文档中出现的次数。但光有词频不够：如果一篇文章里"的"出现 200 次，“量子"出现 5 次，哪个更能代表这篇文章的主题？显然是"量子”（TF-IDF Made Easy）。

IDF（Inverse Document Frequency，逆文档频率） 解决了这个问题——它衡量一个词有多"稀有"：

TF(t, d)  = 词 t 在文档 d 中出现的次数 / 文档 d 的总词数
IDF(t, D) = log(文档总数 / 包含词 t 的文档数)
TF-IDF    = TF × IDF

"的"在每篇文档都出现，IDF 接近 0，TF-IDF 很低。"量子"只在少数文档出现，IDF 很大，TF-IDF 很高。TF-IDF 越高，这个词对这篇文档越重要（Understanding TF-IDF）。

词	TF（在本文档中）	IDF（在所有文档中）	TF-IDF	说明
的	高（200 次）	低（每篇都有）	低	无意义高频词
量子	低（5 次）	高（少数文章有）	高	文档主题词
Apple	中（3 次）	中（部分文章有）	中	领域相关词

TF-IDF 的应用远超搜索引擎（TF-IDF Use Cases）：

应用	做什么	和 B4262 的关系
搜索引擎	按查询词和网页的 TF-IDF 评分排序	B4262 的词频 = TF 的一半
关键词提取	找出文档中 TF-IDF 最高的词	B4262 找频率最高，TF-IDF 找"最独特+最频繁"
文档分类	用 TF-IDF 向量训练分类器	B4262 的频率表是 TF-IDF 向量的基础
推荐系统	基于内容相似度推荐	TF-IDF 向量余弦相似度
主题建模	识别文档集合中的主题	TF-IDF 是 LDA 等模型的预处理步骤

Google 早期的网页排序就用了 TF-IDF——用户搜"apple"，Google 算每个网页中"apple"的 TF-IDF 值，值高的排前面（Understanding TF-IDF）。你在 B4262 里统计的词频，就是 Google 排序公式中的第一个变量。

今天，大语言模型（LLM）也在用词频——transformer 的注意力机制本质上就是在学习"哪些词和哪些词在一起出现更频繁"。从 B4262 的哈希表到 ChatGPT 的注意力矩阵，词频统计始终是自然语言处理的第一块基石。

🔮 三种统计的交汇

P1420、P1179 和 B4262 放在一起，恰好覆盖了统计学的三个基础应用：

	P1420	P1179	B4262	现实应用
统计类型	趋势检测	频率分布	词频统计	—
工业对应	运行图 / 质量控制	本福特定律 / 欺诈检测	TF-IDF / 搜索引擎	—
核心问题	“趋势有多长？”	“频率有多高？”	“谁出现最多？”	—
触发警报	连续 6 点递增 → 机器故障	首位偏离 30/17.6/12.5… → 数据造假	TF-IDF 高 → 关键词	—
你在做的	找 max_ans	数 2 出现几次	找频率最高的单词	—
工业在做的	找最长运行长度	检验首位数字分布	算网页 TF-IDF 排序	—

趋势检测告诉你过程是否稳定——工厂机器有没有在磨损。频率分布告诉你数据是否真实——财务报表有没有在造假。词频统计告诉你信息是否重要——搜索引擎该把哪个网页排第一。

一个看生产线的健康，一个看账本的健康，一个看信息的相关性。你今天在洛谷上写的几行代码，在工业界是三条专业流水线的起点。

📚 延伸阅读文献

论文

F. Benford. The Law of Anomalous Numbers. Proceedings of the American Philosophical Society, 78(4):551–572, 1938. （Benford’s Law — Wikipedia） —— 本福特定律的原始论文，收集了 20,000+ 组数据。
M. Nigrini. I’ve Got Your Number. Journal of Accountancy, 1999. （Benford’s Law in Audit） —— 将本福特定律应用于会计欺诈检测的开创性工作。
C. Goh. Applying visual analytics to fraud detection using Benford’s law. Journal of Corporate Accounting and Finance, 2020. （SMU Research） —— 可视化分析与本福特定律结合的欺诈检测。
T. A. Mir et al. Structural Foundations for Leading Digit Laws: Beyond Probabilistic Mixtures. arXiv:2508.13237, 2025. （arXiv） —— 2025 年最新的首位数字分布理论研究。
A. K. Sharma et al. The Use of Machine Learning to Detect Financial Transaction Fraud: Multiple Benford Law Model. 2024. （Semantic Scholar） —— 机器学习结合本福特定律的欺诈检测。
K. Sparck Jones. A Statistical Interpretation of Term Specificity and Its Application in Retrieval. Journal of Documentation, 1972. —— TF-IDF 中 IDF 概念的原始论文，信息检索领域的奠基之作。

在线资源

洛谷. P1420 最长连号. https://www.luogu.com.cn/problem/P1420
洛谷. P1179 [NOIP 2010 普及组] 数字统计. https://www.luogu.com.cn/problem/P1179
洛谷. B4262 [GESP202503 三级] 词频统计. https://www.luogu.com.cn/problem/B4262
Benford’s Law: Detecting Fraud with the First-Digit Phenomenon. https://www.statisticalaid.com/benfords-law/ —— 本福特定律入门介绍。
Run Chart — Statistics How To. https://www.statisticshowto.com/run-chart/ —— 运行图入门。
All statistics for Run Chart — Minitab. https://support.minitab.com/en-us/minitab/…/run-chart/ —— 运行图的工业标准解读。
Benford’s Law Calculator. https://calculatorcove.com/statistics/benfords-law/ —— 在线本福特定律计算器。
TF-IDF 基础知识详解：从原理到应用. https://blog.csdn.net/2401_83857914/article/details/163674280 —— TF-IDF 中文入门教程。
TF-IDF Made Easy: Intuition, Mathematics, and Python Implementation. https://ml-digest.com/tf-idf/ —— TF-IDF 原理与实现。
Understanding TF-IDF: The Key to Smarter Information Retrieval. https://algocademy.com/blog/understanding-tf-idf-the-key-to-smarter-information-retrieval/ —— TF-IDF 在信息检索中的应用。

洛谷 P1420 / P1179 / B4262 最长连号、数字统计与词频统计——统计的三种面孔