模拟赛
| 问题 |
文件名 |
输入 |
输出 |
内存限制 |
时限 |
分值 |
| 海宝玩具 |
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说：“你先找出海宝玩具数目最多的盒子，去拿出它里面的海宝玩具；然后再找出剩下的盒子里海宝玩具最多的，去拿出它；依此类推，不过你一定要在我限定的时间内回到路边。”
我们假定天天在每个单位时间内，可以做下列四件事情中的一件：
从路边跳到最靠近路边（即第一行）的某个礼物盒子；
从一个盒子跳到前后左右与之相邻的另一个盒子；
拿出盒子里的所有海宝玩具；
从最靠近路边（即第一行）的某个盒子跳回路边。
现在给定一块网格大小和礼物盒子的分布，请问在限定时间内，天天最多可以拿到多少个海宝玩具？注意可能只有部分盒子里有海宝玩具，假设这些盒子里海宝玩具个数各不相同。
例如在图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,依次类推,而每次体力消耗值则为体力系数和书的重量之积
举个例子:
三堆书及重量如下
不用证明,最累的取书方式为: 右左左中, 即: 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本的最大值。
三维，因为已知i，j，k，则知道是第几次搬运，不需要四维。
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;
}