NOIP2018 提高组复赛 Day1 试题及详细答案

NOIP2018提高组复赛Day1试题及详细答案考试时长：3小时满分：300分（每题100分）适用语言：C/C++T1标题：铺设道路【题目描述】春春是一名道路工程师，负责铺设一条长度为n的道路。道路可以看作是n块连续的地砖，初始时所有地砖高度均为0。我们需要通过施工，让每块地砖i的高度变为给定的高度a[i]。每次施工可以选择一段连续的地砖，将这段地砖的高度全部增加1。求最少需要多少次施工，可以完成道路铺设。【输入格式】第一行一个整数n，表示道路地砖数量。第二行n个整数，第i个数表示第i块地砖的目标高度a[i]。【输出格式】输出一个整数，表示最少施工次数。【数据范围】对于30%数据：n≤10对于60%数据：n≤1000对于100%数据：1≤n≤100000，0≤a[i]≤10000【样例输入】PlainText

5

12321【样例输出】PlainText

3【题目思路】本题为经典贪心题。核心规律：相邻两个位置，若后一个高度大于前一个，二者的高度差即为新增的施工次数；若小于等于，则无需额外施工。原理：每一段上升的高度差，都需要单独的区间操作覆盖，平稳或下降的部分可以复用之前的施工区间。最终答案为第一个位置的高度，加上所有后项大于前项的高度差之和。【详细解析】样例数据：1、2、3、2、1初始答案ans=a[1]=1a[2]-a[1]=1>0，ans+=1→ans=2a[3]-a[2]=1>0，ans+=1→ans=3a[4]-a[3]=-1、a[5]-a[4]=-1，无累加最终结果为3，与样例一致。【完整代码】PlainText

#include<cstdio>

usingnamespacestd;

constintMAXN=100010;

intn,a[MAXN];

longlongans;

intmain()

{

scanf("%d",&n);

for(inti=1;i<=n;++i)

scanf("%d",&a[i]);

ans=a[1];

for(inti=2;i<=n;++i)

if(a[i]>a[i-1])

ans+=a[i]-a[i-1];

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

return0;

}【评分要点】1.暴力模拟区间操作（30分）：小数据可过，大数据超时2.O(n)贪心算法（100分）：线性遍历，无超时，逻辑正确即可满分T2标题：货币系统【题目描述】给定一个n种面额的货币系统，面额分别为a[1],a[2]…a[n]，保证所有面额为正整数。若一个货币系统可以组合出的所有金额，与原系统完全相同，则称两个货币系统等价。求与原系统等价的、面额数量最少的货币系统，输出最少的面额数量。【输入格式】第一行一个整数T，表示数据组数。每组数据第一行一个整数n，表示原货币面额数量。第二行n个正整数，表示各货币面额。【输出格式】每组数据输出一行一个整数，表示最简等价货币系统的面额数。【数据范围】对于100%数据：T≤20，n≤100，面额大小≤25000【样例输入】PlainText

2

4

319106

5

1129131917【样例输出】PlainText

2

5【题目思路】核心结论：原系统中，能被其他更小面额组合出来的面额是多余的，可以删除；保留无法被组合的面额，即为最优解。解题方法：完全背包可行性DP。设dp[x]表示金额x是否可以被组合出来，从小到大遍历所有面额，若当前面额无法被更小面额组合，则保留该面额，并用其更新背包数组。【详细解析】第一组样例：3、19、10、6排序后：3、6、10、193无法被组合，保留；6可由3+3组合，舍弃；10无法被3组合，保留；19可由3+10+6组合，舍弃。最终保留2个，答案为2。第二组所有面额均无法互相组合，因此全部保留，答案为5。【完整代码】PlainText

#include<cstdio>

#include<cstring>

#include<algorithm>

usingnamespacestd;

booldp[25010];

inta[110];

intT,n;

intmain()

{

scanf("%d",&T);

while(T--)

{

memset(dp,0,sizeof(dp));

scanf("%d",&n);

for(inti=1;i<=n;++i)

scanf("%d",&a[i]);

sort(a+1,a+1+n);

intmaxx=a[n],ans=0;

dp[0]=1;

for(inti=1;i<=n;++i)

{

if(!dp[a[i]])

{

ans++;

for(intj=a[i];j<=maxx;++j)

dp[j]|=dp[j-a[i]];

}

}

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

}

return0;

}【评分要点】1.未排序直接判断（40分）：逻辑漏洞，会误判可替换面额2.朴素完全背包（100分）：复杂度合理，覆盖全部数据T3标题：赛道修建【题目描述】C城将要举办一系列的赛车比赛。比赛场地是一棵树，共有n个节点，节点间的边为赛道，每条边有对应的长度。我们需要在树上选出m条互不重叠的简单路径（无公共边），使得这m条路径的最短长度尽可能大。求这个最大的最小长度。【输入格式】第一行两个整数n,m，表示节点数和需要选出的路径数。接下来n-1行，每行三个整数u,v,w，表示u、v之间有一条长度为w的边。【输出格式】输出一个整数，表示最大的最小赛道长度。【数据范围】对于30%数据：n≤20对于60%数据：n≤1000对于100%数据：1≤m<n≤50000，1≤w≤10000【样例输入】PlainText

52

122

232

342

452【样例输出】PlainText

2【题目思路】本题为经典二分答案+树形DP。1.二分答案：枚举可能的最小长度mid，判断能否选出至少m条不重叠、长度≥mid的路径；2.树形check：遍历整棵树，统计满足条件的路径数量。对于每个节点，收集所有子树延伸上来的合法链长，两两拼接成合法路径，剩余最长链向上传递给父节点，保证路径不重叠。【详细解析】样例为一条长度为8的链，需要选2条赛道。最优方案是选取两段长度为2的赛道，因此答案为2。二分边界：左边界1，右边界总路径长度。每次取mid，通过树形遍历统计合法赛道数量：数量≥m则说明答案可行，尝试更大值；否则尝试更小值。【完整代码】PlainText

#include<cstdio>

#include<vector>

#include<algorithm>

usingnamespacestd;

constintMAXN=50010;

vector<pair<int,int>>e[MAXN];

intn,m,cnt;

intdfs(intu,intfa,intlim)

{

vector<int>tmp;

for(autop:e[u])

{

intv=p.first,w=p.second;

if(v==fa)continue;

intres=dfs(v,u,lim)+w;

if(res>=lim)cnt++;

elsetmp.push_back(res);

}

sort(tmp.begin(),tmp.end());

intl=0,r=tmp.size()-1;

intmaxlen=0;

while(l<r)

{

if(tmp[l]+tmp[r]>=lim)

{

cnt++;

r--;

l++;

}

elsel++;

}

if(l==r)maxlen=tmp[l];

returnmaxlen;

}

boolcheck(intmid)

{

cnt=0;

dfs(1,0,mid);

returncnt>=m;

}

intmain()

{

scanf("%d%d",&n,&m);

intl=1,r=0,ans=0;

for(inti=1;i<n;++i)

{

intu,v,w;

scanf("%d%d%d",&u,&v,&w);

e[u].emplace_back(v,w);

e[v].emplace_back(u,w);

r+=w;

}

while(l<=r)

{

intmid=(l+r)>>1;

if(check(mid))

{

ans=mid;

l=mid+1;

}

elser=mid-1;

}

pri