NOIP 提高组初赛 · NOIP 2009 提高组初赛试题 第 28 题

（寻找等差数列）有一些长度相等的等差数列（数列中每个数都为 $0\sim 59$ 的整数），设长度均为 $L$，将等差数列中的所有数打乱顺序放在一起。现在给你这些打乱后的数，问原先，$L$ 最大可能为多大？先读入一个数 $n(1\leq n\leq60)$，再读入 $n$ 个数，代表打乱后的数。输出等差数列最大可能长度 $L$。

#include <iostream>
using namespace std;
int hash[60];
int n, x, ans, maxnum;
int work(int now) {
	int first, second, delta, i;
	int ok;
	while (      ①       && !hash[now])
		++now;
	if (now > maxnum)
		return 1;
	first = now;
	for (second = first; second <= maxnum; second++)
		if (hash[second]) {
			delta =       ②       ;  
			if (first + delta *    ③      > maxnum) 
				break;
			if (delta == 0)
				ok = (      ④      ); 
			else{
				ok = 1;
				for (i = 0; i < ans; i++)
					ok =     ⑤     && (hash[first+delta*i]); 
			}
			if (ok){
				for (i = 0; i < ans; i++)
					hash[first+delta*i]--;
				if (work(first)) 
					return 1;
				for (i = 0; i < ans; i++)
					hash[first+delta*i]++;
			}
		}
	return 0;
}
int main()

（本题为阅读程序 / 完善程序，完整题目与测试数据见平台）

这题考的是DFS回溯判断能否把一堆数拆成若干个等长的等差数列。拿到题先想：枚举长度ans从大到小，只要n%ans==0且从0开始DFS能成功把hash清零，那就是答案。核心是work(now)函数里找第一个非零hash作为起点，再枚举第二个数定公差，递归处理剩余项，回溯时记得还原hash。

最容易栽跟头的是把work(0)的条件写错，比如写成work(0)==1或者work(0)>0，虽然逻辑对，但题目给的选项里只有work(0)这种简洁写法，选多了反而扣分。另外在delta==0时，只检查了hash[first]>=ans，漏了hash[second]>=ans和hash[first+delta]>=ans，导致公差为0的数列没被正确统计。还有在while循环里把now<=maxnum写成now<maxnum，会漏掉最后一个数，或者把!(now>maxnum)写成!(now>=maxnum)，逻辑反了。

这道题考查的是深度优先搜索（DFS）与回溯思想，结合等差数列的性质和计数数组的应用。命题人喜欢在这种填空题里挖坑：一方面考你等差数列通项公式的变形（last = first + delta * (ans-1)），另一方面考你回溯时hash数组的还原，还考你枚举起点时如何跳过已处理的数。拿到题先想：题目要求最大长度L，且n个数正好能分成若干段，每段长度都是L。那L肯定整除n，而且L从n往下枚举，第一个满足条件的就是答案。所以外层循环for(ans=n; ans>=1; ans--)直接枚举长度，内层先判断n%ans==0，再调用work(0)看能不能从0开始把hash全清零。work(now)函数的设计很巧妙：它从now开始找第一个hash不为0的数作为数列起点first，然后枚举第二个数second（从first到maxnum），算出公差delta=second-first。如果公差为0，那所有项都是first，只要hash[first]>=ans就行；如果公差非零，就要检查first, first+delta, ..., first+delta*(ans-1)这些位置是否都有足够的数。检查完如果ok，就把这些位置的hash减1，递归处理剩余未处理的数（work(first)），如果递归返回true说明当前方案可行，直接返回1；否则回溯，把hash加回来继续尝试其他second。这里有个细节：while(now <= maxnum && !hash[now]) ++now; 这行代码的作用是跳过所有已经被其他数列用掉的数，找到下一个需要处理的起点。如果now跑出了maxnum，说明所有数都处理完了，返回1。在枚举second时，要确保数列最后一个数不超过maxnum，所以条件first + delta * (ans-1) > maxnum时break。delta的计算就是second-first，因为first和second都是下标，直接相减就是公差。ans-1这个系数来自等差数列项数公式：第ans项 = 首项 + 公差*(项数-1)。delta==0时的ok判断必须同时满足hash[first]>=ans、hash[second]>=ans、hash[first+delta]>=ans，因为当公差为0时，first、second、first+delta其实是同一个位置，但题目给的选项里这三个条件并列出现，说明命题人想让你注意到即使公差为0，也要检查所有涉及的下标是否都有足够的数（虽然数值相同，但下标不同）。回溯时ok的累加逻辑是ok = ok && ...，所以5空填ok。6空填work(0)，因为如果work(0)返回1，说明从0开始能成功构造所有数列。这道题在NOIP提高组初赛里属于偏难的程序填空题，因为它不仅考算法，还考你对代码细节的敏感度。从考频来看，一维数组这个知识点在题库里共考了224题，覆盖9个考试级别，2023年突然暴增到27题，2024年更是高达48题，2025年55题，2026年59题，说明最近这几年对基础数据结构的考察力度在加大。其他算法（DFS/回溯）题库只考了6题，集中在2009-2021年，NOIP提高组初赛只考过1次，说明这类题现在很少见了，但既然考了，就得认真琢磨。预测的话，基于现有数据，一维数组的考频还在持续上升，未来几年可能继续维持高位，但DFS这种具体算法题在NOIP提高组初赛里大概率不会再出现，除非命题人想搞点冷门。不过作为选手，把这类题彻底搞懂还是有必要的，毕竟它融合了多个知识点，练好了能提升综合解题能力。