NOIP 2008复赛模拟试题 (提高组)

全国青少年信息学奥林匹克

联赛复赛模拟试题

湖南省长沙市第一中学 周祖松

试题名称 目录 输入文件名 输出文件名 试题类型 附加文件 时限 infinit infinit infinit.in infinit.out 非交互式程序题 无 0.1秒 remove remove remove.in remove.out 非交互式程序题 无 0.1秒 game game game.in game.out 非交互式程序题 无 0.1秒 fire fire fire.in fire.out 非交互式程序题 无 0.1秒

1．无限序列

(infinit.pas/c/cpp)

【问题描述】

我们按以下方式产生序列： 1、 开始时序列是： \；

2、 每一次变化把序列中的 \变成 \，\变成 \。 经过无限次变化，我们得到序列\。 总共有 Q 个询问，每次询问为：在区间A和B之间有多少个1。 任务 写一个程序回答Q个询问

输入 第一行为一个整数Q，后面有Q行，每行两个数用空格隔开的整数a, b。 输出 共Q行，每行一个回答 约定

? 1 <= Q <= 5000

63

? 1 <= a <= b < 2 样例 infinit.in 1 2 8 分析：

我们先看看序列变化规律，S1 = \\等等. Si 是 S（i+1）的前缀。

infinit.out 4 ?

1

NOIP 2008复赛模拟试题 (提高组)

序列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;

?

2

NOIP 2008复赛模拟试题 (提高组)

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)，如果只去掉一个数，操作价值为这个数的值。 任务

如何操作可以得到最大值，求操作的最大价值。 Input Data

输入文件remove.in 的第一行为一个正整数N，第二行有N个用空格隔开的N个不同的正整数。Output Data

输出文件remove.out 包含一个正整数，为操作的最大值 约束和提示 3<=N<=100

N个操作数为1..1000 之间的整数。 样例

remove.in 6

54 29 196 21 133 118 remove.out 768

说明，经过3 次操作可以得到最大值，第一次去掉前面3个数54、29、196，操作价值为426。第二次操作是在剩下的三个数（21 133 118）中去掉最后一个数118，操作价值为118。第三次操作去掉剩下的2个数21和133 ，操作价值为224。操作总价值为426+118+224=768。 分析：

这是一个基本的动态规划问题

我们用F[i][j]表示按规则消去数列a[i..j]得到的的最大值; 删除第i个数得到的最大值为a[i];

删除a[i..j]得到的最大值为：一次性删除数列a[i..j]得到的值是|a[i]-a[j]|*(j-i+1) 或者是先删除a[i..k] 再删除a[k+1..j], k 在i 到j-1之间,得到的值是 F[i][k]+F[k+1][j].

3

?