pascal高手快来！！！急！！！

pascal高手快来！！！急！！！

Pascal模拟题
问题名称 文件名 输入 输出 时限 分值
序列 sequence.exe sequence.in sequence.out 2s 100
连分数 faction.exe faction.in faction.out 1s 100
词链 link.exe link.in link.out 1s 100
Geodetic集合 geo.exe geo.in geo.out 1s 100
序列(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.in sequence.out
3
2
5
9
4
样例说明：存在如下四个数列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/b¬1，a2/b2，……。现在Cindy的研究中出现了一个连分数 ，她希望你能帮她求出它的渐近分数序列的第m项。请用二元组(am，bm)的形式给出答案，并且对于答案的中的两个数，只需要输出它们模9973的余数即可。
输入(faction.in)
第一行为一个整数n，m，分别表示连分数的循环节长度和需要求的渐近分数的项数。下接n行每行一个整数pi，描述连分数。
输出(faction.out)
空格分隔的两个整数am、bm。
样例
faction.in faction.out
1 6
1 8 13
数据范围
60%的数据，m<=105
100%的数据，n<=10，m <=109

词链（link.exe）
问题描述
给定一个仅包含小写字母的英文单词表，其中每个单词最多包含50个字母。
如果一张由一个词或多个词组成的表中，每个单词（除了最后一个）都是排在它后面的单词的前缀，则称此表为一个词链。例如下面的单词组成了一个词链：
i
int
integer
而下面的单词不组成词链：
integer
intern
请在给定的单词表中取出一些词，组成最长的词链。最长的词链就是包含单词数最多的词链。
数据保证给定的单词表中，单词互不相同，并且单词按字典顺序排列。
输入(link.in)
第一行一个整数n，表示单词表中单词数
下接n行每行一个单词。
输出(link.out)
一个整数，表示最长词链长度。
样例
link.in link.out
5
i
int
integer
intern
internet 4
数据范围
50%的数据，n<=1000
100%的数据，n<=10000
Geodetic集合(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}。

给定一个图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.in geo.out
5 6
1 2
1 3
2 3
2 4
3 5
4 5
3
2 5
5 1
2 4 2 3 4 5
1 3 5
2 4

数据范围
100%的数据，n<=40

各题简要分析：

sequence序列：
令S序列的第一项为k，那么后面几项就可以写成关于k的多项式：
S1=k
S2=2*m1-k
S3=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)=max{1，F(j)+1,当word[j]是word[i]的前缀}
Ans=max{F(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扩展，按得到的BFS序列进行递推。
设 min[i, j]为从i到j的最短路长度
设f[i, j]表示从i到j点的最短路覆盖的节点集合，
f[i, j] = f[i, k] U {j} k={1..n} and (min[i, k]+1=min[i, j]）and (k,j)存在
对于输入的每个v,u对，输出f[v,u]中的所有点就可以了。

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息