当前位置：文档库 › 信息学奥赛试题精选33题(附带题解)

信息学奥赛试题精选33题(附带题解)

第1~10题为基础题，第11~20题为提高题，第21~33为综合题

注：因为在本文档中需要用到一些特殊的数学符号（如：求和号、分数等），所以当您在百度文库中浏览时，一些数学符号可能会显示不出来，不过当您把本文档下载下来在本地浏览时，所有的符号即可全部都显示出来。^_^

基础题：

【1 Prime Frequency】

【问题描述】

给出一个仅包含字母和数字（0-9, A-Z 以及a-z）的字符串，请您计算频率（字符出现的次数），并仅报告哪些字符的频率是素数。

输入：

输入的第一行给出一个整数T( 0

输出：

对输入的每个测试用例输出一行，给出一个输出序列号，然后给出在输入的字符串中频率是素数的字符。这些字符按字母升序排列。所谓“字母升序”意谓按ASCII 值升序排列。如果没有字符的频率是素数，输出“empty”（没有引号）。

样例输入样例输出

ABCC AABBBBDDDDD ABCDFFFF Case 1: C Case 2: AD Case 3: empty

注：

试题来源：Bangladesh National Computer Programming Contest

在线测试：UV A 10789

提示

先离线计算出[2‥2200]的素数筛u[]。然后每输入一个测试串，以ASCLL码为下标统计各字符的频率p[]，并按照ASCLL码递增的顺序（0≤i≤299）输出频率为素数的字符（即u [p[i]]=1且ASCLL码值为i的字符）。若没有频率为素数的字符，则输出失败信息。

【2 Twin Primes】

【问题描述】

双素数（Twin Primes）是形式为(p, p+2)，术语“双素数”由Paul St?ckel (1892-1919)给出，前几个双素数是(3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43)。在本题中请你给出第S对双素数，其中S是输入中给出的整数。

输入：

输入小于10001行，每行给出一个整数S (1≤ S≤ 100000)，表示双素数对的序列编号。输入以EOF结束。

输出：

对于输入的每一行，输出一行，给出第S对双素数。输出对的形式为(p1,空格p2)，其中“空格”是空格字符(ASCII 32)。本题设定第100000对的素数小于20000000。

样例输入样例输出

1 2 3 4 (3, 5) (5, 7) (11, 13) (17, 19)

注：

试题来源：Regionals Warmup Contest 2002, Venue: Southeast University, Dhaka, Ba ngladesh

在线测试：UV A 10394

提示

设双素数对序列为ans[]。其中ans[i]存储第i对双素数的较小素数（1≤i≤num）。ans[]的计算方法如下：

使用筛选法计算出[2，20000000]的素数筛u[]；

按递增顺序枚举该区间的每个整数i：若i和i+2为双素数对（u[i]&&u[i+2]）,则双素数对序列增加一个元素（ans[++num]=i）。

在离线计算出ans[]的基础上，每输入一个编号s，则代表的双素数对为(ans[s]，ans[s]+ 2)。

【3 Less Prime】

【问题描述】

设n为一个整数，100≤n≤10000，请找到素数x，x≤ n，使得n-p*x最大，其中p是整数，使得p*x≤n<(p+1)*x。

输入:

输入的第一行给出一个整数M，表示测试用例的个数。每个测试用例一行，给出一个整数N，100≤N≤10000。

输出:

对每个测试用例，输出一行，给出满足上述条件的素数。样例输入样例输出 5 4399 614 8201 101 7048 2203 311 4111 53 3527

注：

试题来源：III Local Contest in Murcia 2005 在线测试：UV A 10852

提示

要使得n-p*x 最大（x 为素数，p 为整数，p*x ≤ n<(p+1)*x ），则x 为所有小于n 的素数中，被n 除后余数最大的一个素数。由此得出算法：

先离线计算出[2‥11111]的素数表su[]，表长为num 。然后每输入一个整数n ，则枚举小于n 的所有素数，计算tmp=}][][%{max 1n i su i su n n u m

i <≤≤，满足条件的素数即为对应tmp=n%

su[k]的素数su[k]。

【4 Prime Words 】【问题描述】

一个素数是仅有两个约数的数：其本身和数字1。例如，1, 2, 3, 5, 17, 101和10007是素数。

本题输入一个单词集合，每个单词由a-z 以及A-Z 的字母组成。每个字母对应一个特定的值，字母a 对应1，字母b 对应2，以此类推，字母z 对应26；同样，字母A 对应27，字母B 对应28，字母Z 对应52。

一个单词的字母的总和是素数，则这个单词是素单词（prime word ）。请编写程序，判定一个单词是否为素单词。输入：

输入给出一个单词集合，每个单词一行，有L 个字母，1≤L ≤20。输入以EOF 结束。输出：

如果一个单词字母的和为素数，则输出“It is a prime word.”；否则输出“It is not a prime word.”。样例输入样例输出

UFRN

It is a prime word.

contest AcM It is not a prime word. It is not a prime word.

注：

试题来源：UFRN-2005 Contest 1 在线测试：UV A 10924

提示

由于字母对应数字的上限为52，而单词的长度上限为20，因此我们首先使用筛选法，离线计算出[2‥1010]的素数素数筛u[]。

然后每输入一个长度为n 的单词，计算单词字母对应的数字和

}''..'{'][27''][,}''..'{'][1''][1

Z A i s A i s z a i s a i s n

i ∈+-∈+-∑=

若x 为[2‥1010]中的一个素数（u[x]=1），则表明该单词为素单词；否则该单词非素单词。

【5 Sum of Different Primes 】【问题描述】

一个正整数可以以一种或多种方式表示为不同素数的总和。给出两个正整数n 和k ，请您计算将n 表示为k 个不同的素数的和会有几种形式。如果是相同的素数集，则被认为是相同的。例如8可以被表示为3 + 5和5 + 3，但不区分。

如果n 和k 分别为24和3，答案为2，因为有两个总和为24的集合 {2, 3, 19}和{2, 5, 17} ，但不存在其他的总和为24的3个素数的集合。如果n = 24，k = 2，答案是3，因为存在3个集合{5, 19}, {7, 17}以及{11, 13}。如果n = 2，k = 1，答案是1，因为只有一个集合{2} ，其总和为2。如果n = 1，k = 1，答案是0，因为1不是素数，不能将{1}计入。如果n = 4，k = 2，答案是0，因为不存在两个不同素数的集合，总和为4。

请您编写一个程序，对给出的n 和k ，输出答案。输入：

输入由一系列的测试用例组成，最后以一个空格分开的两个0结束。每个测试用例一行，给出以一个空格分开的两个正整数n 和k 。本题设定n ≤ 1120，k ≤ 14。输出：

输出由若干行组成，每行对应一个测试用例，一个输出行给出一个非负整数，表示对相应输入中给出的n 和k 有多少答案。本题设定答案小于231。样例输入样例输出 24 3 24 2 2 1

2 3 1

1 1

4 2

18 3

17 1

17 3

17 4 100 5 1000 10 1120 14 0 0 0

55 200102899 2079324314

注：

试题来源：ACM Japan 2006

在线测试：POJ 3132，ZOJ 2822，UV A 3619

提示

设

su[]为[2..1200]的素数表；f[i][j]为j拆分成i个素数和的方案数(1≤i≤14, su[i]≤j≤1199)。显然，边界值f[0][0]=1。

首先，采用筛选法计算素数表su[]，表长为num。然后每输入一对n和k，使用动态规划方法计算k个不同素数的和为n的方案总数：

枚举su[]表中的每个素数su[i](1≤i≤num）

按递减顺序枚举素数个数j(j=14‥1)：

按递减顺序枚举前j个素数的和p（p=1199‥su[i]）:

累计su[i]作为第j个素数的方案总数f[j][p]+=f[j-1][p-su[i]];

最后得出的f[k][n]即为问题解。

【6 Common Permutation】

【问题描述】

给出两个小写字母的字符串，a和b，输出最长的小写字母字符串x使得存在x的一个排列，是a的子序列，同时也存在x的一个排列是b的子序列。

输入：

输入有若干行。连续的两行组成一个测试用例，也就是说，第1和第2行构成一个测试用例，第3和第4行构成一个测试用例，等等。每个测试用例的第一行是字符串a，第二行是字符串b。每个字符串一行，至多由1000个小写字母组成。

输出：

对每个测试用例，输出一行，给出x。如果有若干个x满足上述要求，选择按字母序列第一个。

样例输入样例输出 pretty women walking down the street

e nw et

注：

试题来源：World Finals Warm-up Contest, University of Alberta Local Contest 在线测试：UV A 10252

提示

试题要求按递增顺序输出两串公共字符的排列。计算方法如下：设S 1=a 1a 2…a l a ，S 2= b 1b 2…b l b 。

先分别统计S 1中各字母的频率c 1[i]和S 2中各字母的频率c 2[i]（1≤i ≤26,其中字母‘a ’对应数字1, 字母‘b ’对应数字2,…，字母‘z ’对应数字26）。

然后计算S 1和S 2的公共字符的排列：递增枚举i(1≤i ≤26)，若i 对应的字母在S 1和S 2中同时存在（（c1[i]≠0）&&（c2[i]≠0））,则字母'a'+i 在排列中出现k=min{c1[i]，c2[i]}次。

【7 Anagram 】

【问题描述】

给出一个字母的集合，请您编写一个程序，产生从这个集合能构成的所有可能的单词。例如：给出单词"abc"，您的程序产生这三个字母的所有不同的组合——输出单词"abc", "acb",

"bac", "bca", "cab" 和"cba"。

程序从输入中获取一个单词，其中的一些字母会出现一次以上。对一个给出的单词，程序产生相同的单词只能一次，而且这些单词按字母升序排列。输入：

输入给出若干单词。第一行给出单词数，然后每行给出一个单词。一个单词是由A 到Z 的大写或小写字母组成。大写字母和小写字母被认为是不同的，每个单词的长度小于13。输出：

对输入中的每个单词，输出这个单词的字母产生的所有不同的单词。输出的单词按字母升序排列。大写字母排在相应的小写字母前，即'A'<'a'<'B'<'b'<...<'Z'<'z'。样例输入样例输出 3 aAb abc acba

Aab Aba aAb abA bAa

baA

abc

acb

bac

bca

cab

cba

aabc

aacb

abac

abca

acab

acba

baac

baca

bcaa

caab

caba

cbaa

注：

试题来源：ACM Southwestern European Regional Contest 1995

在线测试：POJ 1256，UV A 195

提示

建立字母与整数间的对应关系：

字母‘a’对应0，字母‘A’对应1;…；字母‘z’对应50，字母‘Z’对应51。

为了按照字母升序的要求生成单词的所有排列，首先将单词的所有字母转化为数字，然后递增排序数串，排列中每个位置的数字按由左而右顺序从数串中选择。

设单词长度为l，数串的第i个位置已访问标志为v1[i]，初始时v1[]清零；数字k对应的字母已使用标志为v2[k]，v2[]为递归程序内的局部变量（0≤i≤l-1，0≤k≤51）。

生成所有排列的计算过程为一个递归子程序：

void dfs(int d){ //从当前位置d出发，递归计算单词的所有排列if (d==l) 输出当前数字排列对应的单词；//生成单词的一个排列

}else{

v2[]清零; //所有字母未确定

for(int i=0;i

if(!v1[i]&&!v2[i位置字母对应的数字]){

v1[i]=1;v2[i位置字母对应的数字]=1;

i位置字母对应的数字放入当前排列的d位置;

dfs(d+1); //递归排列的第d+1个位置

v1[i]=0; //恢复数串的第i个位置未访问标志

} } } }

显然，主程序设数串的所有位置未访问（v1[]清零），递归调用dfs(0)，便可按字母升序要求输出单词的所有排列。

【8 How Many Points of Intersection?】

【问题描述】

给出两行，在第一行有a 个点，在第二行有b 个点。我们用直线将第一行的每个点与第二行的每个点相连接。这些点以这样的方式排列，使得这些线段之间相交的数量最大。为此，不允许两条以上的线段在一个点上相交。在第一行和第二行中的相交点不被计入，在两行之间允许两条以上的线段相交。给出a 和b 的值，请计算P (a , b )，在两行之间相交的数量。例如，在下图中a = 2，b = 3，该图表示P (2, 3) = 3

。

输入：

输入的每行给出两个整数a ( 0

对输入的每一行，输出一行，给出序列编号，然后给出P (a , b )的值。本题设定输出值在64位有符号整数范围内。样例输入样例输出 2 2 2 3 3 3 0 0

Case 1: 1 Case 2: 3 Case 3: 9

注：

试题来源：Bangladesh National Computer Programming Contest, 2004 在线测试：UV A 10790

提示

如3线交于一点，则一定可以通过左右移动一个点使其交点分开，上面线段上的两点与

下面线段上的两点可以产生一个交点。按照乘法原理，p(a ，b)=错误！未找到引用源。。【9 Stripies 】

【问题描述】

生化学家发明了一种很有用途的生物体，叫 stripies ，（实际上，最早的俄罗斯名叫 polosatiki ，不过科学家为了申请国际专利时方便不得不起了另一个英文名）。stripies 是透明，无定型的，群居在一些象果子冻那样的有营养的环境里。在大部分时间stripies 是在移动中，当两条stripies 碰撞时，这两条stripies 就融合产生一条新的stripies 。经过长时间的观察，科学家们发现当两条stripies 碰撞融合在一起时，新的stripies 的重量并不等于碰撞前两条stripies 的重量。不久又发现两条重量为m 1和m 2的stripies 碰撞融合在一起，其重量变为2*sqrt(m 1*m 2)。科学家很希望知道有什么办法可以限制一群stripies 的总重量的减少。请您编写程序来解决这个问题。本题设定3条或更多的stripies 从来不会碰撞在一起。输入：