NOIP2015模拟赛(三) 试题及详解

时间:2022-12-17 12:34:22

模拟赛

问题

文件名

输入

输出

内存限制

时限

分值

海宝玩具

haibao.pas/dpr/c/cpp

haibao.in

haibao .out

256M

2s

100

半数集问题

set.pas/c/cpp

set.in

set.out

256M

1s

100

陈老师搬书

book.pas/c/cpp

book.in

book.out

256M

1s

100

 

 

 

 

 

 

一、海宝玩具

【问题描述】

举世瞩目的上海世博会开幕了,XX同学和他的宠物天天好不容易得到了一次游览世博园的机会,他们两个正沿着园区小路去XX最感兴趣的天文馆参观,突然发现面前出现了一块告示牌:“你能得到多少海宝?试一试!”。


天天很感兴趣,因为海宝是世博会的吉祥物啊!在告示牌背后,一个个包装精美的盒子整齐地排列成矩形网格(如图1)。每个盒子上面都有一个数字牌,代表盒子里海宝玩具的数目。天天非常想得到这些海宝,但是XX想尽快去参观天文馆,怎么办呢?XX说:“你先找出海宝玩具数目最多的盒子,去拿出它里面的海宝玩具;然后再找出剩下的盒子里海宝玩具最多的,去拿出它;依此类推,不过你一定要在我限定的时间内回到路边。”

NOIP2015模拟赛(三) 试题及详解

我们假定天天在每个单位时间内,可以做下列四件事情中的一件:

从路边跳到最靠近路边(即第一行)的某个礼物盒子;

从一个盒子跳到前后左右与之相邻的另一个盒子;

拿出盒子里的所有海宝玩具;

从最靠近路边(即第一行)的某个盒子跳回路边。

现在给定一块网格大小和礼物盒子的分布,请问在限定时间内,天天最多可以拿到多少个海宝玩具?注意可能只有部分盒子里有海宝玩具,假设这些盒子里海宝玩具个数各不相同。

例如在图2所示的网格里,只有位于(2, 5), (3, 7), (4, 2), (5, 4)的盒子里有海宝玩具,个数分别为13, 7, 15, 9。沿着图示的路线,天天在21个单位时间内,最多可以拿到37个海宝玩具。

【输入】

输入文件haibao.in的第一行包括三个整数,M, N和K,用空格隔开;表示网格大小为M * N(1 <= M, N <= 20),天天拿礼物的限定时间为K(0 <= K <= 1000)个单位时间。接下来的M行,每行包括N个非负整数,也用空格隔开;第i + 1行的第j个整数Pij(0 <= Pij <= 500)表示盒子(i, j)里海宝玩具的数目,0表示该盒子里没有海宝。

【输出】

输出文件haibao.out包括一行,这一行只包含一个整数,即在限定时间内,天天最多可以拿到海宝玩具的个数。

【样例输入1】

6 7 21

0 0 0 0 0 0 0

0 0 0 0 13 0 0

0 0 0 0 0 0 7

0 15 0 0 0 0 0

0 0 0 9 0 0 0

0 0 0 0 0 0 0

【样例输出1】

37

【样例输入2】

6 7 20

0 0 0 0 0 0 0

0 0 0 0 13 0 0

0 0 0 0 0 0 7

0 15 0 0 0 0 0

0 0 0 9 0 0 0

0 0 0 0 0 0 0

【样例输出2】

28

二、半数单集问题

【问题描述】

给定一个自然数n,由n开始可以依次产生半数集set(n)中的数如下。n∈set(n);在n的左边加上一个自然数,但该自然数不能超过最近添加的数的一半;按此规则进行处理,直到不能再添加自然数为止。

例如,set(6)={6,16,26,126,36,136}。半数集set(6)中有6个元素。

注意半数集不是多重集。集合中已经有的元素不再添加到集合中。

对于给定的自然数n,编程计算半数集set(n)中的元素个数。

【输入】

输入文件只有1行,给出整数n。(0<n<201)

【输出】

输出文件只有1行,给出半数集set(n)中的元素个数。

【样例】

输入文件示例

输出文件示例

set.in

set.out

6

6

 

三、陈老师搬书

【问题描述】

陈老师喜欢网购书籍,经常一次购它个百八十本,然后拿来倒卖,谋取暴利.前些天,高一的新同学来了,他便像往常一样,兜售他的书,经过一番口舌,同学们决定买他的书,但是CS桌上的书有三堆,每一堆都有厚厚的一叠,他要想个办法用最轻松的方式把书拿下来给同学们.但是你想逗一下CS于是,请你设计一个最累的方式给他.

若告诉你这三堆分别有i,j,k本书,以及每堆从下到上书的重量.每次取书只能从任意一堆的最上面取,那么请你帮助他设计一个方案,让他花最大的力气取下所有书(CS别打我).

显然,每次取书,陈老师的体力消耗都会加大,这里用体力系数代表,取下第一本书时,体力系数为1,第二本时为2,依次类推,而每次体力消耗值则为体力系数和书的重量之积

举个例子:

三堆书及重量如下NOIP2015模拟赛(三) 试题及详解

 

 

 

 

 

不用证明,最累的取书方式为: 右左左中, 即: 3*1+9*2+2*3+10*4=3+18+6+40=67

【输入文件】(book.in)

 输入文件的第一行为3个数,分别为三堆数量I,j,k

 第二行至第四行分别为每堆由下至上的书本重量

 

【输出文件】(book.out)

 输出最累方式的体力消耗总值即可

 

【输入样例】  

3 2 4

2 3 2

1 5

9 8 7 4

【输出样例】

257

【注释】

输入数据为每堆由下至上的书本重量!

【数据规模】

对于40%的数据有:

0<=i<10   0<=j<10   0<=k<10

对于100%的数据有:

0<=i<100   0<=j<100   0<=k<100

最后输出的体力消耗总值在long范围内

解析:

【算法分析】

乍一看此题,就会发现,穷举、搜索的方法对此题都不适用,因为题目中已明确给出了摘豆子的规则。其实,我们只需要根据题目给出的规则,编程序模拟摘豆子的过程就可以了。首先,定义一个整型的二维数组a存储每个格子中的豆子数目,然后进行摘豆子。

设置一个二层循环求出含有最多豆子的格子的坐标,由数学知识可知,从(x1,y1)到(x2,y2)需要的单位时间为|x1-x2|+|y1-y2|,因此由当前位置(x,y)跳到含有最多豆子的格子(x1,y1)内摘下豆子并回到路边所需的时间为step=|x-x1|+|y-y1|+1+x1,接下来判断step与剩余的时间p的大小关系。若step<=p则说明有足够的时间去摘豆子,则去摘:具体步骤(剩余时间p:=p-|x-x1|+|y-y1|-1;当前点的坐标跳入(x1,y1);摘下的总豆子数sum:=sum+a[x,y],a[x,y]:=0;表示此格子内的豆子已被摘没);若step>p,说明没有足够多的时间跳过去摘下豆子再回到路边,因此只能回到路边而不能去摘豆子了。

   重复此摘法即可得出最后结果。

【数据结构】

var a:array[0..20,0..20]of integer;           {存每个格子内的豆子数}

【程序清单】

program peanuts;

var a:array[0..20,0..20]of integer;                   {存每个格子内的豆子数}

    m,n,k,step,i,j,x,y,x1,y1,sum:integer;

    f1,f2:text;

    yes:boolean;                                      {存是否有豆子可摘}

begin

 assign(f1,'peanuts.in');reset(f1);           {输入文件名"peanuts.in"}

 assign(f2,'peanuts.out');rewrite(f2);        {输出文件名"peanuts.out"}

 readln(f1,m,n,k);

 for i:=1 to m do

  begin

   for j:=1 to n do read(f1,a[i,j]);readln(f1)

  end;                                                                           {读入数据}

 x:=0;y:=0;yes:=true;sum:=0;                {初始化,x,y存当前结点坐标}

 repeat

  x1:=0;y1:=0;

  for i:=1 to m do

    for j:=1 to n do            

     if a[i,j]>a[x1,y1] then begin x1:=i;y1:=j end; {求出含有最多豆子数的格子坐标}

  if y=0 then y:=y1;

  step:=abs(x-x1)+abs(y-y1)+x1+1;  {求出从原点到含豆子数最多点内摘豆子并回到路边所需单位时间}

  if (k<step)or(a[x1,y1]=0)then yes:=false;              {判断豆子是否可摘}

  if yes then

   begin

    sum:=sum+a[x1,y1];

    k:=k-abs(x-x1)-abs(y-y1)-1;

    x:=x1;y:=y1;a[x,y]:=0;

   end;                                                                           {摘豆子}

 until yes=false;

 writeln(f2,sum);

 close(f1);close(f2)

end.

二、半数集

1、半数集

递归过程分析

通过分析所描述问题的特点可知,半数集set(n)中元素个数的求解是个递归的过程。设set(n)中的元素个数为f(n),则显然有递归表达式:

f(n)=1+∑f(i),i=1,2……n/2

据此,可很容易设计出求f(n)的递归算法如下:

int comp(int n)     

{     int ans=1;

       if(n>1)

              for(int i=1;i<=n/2;i++)

                     ans+=comp(i);

       return ans;

}

对于此递归过程,是存在有缺陷的,即有很多的重复子问题计算。比如说:当n=4时,f(4)=1+f(1)+f(2),而f(2)=1+f(1),因此,在计算f(2)的时候又要重复计算一次f(1)。更进一步,当n较大时,类似的重复子问题计算将会变得非常多。

改进的递归算法

可以对如上的递归算法进行改进,用数组来存储已计算过的子问题结果,就可以避免重复,提高算法效率。改进的递归算法如下:

int comp(int n)

{     int ans=1;

       if(a[n]>0)              //避免重复计算的判断语句(在主函数中将数组a的元素全部初始化为0)

              return a[n];

       for(int i=1;i<=n/2;i++)

              ans+=comp(i);

       a[n]=ans;

       return ans;

}

半数单集问题

概念说明

半数单集类似半数集,区别在于:半数集是多重集,而半数单集不是多重集,即集合中已有的元素不再添加到集合中。

例如:n=24,那么半数集set(24)中的元素1224就有如下两种方式可以生成:

24 → 1224

24 →224 → 1224

所以,1224就是一个被重复计算的元素。

如何剔除重复元素

笔者只考虑了n≤200的情况。

在n≤200时,n/2≤100,也就是说,此时可能产生重复的元素是2位数。一个两位数x产生重复的条件是:其个位上的数y=x的半数集中已产生x,即

x/10 ≤y/2 或 2(x/10) ≤x

例如n=24时,x=24/2=12,y=12=2即:2的半数集中已产生12。

因此,在三中的算法里加入剔除重复元素的语句即可实现重复元素的剔除。剔除重复元素的递归算法如下:

int comp(int n)

{     int ans=1;

       if(a[n]>0)

              return a[n];

       for(int i=1;i<=n/2;i++)

       {   

              ans+=comp(i);

              if((i>10)&&(2*(i/10)<=i))     //剔除重复元素的判断语句

                     ans-=a[i/10];          

       }

       a[n]=ans;

       return ans;

}

 

小结

       使用递归算法求解问题时,首先需要得出所求问题的递归方程,递归方程需要有一个初始值,这个初始值也称为边界条件。递归方程是自然数上的一个函数T(n),它使用一个或多个小于n时的值的不等式来描述。递归方程通常有三种方法可以计算:迭代方法,替换方法和主方法。

三、陈老师搬书

动规

f[i,j,k] 表示第一堆剩下i本,第二堆剩下j本,第三堆剩下K本的最大值。

三维,因为已知ijk,则知道是第几次搬运,不需要四维。

 

program book;

var

l1,l2,l3,i,j,k,temp:integer;

f:array[0..100,0..100,0..100] of longint;

a,b,c:array[1..100] of longint;

function max(a,b:longint):longint;

begin

 if a>b then exit(a) else exit(b);

end;

begin

 

 readln(l1,l2,l3); temp:=l1+l2+l3;

 for i:=1 to l1 do read(a[i]);readln;

 for i:=1 to l2 do read(b[i]);readln;

 for i:=1 to l3 do read(c[i]);readln;

 for i:=l1 downto 0 do

  for j:=l2 downto 0 do

   for k:=l3 downto 0 do

   begin

    if i+1<=l1 then f[i,j,k]:=max(f[i,j,k],f[i+1,j,k]+(temp-i-j-k)*a[i+1]);

    if j+1<=l2 then f[i,j,k]:=max(f[i,j,k],f[i,j+1,k]+(temp-i-j-k)*b[j+1]);

    if k+1<=l3 then f[i,j,k]:=max(f[i,j,k],f[i,j,k+1]+(temp-i-j-k)*c[k+1]);

   end;

  writeln(f[0,0,0]);

end.

 

记忆化搜索

 

#include <iostream> 

using namespace std; 

const int maxn=101; 

int i,j,k,n; 

int now,ans; 

int w[4][maxn]; 

void init() 

{int t; 

 freopen("book.in","r",stdin);  

freopen("book.out","w",stdout);  

scanf("%d %d %d",&i,&j,&k); 

 n=i+j+k;  

for (t=1;t<=i;t++)    

scanf("%d",&w[1][t]);  

for (t=1;t<=j;t++)    

scanf("%d",&w[2][t]);  

for (t=1;t<=k;t++)    

scanf("%d",&w[3][t]);  ans=0;   } 

void dfs(int a,int b,int c) 

{int x;  

if (a+b+c==0) 

       {if (now>ans)  ans=now;     return;    } 

 x=n-(a+b+c)+1;  

if (a>0) 

       {now+=w[1][a]*x;  dfs(a-1,b,c);  now-=w[1][a]*x;    }  

if (b>0) 

        {now+=w[2][b]*x;     dfs(a,b-1,c);     now-=w[2][b]*x;    }  

if (c>0) 

        {now+=w[3][c]*x;     dfs(a,b,c-1);     now-=w[3][c]*x;    } 

int main() 

{

init();  

dfs(i,j,k);  

printf("%d\n",ans);  

return 0; 

}