NOIP2002普及组复赛试题

2002年全国青少年信息学〔计算机〕奥林匹克分区联赛复赛试题

注意事项：认真阅读理解，结合历年的真题，总结经验，查找不足！重在审题，多思考，多理解！

〔普及组竞赛用时：3小时〕

题一级数求和〔存盘名：NOIPC1〕

[问题描述]:

：Sn=1＋1／2＋1／3＋…＋1／n。显然对于任意一个整数K，当n足够大的时候，Sn大于K。

现给出一个整数K〔1<=k<=15〕，要求计算出一个最小的n；使得Sn＞K。

[输入]

键盘输入k

[输出]

屏幕输出n

[输入输出样例]

输人：1

输出：2

题二选数〔存盘名：NOIPC2〕

[问题描述]:

n个整数x1,x2,…,xn，以及一个整数k〔k＜n〕。从n个整数中任选k个整数相加，可分别得到一系列的和。例如当n=4，k＝3，4个整数分别为3，7，12，19时，可得全部的组合与它们的和为：

3＋7＋12=223＋7＋19＝297＋12＋19＝383＋12＋19＝34。

现在，要求你计算出和为素数共有多少种。

例如上例，只有一种的和为素数：3＋7＋19＝29〕。

[输入]： 键盘输入，格式为：

n,k〔1<=n<=20，k＜n〕

x1,x2，…,xn〔1<=xi<=5000000〕

[输出]：

屏幕输出，格式为：

一个整数〔满足条件的种数〕。

[输入输出样例]:

输入：

43

371219

输出：

1

题三产生数〔存盘名：NOIPC3〕

[问题描述]:

给出一个整数n〔n<10^30)和k个变换规那么〔k<=15〕。

规那么：

一位数可变换成另一个一位数：

规那么的右部不能为零。

例如：n=234。有规那么〔k＝2〕：

2－>5

3－>6

上面的整数234经过变换后可能产生出的整数为〔包括原数〕:

234 534

264

564

共4种不同的产生数

问题：

给出一个整数n和k个规那么。

求出：

经过任意次的变换〔0次或多次〕，能产生出多少个不同整数。

仅要求输出个数。

noip 2002 普及组第四题

题目：有10个待排序的数，每个数都是非负整数，使用快速排序进行排序。

快速排序是一种常用的排序算法，其基本思想是选择一个基准元素，将数组分成两部分，一部分的元素都比基准元素小，另一部分的元素都比基准元素大，然后对这两部分分别进行快速排序。快速排序的时间复杂度为O(nlogn)，其中n是待排序元素的个数。

以下是使用C++实现的快速排序算法的代码：

c复制代码

#include

#include

using namespace std;

void quicksort(vector& nums, int left, int right) {

if (left >= right) {

return;

}

int pivot = nums[left];

int i = left, j = right;

while (i < j) {

while (i < j && nums[j] >= pivot) {

j--; }

nums[i] = nums[j];

while (i < j && nums[i] <= pivot) {

i++;

}

nums[j] = nums[i];

}

nums[i] = pivot;

quicksort(nums, left, i - 1);

quicksort(nums, i + 1, right);

}

int main() {

vector nums = {5, 2, 9, 1, 5, 6, 8, 7, 4, 2};

quicksort(nums, 0, nums.size() - 1);

for (int num : nums) {

cout << num << " ";

}

cout << endl;

return 0;

第1页 一、新龟兔赛跑（文件名xgtsp.pas）

新龟兔赛跑比赛即将举行，此次龟兔赛跑比赛的规则与以往有所不同，不再考察兔子和乌龟谁在最短的时间内跑完规定的路程，而是考察谁在规定时间内跑的路程更长，且兔子和乌龟跑步都是匀速的。由于兔子的坏习惯，它总喜欢把比赛的总时间T小时中的K小时拿来睡觉。现在给你比赛的总时间T、兔子的睡觉时间K、兔子的速度U、乌龟的速度V，需要你求出该次比赛谁最后获胜。

输入第一行为一个整数X，表示有X组输入数据。每组数据只有一行，包括4个数T、K、U、V (1 ≤ T≤ 300，0 ≤ K ≤ T，1 ≤ U ≤ 100，1 ≤ V ≤ 100)。

对于每组数据，输出只有一个数，如果兔子获胜则输出-1，如果乌龟获胜则输出1，如果同时到达则输出0。允许输入一组数后立即输出对应的结果。样例输入：2

1 1 2 1

6 2 6 3

样例输出：

1

-1

var

v,u,t,k,n,i:integer;

begin

readln(n);

for i:=1 to n do begin

readln(t,k,u,v);

if v*t>U*(t-k) then writeln(1);

if v*t

if v*t=U*(t-k) then writeln(0);

end;

end.

1、输入：

2

6 2 6 2

8 6 8 2

输出：

-1

0

2、输入：

2

300 280 60 20

120 0 12 13

输出：

1

1

3、输入：

3

第2页 100 20 50 30

100 50 45 25

100 80 27 17

输出：

-1

1

1

4、输入：

3

150 77 29 23

127 11 22 13

139 22 13 7

输出：

1

-1

-1

二、小球路程（文件名：XQLC.PAS ）

已知小球从100米高度自由下落，落地后反弹起，又落地，又弹起，„„。每次弹起的高度都是上一次高度的一半。求小球第N次反弹起的高度和球在整个过程所经过的路程（包括下落和反弹），用键盘输入N，输出反弹高度和经过路程，结果保留两位小数。

2002年全国青少年信息学（计算机）奥林匹克分区联赛复赛试题

（提高组 竞赛用时：3 小时）

题一 均分纸牌（存盘名 NOIPG1）

[问题描述]

有 N 堆纸牌，编号分别为 1，2，…, N。每堆上有若干张，但纸牌总数必为 N 的倍数。可以在任一堆上取若于张纸牌，然后移动。

移牌规则为：在编号为 1 堆上取的纸牌，只能移到编号为 2 的堆上；在编号为 N 的堆上取的纸牌，只能移到编号为 N-1 的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。

现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。

例如 N=4，4 堆纸牌数分别为：

① 9 ② 8 ③ 17 ④ 6

移动3次可达到目的：

从 ③ 取 4 张牌放到 ④ （9 8 13 10） -> 从 ③ 取 3 张牌放到 ②（9 11 10 10）-> 从

② 取 1 张牌放到①（10 10 10 10）。

[输 入]：

键盘输入文件名。文件格式：

N（N 堆纸牌，1 <= N <= 100）

A1 A2 … An （N 堆纸牌，每堆纸牌初始数，l<= Ai <=10000）

[输 出]：

输出至屏幕。格式为：

所有堆均达到相等时的最少移动次数。‘

[输入输出样例]

a.in：

4

9 8 17 6

屏慕显示：

3

题二 字串变换 （存盘名: NOIPG2）

[问题描述]:

已知有两个字串 A$, B$ 及一组字串变换的规则（至多6个规则）:

A1$ -> B1$

A2$ -> B2$

规则的含义为：在 A＄中的子串 A1$ 可以变换为 B1$、A2$ 可以变换为 B2$ …。

例如：A$＝'abcd' B$＝'xyz'

变换规则为：

‘abc’->‘xu’ ‘ud’->‘y’ ‘y’->‘yz’

则此时，A$ 可以经过一系列的变换变为 B$，其变换的过程为： ‘abcd’->‘xud’->‘xy’->‘xyz’