全国信息学奥林匹克联赛(NOIP2010)复赛 模拟 赛六重点

全国信息学奥林匹克联赛（NOIP2010）复赛模拟赛六 提高组

（请选手务必仔细阅读本页内容） 一．题目概况

二．运行内存限制

三．注意事项

1、 文件名（程序名和输入输出文件名）必须使用小写。

2、 C/C++中函数main(的返回值类型必须是int ，程序正常结束时的返回值必须是0。 3、 symbol 评测时采用的机器配置为：CPU 2.33GHz，内存2G ，上述时限以此配置为准。

1. F ibonacci sequence (fibonacci.pas/c/cpp 【问题描述】

f(n =f(n?1 +f(n?2 *n≥3, f(1 =1, f(2 =1+，这就是著名的Fibonacci sequence 。现在给你两个数x, y, 其中x ≤y, y ≤231?1。

( 你的任务就是求出 ∑y即Fibonacci 数列第x~y项的和除以10000i=xfi mod 10000。

的余数。 【输入】

第一行是一个整数 T(T≤1000 , 表示有多少组数据。 接下来T行，每行两个整数x ，y ，意义如上述。

【输出】

( 输出T 行，对于每组数据，输出∑yi=xfi mod 10000。 【输入输出样例】

【数据约定】

对于80%的数据，T=1，且y ≤106 对于100%的数据，T≤1000，且y ≤231?1

2. N umber (number.pas/c/cpp 【问题描述】

有N(2≤N ≤15 个数a1,a2, ……, an?1, an, 如果在这N 个数中，有且仅有一个数能整除m ，那么整数m 就是一个幸运数，你的任务就是在给定a1,a2, ……, an?1, an的情况下，求出第K 小的幸运数。

【输入】

第一行为一整数数N ，K(2≤N ≤15，1≤K ≤231?1 ，意义如上述。

接下来一行有N 个整数，a1,a2, ……, an?1, an，这N 个整数均不超过231?1。 【输出】

输出一行，仅包含一个整数ans ，表示第K 小的幸运数。答案保证不超过1015。

【输出输出样例】

【数据约定】

对于50%的数据，N ≤5，ans ≤100000 对于80%的数据，N ≤10，ans ≤1015 对于100%的数据，N ≤15，ans ≤1015

3. P ermRLE (PermRLE.pas/c/cpp 【问题描述】

文本压缩的算法有很多种，这里给出一种叫做PermRLE 的压缩算法。 定义一个整数k ， PermRLE算法依赖于一种压缩顺序。所谓的压缩顺序就是一种1~k的排列。例如当k=4的时候，其中一种排列方式是{1,2,4，3},对于字符串“abdb ”，按照这种排列方式进行排列之后就变成了“abbd ”。

对于一段长度为Len 的文本，其中k 能整除Len ，那么PermRLE 算法就是把整个文本分成Len div k 段，然后每一段按照一种1~k的排列方式进行重新排列，重新排列完之后，就把这Len div k段进行合并。对于合并之后得到一个新字符串，PermRLE 算法就是把字符串中连续相同的字符合并成一个字符，例如aabccaabb 合并后就变成了abcab 。

给出一段长度为Len(1≤Len ≤50000 的文本以及一个整数k(1≤k ≤16 其中k 能整除Len ，你的任务就是找出一种1~k的排列，使得PermRLE 算法压缩之后的文本的长度最小。当然，为了降低难度，你只需输出文本压缩之后最小的长度，而不需要输出这种排列。

【输入】

输入第一行有一个整数k(1≤k ≤16 ，意义如上所述。 接下来一行有一个字符串，保证字符串的长度能被k 整除，且字符串里仅含有小写字母。

【输出】

输出一行，仅包含文本压缩之后的最小长度。 【输出输出样例】

【样例解释】 对于样例一，k 的排列是1 4 3 2，然后原字符串变成

aacbbbacccba ，压缩之后变成acbacba ，长度为7，可以证明，这是最小答案。 对于样例二，无论k 的排列如何，都无法使压缩之后的字符串长度小于12

【数据约定】

对于50%的数据，1≤k ≤5，1≤Len ≤1000 对于100%的数据，1≤k ≤16，1≤Len ≤50000

4. T reeCount (treecount.pas/c/cpp 【问题描述】

给出一个有N(2≤N ≤1000 个顶点M(N?1≤M ≤N ?(N ?1 /2 条边的无向连通图。设dist1[i]表示在这个无向连通图中，顶点i 到顶点1的最短距离。

现在要求你在这个图中删除M ?(N?1 条边，使得这个图变成一棵树。设dist2[i]

表示在这棵树中，顶点i 到顶点1的距离。 你的任务是求出有多少种删除方案，使得对于任意的i ，满足dist1[i]=dist2[i]。

【输入】

第一行，两个整数，N ，M ，表示有N 个顶点和M 条边。

接下来有M 行，每行有3个整数x, y, len(1≤x, y ≤n, 1≤len ≤100 ，表示顶点x 和顶点y 有一条长度为len 的边。

数据保证不出现自环、重边。

【输出】 输出一个整数，表示满足条件的方案数 mod 2147483647的答案。 【输出输出样例】

【样例解释】

删除第一条边或者第三条边都能满足条件，所以方案数为2。 【数据规模】

对于30%的数据，2≤N ≤5，M ≤10

对于50%的数据，满足条件的方案数不超过10000 对于100%的数据，2≤N ≤1000

【输入】

第一行，两个整数，N ，M ，表示有N 个顶点和M 条边。

接下来有M 行，每行有3个整数x, y, len(1≤x, y ≤n, 1≤len ≤100 ，表示顶点x 和顶点y 有一条长度为len 的边。

数据保证不出现自环、重边。

【输出】 输出一个整数，表示满足条件的方案数 mod 2147483647的答案。 【输出输出样例】

【样例解释】

删除第一条边或者第三条边都能满足条件，所以方案数为2。 【数据规模】

对于30%的数据，2≤N ≤5，M ≤10

对于50%的数据，满足条件的方案数不超过10000 对于100%的数据，2≤N ≤1000

本文来源：https://www.bwwdw.com/article/z82a.html