雅礼NOIP试题1.docx

模拟一问题名称文件名输入输出时限分值序列sequence.exesequence.insequence.out2s100连分数faction.exefaction.infaction.out1s100词链link.exelink.inlink.out1s100Geodetic集合geo.exegeo.ingeo.out1s100序列(sequence.exe)问题描述 有一个非递减的整数序列S1，S2，S3，Sn+1（Si=Si+1）。定义序列m1，m2，mn为S的“M序列”，其中mi=(Si+Si+1)/2。 例如，S=(1, 3, 3, 5)，则m=(2, 3, 4)。 现在给你序列m，要你求有多少个S序列的“M序列”是序列m。输入(sequence.in) 第一行一个整数n， 下接n行，每行一个整数mi输出(sequence.out) 一个整数，表示有多少个S序列的“M序列”是序列m样例 sequence.insequence.out32594样例说明：存在如下四个数列S满足要求：2，2，8，10；1，3，7，11；0，4，6，12；-1，5，5，13。数据范围 50%的数据n=1000，mi=20000 100%的数据2=n=100000，mi=109. 连分数(faction.exe)问题描述 Cindy新学了无理数，老师教她了一种用有理数逼进无理数的方法：找到这个无理数相应的无限循环连分数。 例如，我们可以通过分别取出连分数中的一层、两层、三层、，而忽略其他部分，这样就可以得到一个有理数序列，我们称之为该连分数的渐近分数序列。黄金分割数的渐近分数是1/1，1/2，2/3，3/5，5/8，8/13。Cindy对其中的连分数形式尤为感兴趣，为了简化，她准备研究的连分数都是如下形式的：她用一个简单的记号表示这种连分数：。例如黄金分割数的连分数简记为对于每一个这样的连分数，都有其相应的渐近分数序列：a1/b1，a2/b2，。现在Cindy的研究中出现了一个连分数，她希望你能帮她求出它的渐近分数序列的第m项。请用二元组(am，bm)的形式给出答案，并且对于答案的中的两个数，只需要输出它们模9973的余数即可。输入(faction.in) 第一行为一个整数n，m，分别表示连分数的循环节长度和需要求的渐近分数的项数。下接n行每行一个整数pi，描述连分数。输出(faction.out) 空格分隔的两个整数am、bm。样例faction.infaction.out1 618 13数据范围60%的数据，m=105100%的数据，n=10，m =109词链（link.exe）问题描述 给定一个仅包含小写字母的英文单词表，其中每个单词最多包含50个字母。 如果一张由一个词或多个词组成的表中，每个单词（除了最后一个）都是排在它后面的单词的前缀，则称此表为一个词链。例如下面的单词组成了一个词链： i int integer而下面的单词不组成词链： integer intern 请在给定的单词表中取出一些词，组成最长的词链。最长的词链就是包含单词数最多的词链。 数据保证给定的单词表中，单词互不相同，并且单词按字典顺序排列。输入(link.in) 第一行一个整数n，表示单词表中单词数 下接n行每行一个单词。输出(link.out) 一个整数，表示最长词链长度。样例link.inlink.out5iintintegerinterninternet4数据范围 50%的数据，n=1000 100%的数据，n=10000Geodetic集合(geo.exe)问题描述 图G是一个无向连通图，没有自环，并且两点之间至多只有一条边。我们定义顶点v,u最短路径就是从v到u经过边最少的路径。所有包含在v-u的最短路径上的顶点被称为v-u的Geodetic顶点，这些顶点的集合记作I(v, u)。我们称集合I(v, u)为一个Geodetic集合。例如下图中，I(2, 5)=2, 3, 4, 5，I(1, 5)=1, 3, 5，I(2, 4)=2, 4。13254给定一个图G和若干点对v,u，请你分别求出I(v, u)。输入(geo.in) 第一行两个整数n,m，分别表示图G的顶点数和边数（顶点编号1-n） 下接m行，每行两个整数a,b表示顶点a和b之间有一条无向边。 第m+2行有一个整数k，表示给定的点对数。 下接k行，每行两个整数v,u。输出(geo.out) 共k行，每行对应输入文件中每一个点对v,u，按顶点编号升序输出I(v, u)。同一行的每个数之间用空格分隔。样例geo.ingeo.out5 61 21 32 32 43 54 532 55 12 42 3 4 51 3 52 4数据范围 100%的数据，n=40各题简要分析：sequence序列： 令S序列的第一项为k，那么后面几项就可以写成关于k的多项式：S1=kS2=2*m1-kS3=2*m2-2*m1+k然后根据S序列的非递减性质，有S1=S2=S3=.所以有 k=2*m1-k 2*m1-k=2*m2-2*m1+k 可以得到n个关于k的不等式，而且都是有规律的，可以在O(n)的时间内解出形如 a=k=b的结果。由于k的值和S序列是一一对应的，所以k的取值的个数(b-a)就是满足要求的S序列的个数。faction连分数： 本题是原创的，重点考察递推和用矩阵乘法优化递推。 由递推式： k = (m-1) mod n + 1可得 ; 直接按照这个递推式计算，复杂度O(m)，预计得分60%。 上面的递推式对应的矩阵运算是：所以有 其中c是(m mod n)部分的余式矩阵的乘积。由于计算矩阵幂时间复杂度为O(logm)，所以总的算法复杂度是O(n+logm)，预计得分100%。Link词链： 本题用动态规划是容易的，设f(i)表示前i个单词可以构成包含第i个单词的最长词链。 F(i)=max1，F(j)+1,当wordj是wordi的前缀 Ans=maxF(i) 这样算法的复杂度是O(n2)，预计得分50%。 其实本题有很简单的贪心算法。 用一个栈存储当前的以第i个单词结尾的最长词链，第i+1个单词加在栈的结尾（通过出栈保持栈所存储的是一个词链）。 例如： i 栈 ： i int 栈： i int integer 栈： i int interger intern 栈： i int intern （interger出栈） internet 栈： i int intern internet 可以证明，在第i个单词插入后，当前在栈中的词链就是包含第i个单词的最长词链。 这样由于每个单词进栈出栈分别一次，所以算法的复杂度是O(n) 贪心算法预计得分100%Geodetic集合： 本题是由pku上一道试题改编的，考察图的有关知识。算法就是从每个点出发进行BFS扩展，