NOIP2008提高组赛模拟试题NOIP2008提高组复赛模拟试题.doc

NOIP 2008复赛模拟试题 (提高组) PAGE  PAGE 13 ? 全国青少年信息学奥林匹克 联赛复赛模拟试题 湖南省长沙市第一中学 周祖松 试题名称infinitremovegamefire目录infinitremovegamefire输入文件名infinit.inremove.ingame.infire.in输出文件名infinit.outremove.outgame.outfire.out试题类型非交互式程序题非交互式程序题非交互式程序题非交互式程序题附加文件无无无无时限0.1秒0.1秒0.1秒0.1秒 1．无限序列 (infinit.pas/c/cpp) 【问题描述】 我们按以下方式产生序列：1、 开始时序列是： 1 ；2、 每一次变化把序列中的 1 变成 10 ，0 变成 1。 经过无限次变化，我们得到???列1011010110110101101...。总共有 Q 个询问，每次询问为：在区间A和B之间有多少个1。 任务 写一个程序回答Q个询问 输入 第一行为一个整数Q，后面有Q行，每行两个数用空格隔开的整数a, b。 输出 共Q行，每行一个回答 约定 1 = Q = 5000 1 = a = b 263 样例 infinit.in infinit.out 12 8 4  分析： 我们先看看序列变化规律，S1 = 1, S2 = 10, S3 = 101, S4 = 10110, S5 = 等等. Si 是 S（i+1）的前缀。 序列Si 是由序列 S（i-1） 和 S（i-2）, 连接而成的。 即Si = Si-1 + Si-2 (实际上上是Fibonacci数列)。 找到规律以后，我们可以可以用递归的方法求出从从位置1到位置X之间所有的1的个数，用一个函数F计算，结果为f(b)-f(a-1)。 时间复杂度为： O(Q * log MAX_VAL) 此题需要先找出数学规律，再进用递归实现。主要考查选手的数学思维能力和递归程序的实现。 源程序： const nn=92; //进行92次的数列扩展后，数列长度就会超过给定的数据范围, var f,ft:array[0..nn] of int64; q,i,j,l1,l2:longint; a,b:qword; procedure prapre;{预处理} var i:longint; begin f[0]:=1;f[1]:=1; ft[0]:=0;ft[1]:=1; for i:=2 to nn do begin f[i]:=f[i-1]+f[i-2]; ft[i]:=ft[i-1]+ft[i-2]; end; end; function find(a:int64;ll:longint):int64;{求这个数列的前a个有多少个1} begin if a=0 then exit(0); find:=0; if a=f[ll] then find:=ft[ll] else if a=f[ll-1] then find:=find(a,ll-1) else find:=ft[ll-1]+find(a-f[ll-1],ll-2); end; begin assign(input,infinit.in);reset(input); assign(output,infinit.out);rewrite(output); prapre; readln(q); for i:=1 to q do begin readln(a,b); writeln(find(b,nn)-find(a-1,nn)); end; close(input);close(output); end. 2．删数 (remove.pas/c/cpp) 【问题描述】 有N个不同的正整数数x1, x2, ... xN 排成一排，我们可以从左边或右边去掉连续的i个数（只能从两边删除数），1=i=n，剩下N-i个数，再把剩下的数按以上操作处理，直到所有的数都被删除为止。 每次操作都有一个操作价值，比如现在要删除从i位置到k位置上的所有的数。操作价值为|xi – xk|*(k-i+1)，如果只去掉一个数