资源描述：
《全国信息学奥林匹克联赛(noip2010 )复赛 模拟 赛六》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、全国信息学奥林匹克联赛（NOIP2010）复赛模拟赛六提高组全国信息学奥林匹克联赛（NOIP2010）复赛模拟赛六提高组（请选手务必仔细阅读本页内容）一．题目概况Fibonacci中文题目名称NumberPermRLETreeCountSequence英文题目名称fibonaccinumberpermrletreecount可执行文件名fibonacci.exenumber.exepermrle.exetreecount输入文件名fibonacci.innumber.inpermrle.intreecount.in输
2、出文件名fibonacci.outnumber.outpermrle.outtreecount.out每个测试点时限1秒1~2秒1~4秒1秒测试点数目10101010每个测试点分值10101010附加样例文件有有有有全文比较全文比较全文比较全文比较结果比较方式过滤行末空格过滤行末空格过滤行末空格过滤行末空格及文末回车及文末回车及文末回车及文末回车题目类型传统传统传统传统二．运行内存限制内存上限64M64M64M64M三．注意事项1、文件名（程序名和输入输出文件名）必须使用小写。2、C/C++中函数main()的返回值
3、类型必须是int，程序正常结束时的返回值必须是0。3、symbol评测时采用的机器配置为：CPU2.33GHz，内存2G，上述时限以此配置为准。EditedbyAcFast全国信息学奥林匹克联赛（NOIP2010）复赛模拟赛六提高组1.Fibonaccisequence(fibonacci.pas/c/cpp)【问题描述】?(?)=?(?−1)+?(?−2)*?≥3,?(1)=1,?(2)=1+，这就是著名的Fibonaccisequence。现在给你两个数x,y,其中x≤y,y≤231−1。?你的任务就是求出∑?(
4、?)???10000。即Fibonacci数列第x~y项的和除以10000i=x的余数。【输入】第一行是一个整数?(?≤1000),表示有多少组数据。接下来?行，每行两个整数x，y，意义如上述。【输出】?输出T行，对于每组数据，输出∑?(i)???10000。i=x【输入输出样例】fibonacci.infibonacci.out212155976127255【数据约定】对于80%的数据，?=1，且y≤106对于100%的数据，?≤1000，且y≤231−1EditedbyAcFast全国信息学奥林匹克联赛（NOIP
5、2010）复赛模拟赛六提高组2.Number(number.pas/c/cpp)【问题描述】有N(2≤N≤15)个数?1,?2,……,??−1,??,如果在这N个数中，有且仅有一个数能整除m，那么整数m就是一个幸运数，你的任务就是在给定?1,?2,……,??−1,??的情况下，求出第K小的幸运数。【输入】第一行为一整数数N，K(2≤N≤15，1≤K≤231−1)，意义如上述。接下来一行有N个整数，?,?,……,?,?，这N个整数均不超过231−1。12?−1?【输出】输出一行，仅包含一个整数ans，表示第K小的幸运数
6、。答案保证不超过1015。【输出输出样例】number.innumber.out24823number.innumber.out21001250012532767【数据约定】对于50%的数据，N≤5，ans≤100000对于80%的数据，N≤10，ans≤1015对于100%的数据，N≤15，ans≤1015EditedbyAcFast全国信息学奥林匹克联赛（NOIP2010）复赛模拟赛六提高组3.PermRLE(PermRLE.pas/c/cpp)【问题描述】文本压缩的算法有很多种，这里给出一种叫做PermRLE的
7、压缩算法。定义一个整数k，PermRLE算法依赖于一种压缩顺序。所谓的压缩顺序就是一种1~k的排列。例如当k=4的时候，其中一种排列方式是{1,2,4，3},对于字符串“abdb”，按照这种排列方式进行排列之后就变成了“abbd”。对于一段长度为Len的文本，其中k能整除Len，那么PermRLE算法就是把整个文本分成Lendivk段，然后每一段按照一种1~k的排列方式进行重新排列，重新排列完之后，就把这Lendivk段进行合并。对于合并之后得到一个新字符串，PermRLE算法就是把字符串中连续相同的字符合并成一个字
8、符，例如aabccaabb合并后就变成了abcab。给出一段长度为Len(1≤Len≤50000)的文本以及一个整数k(1≤k≤16)其中k能整除Len，你的任务就是找出一种1~k的排列，使得PermRLE算法压缩之后的文本的长度最小。当然，为了降低难度，你只需输出文本压缩之后最小的长度，而不需要输出这种排列。【输入】输入第一行有一个整数k(1
