搜索
第1~10题为基础题，第11~20题为提高题，第21~33为综合题注：因为在本文档中需要用到一些特殊的数学符号（如：求和号、分数等），所以当您在百度文库中浏览时，一些数学符号可能会显示不出来，不过当您把本文档下载下来在本地浏览时，所有的符号即可全部都显示出来。^_^基础题：【1PrimeFrequency】【问题描述】给出一个仅包含字母和数字（0-9,A-Z以及a-z）的字符串，请您计算频率（字符出现的次数），并仅报告哪些字符的频率是素数。输入：输入的第一行给出一个整数T(0T201)，表示测试用例个数。后面的T行每行给出一个测试用例：一个字母-数字组成的字符串。字符串的长度是小于2001的一个正整数。输出：对输入的每个测试用例输出一行，给出一个输出序列号，然后给出在输入的字符串中频率是素数的字符。这些字符按字母升序排列。所谓“字母升序”意谓按ASCII值升序排列。如果没有字符的频率是素数，输出“empty”（没有引号）。样例输入样例输出3ABCCAABBBBDDDDDABCDFFFFCase1:CCase2:ADCase3:empty注：试题来源：BangladeshNationalComputerProgrammingContest在线测试：UVA10789提示先离线计算出[2‥2200]的素数筛u[]。然后每输入一个测试串，以ASCLL码为下标统计各字符的频率p[]，并按照ASCLL码递增的顺序（0≤i≤299）输出频率为素数的字符（即u[p[i]]=1且ASCLL码值为i的字符）。若没有频率为素数的字符，则输出失败信息。【2TwinPrimes】【问题描述】双素数（TwinPrimes）是形式为(p,p+2)，术语“双素数”由PaulStä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)，其中“空格”是空格字符(ASCII32)。本题设定第100000对的素数小于20000000。样例输入样例输出1234(3,5)(5,7)(11,13)(17,19)注：试题来源：RegionalsWarmupContest2002,Venue:SoutheastUniversity,Dhaka,Bangladesh在线测试：UVA10394提示设双素数对序列为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)。【3LessPrime】【问题描述】设n为一个整数，100≤n≤10000，请找到素数x，x≤n，使得n-p*x最大，其中p是整数，使得p*x≤n(p+1)*x。输入:输入的第一行给出一个整数M，表示测试用例的个数。每个测试用例一行，给出一个整数N，100≤N≤10000。输出:对每个测试用例，输出一行，给出满足上述条件的素数。样例输入样例输出543996148201101704822033114111533527注：试题来源：IIILocalContestinMurcia2005在线测试：UVA10852提示要使得n-p*x最大（x为素数，p为整数，p*x≤n(p+1)*x），则x为所有小于n的素数中，被n除后余数最大的一个素数。由此得出算法：先离线计算出[2‥11111]的素数表su[]，表长为num。然后每输入一个整数n，则枚举小于n的所有素数，计算tmp=}][][%{max1nisuisunnumi，满足条件的素数即为对应tmp=n%su[k]的素数su[k]。【4PrimeWords】【问题描述】一个素数是仅有两个约数的数：其本身和数字1。例如，1,2,3,5,17,101和10007是素数。本题输入一个单词集合，每个单词由a-z以及A-Z的字母组成。每个字母对应一个特定的值，字母a对应1，字母b对应2，以此类推，字母z对应26；同样，字母A对应27，字母B对应28，字母Z对应52。一个单词的字母的总和是素数，则这个单词是素单词（primeword）。请编写程序，判定一个单词是否为素单词。输入：输入给出一个单词集合，每个单词一行，有L个字母，1≤L≤20。输入以EOF结束。输出：如果一个单词字母的和为素数，则输出“Itisaprimeword.”；否则输出“Itisnotaprimeword.”。样例输入样例输出UFRNItisaprimeword.contestAcMItisnotaprimeword.Itisnotaprimeword.注：试题来源：UFRN-2005Contest1在线测试：UVA10924提示由于字母对应数字的上限为52，而单词的长度上限为20，因此我们首先使用筛选法，离线计算出[2‥1010]的素数素数筛u[]。然后每输入一个长度为n的单词，计算单词字母对应的数字和X=}''..'{'][27''][,}''..'{'][1''][1ZAisAiszaisaisni若x为[2‥1010]中的一个素数（u[x]=1），则表明该单词为素单词；否则该单词非素单词。【5SumofDifferentPrimes】【问题描述】一个正整数可以以一种或多种方式表示为不同素数的总和。给出两个正整数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。样例输入样例输出243242212311142183171173174100510001011201400002101552001028992079324314注：试题来源：ACMJapan2006在线测试：POJ3132，ZOJ2822，UVA3619提示设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]即为问题解。【6CommonPermutation】【问题描述】给出两个小写字母的字符串，a和b，输出最长的小写字母字符串x使得存在x的一个排列，是a的子序列，同时也存在x的一个排列是b的子序列。输入：输入有若干行。连续的两行组成一个测试用例，也就是说，第1和第2行构成一个测试用例，第3和第4行构成一个测试用例，等等。每个测试用例的第一行是字符串a，第二行是字符串b。每个字符串一行，至多由1000个小写字母组成。输出：对每个测试用例，输出一行，给出x。如果有若干个x满足上述要求，选择按字母序列第一个。样例输入样例输出prettywomenwalkingdownthestreetenwet注：试题来源：WorldFinalsWarm-upContest,UniversityofAlbertaLocalContest在线测试：UVA10252提示试题要求按递增顺序输出两串公共字符的排列。计算方法如下：设S1=a1a2…ala，S2=b1b2…blb。先分别统计S1中各字母的频率c1[i]和S2中各字母的频率c2[i]（1≤i≤26,其中字母‘a’对应数字1,字母‘b’对应数字2,…，字母‘z’对应数字26）。然后计算S1和S2的公共字符的排列：递增枚举i(1≤i≤26)，若i对应的字母在S1和S2中同时存在（（c1[i]≠0）&&（c2[i]≠0））,则字母'a'+i在排列中出现k=min{c1[i]，c2[i]}次。【7Anagram】【问题描述】给出一个字母的集合，请您编写一个程序，产生从这个集合能构成的所有可能的单词。例如：给出单词abc，您的程序产生这三个字母的所有不同的组合——输出单词abc,acb,bac,bca,cab和cba。程序从输入中获取一个单词，其中的一些字母会出现一次以上。对一个给出的单词，程序产生相同的单词只能一次，而且这些单词按字母升序排列。输入：输入给出若干单词。第一行给出单词数，然后每行给出一个单词。一个单词是由A到Z的大写或小写字母组成。大写字母和小写字母被认为是不同的，每个单词的长度小于13。输出：对输入中的每个单词，输出这个单词的字母产生的所有不同的单词。输出的单词按字母升序排列。大写字母排在相应的小写字母前，即'A''a''B''b'...'Z''z'。样例输入样例输出3aAbabcacbaAabAbaaAbabAbAabaAabcacbbacbcacabcbaaabcaacbabacabcaacabacbabaacbacabcaacaabcabacbaa注：试题来源：ACMSouthwesternEuropeanRegionalContest1995在线测试：POJ1256，UVA195提示建立字母与整数间的对应关系：字母‘a’对应0，字母‘A’对应1;…；字母‘z’对应50，字母‘Z’对应51。为了按照字母升序的要求生成单词的所有排列，首先将单词的所有字母转化为数字，然后递增排序数串，排列中每个位置的数字按由左而右顺序从数串中选择。设单词长度为l，数串的第i个位置已访问标志为v1[i]，初始时v1[]清零；数字k对应的字母已使用标志为v2[k]，v2[]为递归程序内的局部变量（0≤i≤l-1，0≤k≤51）。生成所有排列的计算过程为一个递归子程序：voiddfs(intd){//从当前位置d出发，递归计算单词的所有排列if(d==l)输出当前数字排列对应的单词；//生成单词的一个排列}else{v2[]清零;//所有字母未确定for(inti=0;il;i++){//按由左而右顺序从数串中选择d位置的字母：若数串的第i个位置未访问且对应字母未在排列中出现，则设访问标志，该字符进入排列中的第d个位置if(!v1[i]&&!v2[i位置字母对应的数字]){v1[i]=1;v2[i位置字母对应的数字]=1;i位置字母对应的数字放入当前排列的d位置;dfs(d+1);//递归排列的第d+1个位置v1[i]=0;//恢复数串的第i个位置未访问标志}}}}显然，