![](https://csdnimg.cn/release/download_crawler_static/1882535/bg5.jpg)
搜索基础 2006/01/23 版 By XT
如果达到共k个,则进行求和,并且判断是否为素数,统计。此种方法在数据规
模较大的时候不是很好用,也就是判断次数在n大时增长迅速,属于指数级渐进
时间复杂度,时间耗费大。时间复杂度O(2
n
)。
[例题 5] 等差数列(ZJOI2004)
给定 n(1<=n<=100)个数,从中找出尽可能多的数使得他们能够组成一个等差
数列.求最长的等差数列的长度.
我们首先必须对这个数列进行排序,排序我们采用 QuickSort。然后我们
就能够很快想到一系列的方法:枚举头部、第二个与尾部。
但是我们为什么要枚举三个呢?头部当然不用说,第二个是为了与第一个作
差,得出公差。然后就可以递推地去枚举到最后。
这样我们就能够得出一个O(n
3
)的方法,而在n<=100 的时候保证不会超
时。
[例题 6] 敲七、敲七版本 2(TOJ1006/1044)
1.输出7和7的倍数,还有包含 7 的数字例如(17,27,37...70,71,72,
73...),给出一个整数 N,(N 不大于 30000),输出从小到大排列的不大于 N 的
与 7 有关的数字,每行一个。
2. 给定正整数 N,求数列{An}的前 N 项。数列{An}满足如下条件:
1.该数列包含自然数集中所有能被 7 整除的数
2.该数列包含自然数集中所有个位上含 7 的数,如 17,27,177
3.该数列不包含自然数集中其他的数
4.该数列中的数有小到大有序排列
5.该数列中任意两项互不相同
给出一个正整数 N(N<=100,000),输出数列{An}的前 N 项,每项占单独一行。
1.这道题按照题意,我们可以求得最简单的方法:从 1 枚举到 N,对每一个
数字进行判断。当然这是对这个数据来说最好的方法,其实还有一种方法是预处
理,用一些方法记录下来(方法很多)。至于判断是否含有 7,我想到的是一位
一位看,而 Maigo 大牛有个方法,就是转成字符串用 POS,这是不是个好方法
呢?
2.理清题意,发现这是个简单题。读入 N 后,我们从 1 开始依次枚举,对
每个数字进行 2 次运算,如果运算成功,就可以输出并记录个数,直到最后。
这个题目还有一种对于大数据的高效方法——合并有序链表。我们可以建立
2 个链表,然后生成 1..N 中符合条件的数字。因为这两个链表是有序的,因此
用两个指针(静态、动态皆可)去合并。这样是最优效果。
[例题 7] 猫老大数(TOJ1081,猫老大与彩虹的竞赛)
猫老大很喜欢研究数字,特别是喜欢质数。一天,猫老大发现有一些数字可
以表示成两个质数相乘的形式。比如,10=2×5. 2,5 都是质数,所以 10 是一
个“猫老大数 ”。所以猫老大决定考考彩虹,他告诉彩虹一个数 n ,判断 n 是
不是“猫老大数”?(1<=n<=2
31
-1)
第 5 页 共 25 页