9.19模拟考试解题报告

题目:noip2015模拟试题

一、购物

这道题真心弱 三行代码就完事了

不过考试的时候看着旁边的人写了一堆函数十几行最后还错了。。呵呵

思路:取能够得到下一面值的最大面值硬币

因为硬币最多10种 从大到小枚举即可

然后再将能取到的最大面值+取得硬币的面值

考试的时候被坑了一下 输入数据不一定有序。。然后掉了50分 加上一句排序满分

代码:

// <shopping.cpp> – 09/20/15 08:14:11
// This file is created by XuYike’s black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don’t know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
int ans,m=0;
int main()
{
freopen(“shopping.in”,”r”,stdin);
freopen(“shopping.out”,”w”,stdout);
int x,n,d[10];
cin>>x>>n;
for(int i=0;i<n;i++)cin>>d[i];
sort(d,d+n);
while(m<x)
for(int k=n-1;k>=0;k–)
if(d[k]<=m+1){m+=d[k];ans++;break;}
if(ans)cout<<ans;
else cout<<-1;
return 0;
}

 

二、养猪

考试的时候深搜得了10分。。

主要是这道题体重减到0为止 不好弄

正解:先将猪按p[i]从大到小排序 再动归

转移方程:dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]+max(0,pi[i].a-pi[i].p*(j-1)))

dp[i][j]指i头猪中选j头 dp[i-1][p]为不选当前猪 另一个为选择

代码:

// <pig.cpp> – 09/20/15 08:14:11
// This file is created by XuYike’s black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don’t know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
struct pig
{
int a,p;
}pi[1001];
bool cmp(pig a,pig b)
{
return a.p>b.p;
}
int dp[1001][1001];
int main()
{
freopen(“pig.in”,”r”,stdin);
freopen(“pig.out”,”w”,stdout);
int n,k,ans=0;
cin>>n>>k;
if(k>n)k=n;
for(int i=1;i<=n;i++)cin>>pi[i].a;
for(int i=1;i<=n;i++)cin>>pi[i].p;
sort(pi+1,pi+1+n,cmp);
for(int i=1;i<=n;i++)
for(int j=1;j<=min(i,k);j++){
dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]+max(0,pi[i].a-pi[i].p*(j-1)));
if(dp[i][j]>ans)ans=dp[i][j];
}
cout<<ans;
return 0;
}

 

三、数位平方和

还没做XD

 

四、扩散

这个应该算第二简单的了

不过考完答案给错了 郁闷了好久

思路:两两求出连通所需时间:(两边长相加+1)/2

然后将时间从小到大排序

然后开并查集

每选取一个加入并查集 判断是否全部连通 是则输出当前连通所需时间

代码:

// <ppg.cpp> – 09/20/15 08:14:11
// This file is created by XuYike’s black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don’t know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
long long l[51][51];
long long father[51];
int k,n;

struct point
{long long x,y;}p[51];

struct juli
{long long a,b,dis;}jl[1500];

long long abss(long long a)
{return a>=0?a:-a;}

long long getfather(long long x)
{
if(father[x]!=x)father[x]=getfather(father[x]);
return father[x];
}

bool cmpj(juli a,juli b)
{return a.dis<b.dis;}

bool panduan()
{
for(int i=1;i<n;i++)if(getfather(i)!=getfather(0))return 0;
return 1;
}

int main()
{
freopen(“ppg.in”,”r”,stdin);
freopen(“ppg.out”,”w”,stdout);
cin>>n;
for(int i=0;i<n;i++)cin>>p[i].x>>p[i].y;
for(int i=0;i<n;i++)father[i]=i;
for(int i=0;i<n;i++)
for(int j=i+1;j<n;j++){
jl[k].a=i;
jl[k].b=j;
jl[k++].dis=(abss(p[i].x-p[j].x)+abss(p[i].y-p[j].y)+1)>>1;
}
sort(jl,jl+k,cmpj);
for(int i=0;i<k;i++){
father[getfather(jl[i].a)]=getfather(jl[i].b);
if(panduan()){cout<<jl[i].dis;return 0;}
}
return 0;
}

 

今天的题目还算比较水的 不是第一题被坑的话能混进前五XD

说点什么

您将是第一位评论人!

提醒
wpDiscuz