青少年中学生信息学奥赛试题精选 33 题 (附带题解 ) 第 1~10 题为基础题，第 11~20 题为提高题，第 21~33 为综合题
基础题：
【 1 Prime Frequency 】
【问题描述】
给出一个仅包含字母和数字（ 0-9, A-Z 以及 a-z）的字符串，请您计算频率（字符出现
的次数），并仅报告哪些字符的频率是素数。
【 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。 输出 :
样例输入
样例输出
1
(3, 5)
2
(5, 7)
3
(11, 13)
4 注：
(17, 19)
试题来源： Regionals Warmup Contest 2002, Venue: Southeast University, Dhaka, Bangl adesh
在线测试： UVA 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)。
【 2 Twin Primes】 【问题描述】
1
双素数（ Twin Primes）是形式为 (p, p+2) ，术语“双素数”由 Paul St?ckel (1892-1919) 给出，前几个双素数是 (3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43)。在本题中请你给 出第 S 对双素数，其中 S 是输入中给出的整数。 输入：
输入：
输入的第一行给出一个整数 T ( 0<T<201)，表示测试用例个数。后面的 T 行每行给出一
个测试用例：一个字母 -数字组成的字符串。字符串的长度是小于 2001 的一个正整数。
输出：
对输入的每个测试用例输出一行，给出一个输出序列号，然后给出在输入的字符串中频
率是素数的字符。这些字符按字母升序排列。所谓“字母升序”意谓按
ASCII 值升序排列。
如果没有字符的频率是素数，输出“ empty ”（没有引号） 。
样例输入Βιβλιοθήκη 样例输出3Case 1: C
ABCC
Case 2: AD
AABBBBDDDDD
Case 3: empty
ABCDFFFF 注：
试题来源： Bangladesh National Computer Programming Contest 在线测试： UVA 10789
提示 先离线计算出 [2‥2200] 的素数筛 u[] 。然后每输入一个测试串， 以 ASCLL码为下标统计各 字符的频率 p[] ，并按照 ASCLL码递增的顺序 （ 0≤ i≤ 299）输出频率为素数的字符 （即 u[p[i]] =1 且 ASCLL码值为 i 的字符）。若没有频率为素数的字符，则输出失败信息。
输入小于 10001 行，每行给出一个整数 S (1 ≤S ≤ 100000) ，表示双素数对的序列编号。 输入以 EOF结束。 输出：
对于输入的每一行，输出一行，给出第 S 对双素数。输出对的形式为 (p1,空格 p2)，其中 “空格”是空格字符 (ASCII 32)。本题设定第 100000 对的素数小于 20000000。
2