tceic.com
学霸学习网 这下你爽了
相关标签
当前位置:首页 >> IT认证 >>

NOIP2008提高组复赛模拟试题


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

全国青少年信息学奥林匹克 联赛复赛模拟试题
湖南省长沙市第一中学
试题名称 目录 输入文件名 输出文件名 试题类型 附加文件 时限 infinit infinit infinit.in infinit.out 非交互式程序题 无 0.1 秒 remove remove remove.in remove.out 非交互式程序题 无 0.1 秒

周祖松
game game game.in game.out fire fire fire.in fire.out 非交互式程序题 无 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 63 ? 1 <= a <= b < 2 样例 infinit.in 1 2 8 infinit.out 4

分析: 我们先看看序列变化规律,S1 = "1", S2 = "10", S3 = "101", S4 = "10110", S5 = "10110101", 等等. Si 是 S(i+1)的前缀。

?

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; 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; //进行92次的数列扩展后,数列长度就会超过给定的数据范围,

?

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

?

NOIP 2008 复赛模拟试题 (提高组)
我们得到状态转移方程: F[i][i]=a[i], for i=1..N 对于任意的 i<j,有:

F[i][j]=max{|a[i]-a[j]|*(j-i+1), f[i][i]+f[i+1][j], F[i][i+1]+F[i+2][j],...,F[i][j-1]+F[j][j]} F[1,n]为所求的解 时间复杂度:o(N^3);

此题需要选手对算法的时间复杂度进行分析,简单的搜索是不能在规定时间内求出结果,必需使用 高效的算法,主要考查选手运用高效算法——动态规划解决问题的能力。

源程序: var n:longint; a:array[1..100] of longint; f:array[0..101,0..101] of longint; procedure init; var i:longint; begin readln(n); for i:=1 to n do read(a[i]); end; function work(i,k:longint):longint; begin if i=k then exit(a[i]); exit(abs(a[i]-a[k])*(k-i+1)); end; function max(a,b:longint):longint; begin if a>b then max:=a else max:=b; end; procedure main; var i,j,p:longint; begin

?

4

NOIP 2008 复赛模拟试题 (提高组)
fillchar(f,sizeof(f),0); for i:=1 to n do f[i,i]:=a[i]; for i:=n downto 1 do for j:=i+1 to n do begin for p:=i+1 to j+1 do f[i,j]:=max(f[i,j],f[p,j]+work(i,p-1)); for p:=j-1 downto i-1 do f[i,j]:=max(f[i,j],f[i,p]+work(p+1,j)); end; end; procedure print; begin writeln(f[1,n]); end; begin assign(input,'remove.in');reset(input); assign(output,'remove.out');rewrite(output); init; main; print; close(input);close(output); end.

3.俄罗斯方块
(game.pas/c/cpp) 【问题描述】 相信大家都玩过“俄罗斯方块”游戏吧,“俄罗斯方块”是一个有趣的电脑小游戏,现有一个 有C列、行不受限定游戏平台,每一次下落的方块是下列的7个图形的一种:

在下落的过程中,游戏者可以作90、 180或270 度旋转,还可以左右移动,对于每一次方块落 地,我们要求方块的每一部分都必须与地面(最底面或己落下的方块上表面)接触,例如,有一个 宽度为6列的平台,每一列的初始高度(已经占用的方格数)分别为2, 1, 1, 1, 0 和 1。编号为5的方

?

5

NOIP 2008 复赛模拟试题 (提高组) 块下落,有且仅有5种不同的落地方法:

现给出每一列的初始高度和下落方块的形状,请你编写一个程序,求出落地的方法总数,也就 是落地后,地表面形成的不同的形状总数。 输入: 第一行为二个整数C和P,1 ≤ C ≤ 100, 1 ≤ P ≤ 7,表示列数和下落方块的编号 第二行共有用一个空隔隔开的C个整数,每一个数字在 0 到 100,之间(包含0和100),表示每一列 的初始高度 输出: 输出为一个整数,表示落地的方法总数 样例数据 Input1 Input2 Input3 6 5 5 1 9 4 2 1 1 1 0 1 0 0 0 0 0 4 3 5 4 6 5 7 6 6 Output1 Output2 Output3 5 7 1

分析:
我们用编码序列表示下落方块的底部, 比如编号为5的方块经过4种旋转得到4个序列: { 1, 1, 1 }, { 1,

2 }, { 2, 1, 2 } 和 { 2, 1 }。 如果序列A上每一个元素都加上同一个常数得到序列B, 我们就称序列A和序列B是对应 的,比如序列{ 2, 1, 2 }与{ 5, 4, 5 }对应,但不与{ 4, 5, 4 } 或 { 5, 4 }对应。 可以看出,当且仅当方块的序列与地面相对位置的高度形成的序列对应,那么这个方 块能与地面能结合。因此对于给定的方块和地面,我们只要简单地检查所有旋转所形 成的可能的形状,这样我们就可以用枚举法求解。 此题比较简单,用枚举法解决,在实现中要考虑各种变换。主要考查选手的基本的程序实现能力。 源程序:
program game; const MAXS = 100; fin='game.in'; fout='game.out'; var v : array[1..MAXS] of longint;
6

?

NOIP 2008 复赛模拟试题 (提高组)
s, f, i, count : longint; begin assign(input,fin);reset(input); assign(output,fout);rewrite(output); readln(s, f); if (f=4)or(f=7) then begin dec(f); for i:=1 to s do read(v[s-i+1]); end else for i:=1 to s do read(v[i]); count := 0; case f of 1: begin count:=s; for i:=1 to s-3 do if (v[i]=v[i+1])and(v[i]=v[i+2])and(v[i]=v[i+3]) then inc(count); end; 2: begin for i:=1 to s-1 do if v[i]=v[i+1] then inc(count); end; 3: begin for i:=1 to s-1 do if v[i]=v[i+1]+1 then inc(count); for i:=1 to s-2 do if (v[i]=v[i+1])and(v[i]=v[i+2]-1) then inc(count); end; 5: begin for i:=1 to s-2 do if ((v[i]-v[i+1]=1)or(v[i]-v[i+1]=0))and(v[i]=v[i+2]) then inc(count); for i:=1 to s-1 do if abs(v[i]-v[i+1])=1 then inc(count); end; 6: begin for i:=1 to s-2 do if (v[i+1]=v[i+2])and((v[i+1]-v[i]=1)or(v[i+1]-v[i]=0)) then inc(count); for i:=1 to s-1 do if (v[i]=v[i+1])or(v[i]=v[i+1]+2) then inc(count); end; end; writeln(count); {如果是第四种和第七种,则变成第三种和第六种}

?

7

NOIP 2008 复赛模拟试题 (提高组)
close(input); close(output); end.

4.燃烧木棍
(fire.pas/c/cpp)
【问题描述】 Tom 是调皮的孩子,特别喜欢玩火,现在他手上有若干 根长度分别为 1 和 2 的木棍,还有一张不能燃烧的平板,他 把平板划分成长度为 1 的单元格,并标上座标。然后按以下 规则把平板上的木棍组成一个连通图:木棍的两端必须放在 单元格的顶点上。即长度为 1 的木棍放在单元格的某一边上, 长度为 2 的木棍放在单元格的对角线上。 Tom 的点火规则是,只能从木棍的两端点火,而不能 从木棍的中间点火。如图,不能在 A 点点火,但在 C 点或 B 点点火都是充许的。点火后,火会沿着木棍向前燃烧(每根都有自己的燃烧速度),并能点燃与它 相接的其它木棍。 任务:写一程序计算从哪里开始点火,使得燃烧的总时间最短,输出最短时间。 Input Data 输入文件 bete.in 第一行为一个正整数 N,表示组成图形的木棍数目,后面共有 N 行,每行 5 个数: X1 Y1 X2 Y2 T,其中(X1, Y1)和(X2, Y2)分别表示木棍两端的坐标,T 表示木棍燃 烧时间,是指从木棍的某一端点火燃烧到别一端,燃完所需的时间。 Output Data 输出文件 bete.out 是一个保留 4 位小数的实数,表示所有木棍完全燃烧的最少时间。 约束 1≤n≤40 保证图形是连通的,所有的木棍长度都是 1 或 -200≤X1, Y1, X2, Y2≤200; 0≤T≤107. 如果你的输出结果与标准答案相差小于 0.001,则认为你的结果正确。 样例 1 fire.in fire.out 解释 1 0 0 1 1 1 样例 2 fire.in 1.0000 从任一端点火都行,燃烧时间都是 1

2 ,没有任何两根木棍重合.

fire.out

解释
8

?

NOIP 2008 复赛模拟试题 (提高组) 5 0 1 0 0 2 3.2500 0 0 0 0 2 0 0 1 1 1 1 1 0 1 1 1 10 1 1 1 在 (0,0)位置点火 木棍 1, 3 和 4 将被点燃,燃烧 0.5 分钟后,木棍 2 将被从中间点燃向两端 燃烧,再过 0.5 分钟,木棍 1, 3, 4 将被完全燃烧,木棍 5 将被点燃并在 1 分钟后燃烧完 (比木棍 2 早燃完)。 木棍 2 从中间向两端燃烧 0.5 分钟以后, 变成两小段, 每段的燃烧时间是 4.5 分钟。但因为此时两小段木棍的另一端也同时被点燃,燃烧速度变成原来的 两倍,还需 2.25 分钟的燃烧时间, 所以总时间: 1 + 2.25 = 3.25 fire.out 35.0000 解释 在 (1,2)位置点火, 木棍(1 1, 1 2) 和(1 2, 2 2)将燃烧 10 分 钟。. 最后一根木棍在 10 分钟后从两端被点燃,燃烧时间为 25 分钟。

样例 3 fire.in 3 1 1 1 2 10 1 2 2 2 10 1 1 2 2 50

分析:

在此题问题中,木棍构成的是一个连通图,如果我们直接构图处理比较复杂, 我们对原问题进行转换,由于木棍与木棍之间只能在木棍的两端或中间相交。我们把 每根木棍拆分成两根相等的小木棍,这样,木棍的数量增加了一倍,原问题就转化为, 木棍与木棍之间只能在木棍的两端相交,这样处理起来就比较方便。 我们以木棍为边,木棍与木棍之间的交点为顶点,构建一个连通图,问题变为 寻找一个合适的顶点,使得点燃以后完全燃烧的时间最短。 很显然,燃烧时间等于点燃的顶点到图中最远点的时间,如下图

我们可以先求出某个点到其它所有点的最短时间,在这里我们可以使用 Floyd’s 算法求出任意两点之间的最短时间,时间复杂度为 O(N3)。 注意,我们在这里用 Floyd’s 算法求的是第个点被点燃的时间,每个点被点燃, 并不代表所有木棍都被完全燃烧,如上图。 求出从某个点到其它点的最短时间以后,余下的问题是检查每一边是否完全燃 烧。如果没有完全燃烧,求出剩余边燃烧所需最长时间。 对于燃烧时间为 L 的木棍, 它的两端被点燃的时刻为 T1 和 T2, 如果 T1 = T2+L 或者是 T2 = T1+L,那么燃烧到 T1 和 T2 的最大时刻,这根木棍己经完全燃烧。

?

9

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

如果 T1 与 T2 之间的时间差不等于 L,那么就说明火是从不同的路径燃烧到这 根木棍的两端。火将从两端向中间燃烧,并在木棍内的某个点燃完,在简单情况中, 如果是从两端同时点燃,燃烧时间为 L/2。更一般地,如果 T1 与 T2 不等,我们设一 端是从 0 时刻点燃,另一端是从 T 时刻点燃,那么这根木棍的燃烧时间为 T + (L-T)/2. 此题比较复杂,先要构图,并且要对原图形进行转换,再用 Floyd’s 算法求出任意两点之间的 最少时间,最后还要检查所有的边是否燃烧,此题考查选手用图解决问题的能力,并且此题 不能简单的套用 Floyd’s 算法,需要选手在解决问题中灵活运用经典算法。
源程序: Program Matches; Const MaxN=42; { N根木棍的端点 } MaxG=2*MaxN+1; { 拆分以后的最大顶点数 } Infinity=MaxLongInt; { 燃烧时间的最大值 } Var N:Integer; Match:Array[1..MaxN] Of Record X1,Y1,X2,Y2:Integer; Time:LongInt; End; NG:Integer; Vertex:Array[1..MaxG]Of Record X,Y:Integer; End; Edge,Distance:Array[1..MaxG,1..MaxG]Of LongInt; Res:Extended; ResX,ResY:Integer; Procedure Init;{输入} Var I:Integer; Begin Read(N); For I:=1 To N Do With Match[I] Do Read(X1,Y1,X2,Y2,Time); End; Function GetVertex(VX,VY:Integer):Integer; { intoarce numarul varfului cu coordonatele date daca lipseste, este creat } Var I:Integer; Begin For I:=1 To NG Do { 燃烧最少时间 } { 图的顶点信息} { 每根木棍构成边的信息:端点座标和燃烧时间 }

?

10

NOIP 2008 复赛模拟试题 (提高组)
With Vertex[I] Do If (X=VX) And (Y=VY) Then Begin GetVertex:=I; Exit; End; Inc(NG); { Daca varful nu este gasit } With Vertex[NG] Do Begin X:=VX; Y:=VY; For I:=1 To NG-1 Do Begin Edge[I,NG]:=Infinity; Edge[NG,I]:=Infinity; End; Edge[NG,NG]:=0; End; GetVertex:=NG; End; Procedure AddEdge(X1,Y1,X2,Y2:Integer; Time:Longint); { Functia adauga muchie intre varfuri } Var A,B:Integer; Begin A:=GetVertex(X1,Y1); B:=GetVertex(X2,Y2); Edge[A,B]:=Time; Edge[B,A]:=Time; End; Procedure BuildGraph; { 构图 } Var I:Integer; Begin NG:=0; For I:=1 To N Do With Match[I] Do Begin AddEdge(X1*2,Y1*2,X1+X2,Y1+Y2,Time); AddEdge(X1+X2,Y1+Y2,X2*2,Y2*2,Time); End; End; Procedure FindShortestPaths;{ Var K,I,J:Integer; Begin Distance:=Edge; For K:=1 To NG Do

Floyd’s算法求任意两点之间的最短时间}

?

11

NOIP 2008 复赛模拟试题 (提高组)
For I:=1 To NG Do If Distance[I,K]<Infinity Then For J:=1 To NG Do If Distance[K,J]<Infinity Then If Distance[I,K]+Distance[K,J]<Distance[I,J] Then Distance[I,J]:=Distance[I,K]+Distance[K,J]; End; Function BurnAt(At:Integer):Extended; Var I,J:Integer; Curent,ThisEdge:Extended; Begin Curent:=0; For I:=1 To NG Do If Distance[At,I]>Curent Then Curent:=Distance[At,I]; For I:=1 To NG Do For J:=I+1 To NG Do If Edge[I,J]<Infinity Then Begin If (Distance[At,I]<Distance[At,J]+Edge[I,J]) And (Distance[At,J]<Distance[At,I]+Edge[I,J]) Then Begin If Distance[At,I]<Distance[At,J] Then ThisEdge:=Distance[At,J]+(Edge[I,J]-(Distance[At,J]-Distance[At,I]))/2 Else ThisEdge:=Distance[At,I]+(Edge[I,J]-(Distance[At,I]-Distance[At,J]))/2; If ThisEdge>Curent Then Curent:=ThisEdge; End; End; BurnAt:=Curent; End; Procedure Solve; Var I:Integer; Curent:Extended; Begin Res:=Infinity; For I:=1 To NG Do With Vertex[I] Do If Not Odd(X) And Not Odd(Y) Then Begin Curent:=BurnAt(I); If Curent<Res Then End; End; Begin Assign(Input,'fire.in'); ReSet(Input); Assign(Output,'fire.out'); ReWrite(Output); Init; BuildGraph; Res:=Curent;

?

12

NOIP 2008 复赛模拟试题 (提高组)
FindShortestPaths; Solve; Writeln(Res/2:0:4); Close(Input);Close(Output); End.

?

13


推荐相关:

NOIP2008_提高组_复赛试题

NOIP2008_提高组_复赛试题_学科竞赛_高中教育_教育专区。全国信息学奥林匹克联赛...染完之后,模拟输出序列就可以了。 第 8 页共 8 页 文档贡献者 年华似火...


NOIP2008提高组复赛试题

Noip2010提高组试题 10页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 NOIP2008提高组复赛试题 NOIP2008提高组复赛...


NOIP2008提高组解题报告

【题目类型】 模拟 【建议编程时间】 10 分钟(细心一些,避免出错). 【解题...NOIP2008 复赛提高组第四题 twostack 解题报告(2008-11-16 15:19:06) 标签...


NOIP2008提高组复赛

提高组复赛《火柴棒等式》 NOIP2008 提高组复赛《火柴棒等式》题解程序作者[fanld] 发表于[2008-11-22 0:07:00] 本题看题后感觉无法上手,但是仔细分析后便...


noip2015提高组复赛试题答案

noip2015提高组复赛试题答案_IT认证_资格考试/认证_教育专区。noip2015 提高组复赛试题答案一. 单项选择题 (共 20 题,每题 1.5 分,共计 30 分;每题有且仅...


历届noip提高组复赛试题

NOI’95 “同创杯”全国青少年信息学(计算机)奥林匹克竞赛 分区联赛复赛试题(...(NOIP2008)复赛 提高组一、题目概览中文题目名称 英文题目名称 可执行文件名 ...


NOIP2008普及组复赛试题与解题报告

NOIP2008普及组复赛试题与解题报告_学科竞赛_初中教育_教育专区 暂无评价|0人阅读|0次下载|举报文档NOIP2008普及组复赛试题与解题报告_学科竞赛_初中教育_教育专区。...


NOIP2008提高组初赛试题_C++含答案 改动

NOIP2008提高组初赛试题_C++含答案 改动_学科竞赛_高中教育_教育专区。第十四届...NOIP2008提高组复赛模拟... 13页 免费 NOIP2008初赛普及组试题... 暂无评价...


NOIP2008提高组前三题解题报告

NOIP2008 提高组复赛 解题思路 1、字符串中统计字母出现次数 最大减最小的 ...口腔执业医师实践技能复习资料 中医护理学基础重点 执业医师实践技能考试模拟试题©...


NOIP2008_复赛试卷_提高组

NOIP2008提高组复赛 4页 1下载券N​O​I​P​2​0​0​8​_...N​O​I​P​2​0​0​8​年​的​复​赛​题今日...

网站首页 | 网站地图
All rights reserved Powered by 学霸学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com