这是第二次模拟测试的解题报告
本次题目出自OIBH模拟赛
题目如下:
===================================================================================================================
饮食问题
(eatpuz.pas/c/cpp/in/out)
时限:1 sec | 内存: 64 MB
背景
平平正在减肥,所以要控制他的饮食。并且要求她及时去公园里面散步。
题目描述
平平正在减肥,所以她规定每天不能吃超过 C (10 <= C <= 35,000)卡路里的食物。农民 John 在戏弄她,在她面前放了B (1 <= B <= 21) 捅食物。每桶内都有某个单位卡路里(范围:1..35,000)的食物(不一定相同)。平平没有自控能力,一旦她开始吃一个桶中的食物,她就一定把这桶食物全部吃完。
平平对于组合数学不大在行。请确定一个最优组合,使得可以得到最多的卡路里,并且总量不超过C。
例如,总量上限是40卡路里, 6 桶食物分别含有7, 13, 17, 19, 29, 和 31卡路里的食物。平平可以吃7 + 31 = 38卡路里,但是可以获取得更多: 7 + 13 + 19 = 39卡路里。没有更好的组合了。
输入
共两行。
第一行,两个用空格分开的整数: C 和 B
第二行,B个用空格分开的整数,分别表示每桶中食物所含的卡路里。
输出
共一行,一个整数,表示平平能获得的最大卡路里,使她不违反减肥的规则。
输入样例
40 6
7 13 17 19 29 31
[样例输出]
39
三个袋子
(bags.pas/c/cpp/in/out)
时限:1 sec | 内存: 64 MB
背景
平平在公园里游玩时捡到了很多小球,而且每个球都不一样。平平找遍了全身只发现了3个一模一样的袋子。他打算把这些小球都装进袋子里(袋子可以为空)。他想知道他总共有多少种放法。
题目描述
将N个不同的球放到3个相同的袋子里,求放球的方案总数M。
结果可能很大,我们仅要求输出M mod K的结果。
现在,平平已经统计出了N<=10的所有情况。见下表:
N 1 2 3 4 5 6 7 8 9 10
M 1 2 5 14 41 122 365 1094 3281 9842
输入
两个整数N,K,N表示球的个数。
输出
输出仅包括一行,一个整数M mod K 。
输入样例 ( bags.in )
11 10000
输出样例( bags.out )
9525
数据规模
对于 40%数据,10<=N<=10,000
对于100%数据,10<=N<=1,000,000,000
对于 100%数据,K<=100,000
智捅马蜂窝
(clever.pas/c/cpp/in/out)
时限:1 sec | 内存: 64 MB
背景
为了统计小球的方案数,平平已经累坏了。于是,他摘掉了他那800度的眼镜,躺在树下休息。
后来,平平发现树上有一个特别不一样的水果,又累又饿的平平打算去把它摘下来。
题目描述
现在,将大树以一个N个节点的无向图的形式给出,每个节点用坐标(Xi,Yi)来表示表示,平平要从第一个点爬到第N个点,除了从一个节点爬向另一个相邻的节点以外,他还有一种移动方法,就是从一个节点跳下,到达正下方的某个节点(之间可隔着若干个点和边),即当Xj=Xi and Yi<Yj 时,平平就可以从j节点下落到i节点,他下落所用时间满足自由落体公式,t=sqrt((Yj-Yi)*2/g) (注意:g取10)。如果出现两线相交的情况,我们不认为它们是相通的。
输入
两个整数N,V,N表示节点个数,V表示平平爬树的速度。
接下来N行,每行包含3个整数X,Y,F,X,Y是这个点的坐标,F是他的父节点(F一定小于这个点的标号,第一行的F为0)。
注意:两节点间距离按欧几里德距离计算 dis = sqrt( ( x1 – x2 ) 2+ ( y1 – y2 )2 )
输出
输出仅包括一行,从1到N所用的最少所需时间T,保留两位小数。
输入样例 ( clever.in )
9 1
5 0 0
5 5 1
6 5 2
7 6 2
6 9 2
3 6 2
4 5 2
3 2 7
7 2 3
输出样例 ( clever.out )
8.13
数据规模
对于100%数据,1<=N<=100,1<=V<=10,0<=X,Y<=100.
建议使用extended(pas)或double(c and c++)计算,我们对于精度造成的误差将不予重测。
过河
(river.pas/c/cpp/in/out)
时限:1 sec | 内存: 64 MB
背景
经过一番努力,平平终于摘到了水果,拿近一看才发现是马蜂窝。
平平从树上掉了下来,没命的跑啊跑啊……
后来,他发现前方有一条河。现在他用电话求助于你,希望你在他跑到之前铺好过河的路,让他顺利过河。
题目描述
已知河的长度为L,现在我们有M个石子,我们可以把一个石子铺在河上的一个点,让平平踩着这些石头过河。河上已经有N个石子,而且已知平平每步跨出的距离为S到T之间的整数( S <= T ),起点是0点,河为1到L,只要平平最后能跳过L(必须大于L)就算平平顺利过河。
如果平平能够过河,请输出最少步数,否则输出最远到达的距离,以便我们及时去救起平平。
输入
第一行有五个整数L,N,M,S,T ,L是河的宽度,N表示河里原来就有N个石头,M表示我们手上拥有的石头,S,T表示平平的一步最小的跨度和最大跨度。接下来N行有一个值表示在河里的石头的位置(从小到大给出)。
输出
输出仅包括一行,如果能够过河,输出最少步数,否则输出平平能够到达的最远距离。
输入样例 ( river.in )
样例1:
8 2 2 2 3
2
3
样例2:
10 1 1 1 2
2
输出样例 ( river.out )
样例1:
3
样例2:
4
数据规模
对于40%数据,1<=M<=L<=1000 , 1<=S<=T<=10 ;
对于100%数据,1<=M<=L<=100000;
对于100%数据,1<=S<=T<=100,1<=N<=100.
后记
可怜的平平还是没有逃过被马蜂蛰的命运。大老板以最快的速度把平平送到了医院。
平平的故事就此告一段落。现在平平小朋友正躺在家里好好休息,准备冲刺2007年的NOIP……
================================================================================================================
解题报告:
第一题:
简单的01背包,就算使用回溯法枚举所有可能情况也能过(经测试),数据很弱。。。。。。。
本人用DP方法,求出了所有可能得到的卡路里值
附上程序:
#include "stdio.h"
#include "stdlib.h"
#define N 25
int b[N];
int d[N];
int l,n;
int ans;
![](/Images/OutliningIndicators/None.gif)
void input()
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
int i;
scanf("%d%d",&l,&n);
for(i=0;i<n;i++)
scanf("%d",&d[i]);
}
![](/Images/OutliningIndicators/None.gif)
int add(void)
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
int i,f=0;
for(i=0;i<n;i++)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if(b[i])
f+=d[i];
}
return f;
}
![](/Images/OutliningIndicators/None.gif)
int work()
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
int i,j;
int sum;
i=0;
b[0]=-1;
ans=0;
while(i>=0)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if(i==n)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
sum=add();
if(sum>ans&&sum<=l)
ans=sum;
i--;
continue;
}
b[i]++;
if(b[i]>1)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
i--;
continue;
}
b[i+1]=-1;
i++;
}
return ans;
}
![](/Images/OutliningIndicators/None.gif)
int main()
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
freopen("eatpuz.in","r",stdin);
freopen("eatpuz.out","w",stdout);
input();
printf("%d\n",work());
return 0;
}
![](/Images/OutliningIndicators/None.gif)
第二题:
无奈的数学题,快速幂,或者干脆用矩阵乘法加速,看着办吧
第三题:
简单的单元最短路,注意如果可能掉下来而不用爬的方法,更新两点间的通路时间,其他没什么了。
Dijkstra算法,代码:
#include "stdio.h"
#include "stdlib.h"
#include "math.h"
#define N 128
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
double g[N][N]=
{0},v;
int x[N],y[N];
int n;
![](/Images/OutliningIndicators/None.gif)
void input(void)
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
int i,j;
int a,b,f;
int af,bf;
double dis;
scanf("%d%lf",&n,&v);
for(i=1;i<=n;i++)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
for(j=1;j<=n;j++)
g[i][j]=32768;
}
for(i=1;i<=n;i++)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
scanf("%d%d%d",&a,&b,&f);
x[i]=a; y[i]=b;
if(f==0)
continue;
af=x[f]; bf=y[f];
dis=sqrt(1.0*(a-af)*(a-af)+(b-bf)*(b-bf));
g[i][f]=g[f][i]=dis/v;
}
for(i=1;i<=n;i++)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
for(j=1;j<=n;j++)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if(x[i]==x[j]&&y[i]<y[j])
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
dis=sqrt(1.0*(y[j]-y[i])*2/10.0);
if(dis<g[j][i])
g[j][i]=dis;
}
}
}
}
![](/Images/OutliningIndicators/None.gif)
int work(void)
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
int i,j,k;
int min;
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
int b[N]=
{0};
double len[N];
for(i=1;i<=n;i++)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
len[i]=g[1][i];
}
len[0]=32768;
len[1]=0;
b[1]=1;
for(k=1;k<=n;k++)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
min=0;
for(i=1;i<=n;i++)
if(b[i]==0&&len[i]<len[min])
min=i;
if(min==0)
break;
b[min]=1;
for(i=1;i<=n;i++)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if(b[i]==0&&len[min]+g[min][i]<len[i])
len[i]=len[min]+g[min][i];
}
}
printf("%.2lf\n",len[n]);
}
![](/Images/OutliningIndicators/None.gif)
int main()
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
freopen("clever.in","r",stdin);
freopen("clever.out","w",stdout);
input();
work();
//getch();
return 0;
}
![](/Images/OutliningIndicators/None.gif)
第四题:
让人崩溃的DP题目,不过由于数据比较弱,搜索应该也是可以过的(不过本人不会)。
首先我们应该明确题目中的几个重要部分(或者说是细节步骤,要不然就是过河时的一般规律):
1、如果可能到达河岸对面,那么,手中的石头全部使用完肯定对应至少一个最优解(为什么?自己想,简单的很);
2、对于两个石头之间,是否存在可能到达方式的判断条件:len/s*t>=len(len为两石头间的距离,下同) (具体证明,可以形象的画一画);
3、如果两个点(或者说石头),如果之间有可能的方法到达(即满足2中的判断条件),那么,从一个石头到达另一个石头所需要踩过的其他石头(即非这两个石头)的数目为 (len-1)/t,并且可以保证一定有这样子的一种到达方法。
接下来,就应该介绍动态转移方程,以及相关的预处理了。
对于数据,我们首先要进行一些必要的预处理:
1、对于读入的每个石头的位置,通过对于上述条件的判断,如果从0点不可到达,则可以将次石头略去不考虑;
2、因为题目要求一定要过河(就是行动的总距离要大于L才行),所以就在 L+1~L+S 这S个位置上人为的构造出S个石头,并认为这些石头是本身存在与河面上的。
3、对于上面提到的每一个石头,应该对其预处理出一个值(我将其保存在B数组中),代表从0点到达这个石头中间要踩过多少个石头(这里踩过的石头可以是已有的,可以是从手中放下的,石头数允许是不合法的。注意:这个数组只是表示这一种可能情况,不表示一定满足输入数据);
4、动态规划的初始状态 F[i][0]=b[i]+1。
接下来,介绍动态规划中状态的表示方法:
F[i][j]表示从0点到第i个石头,中间如果踩过j个石头,所需要的最少步数。(注意:此处是踩过,如果只是经过某个石头而不必踩过,则这个石头就不包含在这j个石头中)。
动态转移方程:
F[j][k+ifneed(i)]=min{F[i][k]+w[i][j]+1} (0<=k<i),其中w[i][j]表示从第i个石头到第j个石头中间要踩过的石头数,ifneed表示一种判断条件,就是用来判断如果到达第j个石头,是否一定要踩到第i个石头上面,如果必要,则返回1,否则返回0。具体的判断方法实现如下:
d=(rock[j]-rock[i]-1)/t; //rock中存放的为第i个石头的位置
need=b[j]-b[i]-d; 最后就是对结果的判断了。
第一项,应该是判断是否存在能够过河的方法。由于可以明显的看出,在上述动态规划的过程中,由于判断了中转石头是否必要踩过,已经形成了一定的贪心规则。所以,在输出时,就应该对最后s个石头(就是自己加进去的石头判断),如果b[i]满足条件,就取其中最小的;如果b[i]>m,就取F[i][b[i]-m]里最小的。(原因应该很简单,因为上面在转移和预处理时已经保证了得到最优)
第二项,就是在第一项没有找到过河步数是,求出最远走到哪里了。这里就更为简单了:1、最近可以走m*t的距离;2、如果F[i][j]可行(就是不为0),并且满足m+j>=b[i],就判断rock[i]+(m+j-b[i])*t 是否为可行解即可。
再来分析一下时间复杂度,由于石头数不大于100,s也不大于10,对于上述O(N^3)的算法是绝对不会超时的。这样,这道题就完美解决了。
附上代码:
#include "stdio.h"
#include "stdlib.h"
#define N 210
![](/Images/OutliningIndicators/None.gif)
int rock[N];
int b[N];
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
int f[N][N]=
{0};
int l,n,m,s,t;
![](/Images/OutliningIndicators/None.gif)
void input()
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
int i;
int cnt;
scanf("%d%d%d%d%d",&l,&n,&m,&s,&t);
cnt=1;
for(i=1;i<=n;i++)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
scanf("%d",&rock[cnt]);
if(rock[cnt]/s*t>=rock[cnt])
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
b[cnt]=(rock[cnt]-1)/t;
f[cnt][0]=b[cnt]+1;
cnt++;
}
}
for(i=1;i<=s;i++)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
rock[cnt]=l+i;
b[cnt]=(rock[cnt]-1)/t;
f[cnt][0]=b[cnt]+1;
cnt++;
}
n=cnt-1;
}
![](/Images/OutliningIndicators/None.gif)
int work(void)
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
int ans;
int i,j,k;
int d,need;
for(i=1;i<=n;i++)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
for(j=1;j<=n;j++)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if( ((rock[j]-rock[i])/s*t) >= (rock[j]-rock[i]) )
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
d=(rock[j]-rock[i]-1)/t;
need=b[j]-b[i]-d;
for(k=0;k<i;k++)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if(f[i][k])
if(f[j][k+need]==0||f[j][k+need]>f[i][k]+d+1)
f[j][k+need]=f[i][k]+d+1;
}
}
}
}
ans=2147483647;
for(i=n-s+1;i<=n;i++)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if(b[i]<=m&&ans>f[i][0])
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
ans=f[i][0];
}
else if( (n-1>b[i]-m) && (f[i][b[i]-m]>0) && (ans>f[i][b[i]-m]) )
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
ans=f[i][b[i]-m];
}
}
if(ans==2147483647)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
ans=m*t;
for(i=1;i<=n;i++)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
for(j=0;j<i;j++)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if(f[i][j]&&m+j>=b[i])
if(rock[i]+(m+j-b[i])*t>ans)
ans=rock[i]+(m+j-b[i])*t;
}
}
}
return ans;
}
![](/Images/OutliningIndicators/None.gif)
int main()
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
freopen("river.in","r",stdin);
freopen("river.out","w",stdout);
input();
printf("%d\n",work());
return 0;
}
![](/Images/OutliningIndicators/None.gif)