NOIP2018全国青少年信息学奥林匹克联赛普及组复赛试题及详细答案

NOIP2018全国青少年信息学奥林匹克联赛普及组复赛试题及详细答案考试时长：3小时满分：400分（每题100分）编译环境：C/C++第一题标题统计（count）【题目描述】凯凯刚写了一篇美妙的作文，请问这篇作文的标题中有多少个字符？注意：标题中可能包含大、小写英文字母、数字字符和空格。统计字符数量时，不统计空格。【输入格式】输入只有一行，为一个字符串，代表作文标题。【输出格式】输出一行一个整数，表示标题中非空格的字符个数。【输入样例】2018noip【输出样例】7【数据范围】字符串长度不超过100。【解题思路】本题为基础字符串模拟题。整体逻辑简单：读取整行字符串，遍历每一个字符，判断字符是否不为空格，累计有效字符数量即可。需要注意：普通cin读取会自动截断空格，必须使用整行读取方式读取输入，避免丢失空格字符导致统计错误。【满分代码】PlainText

#include<iostream>

#include<string>

usingnamespacestd;

intmain()

{

strings;

getline(cin,s);

intcnt=0;

for(inti=0;i<s.size();i++)

{

if(s[i]!='')

cnt++;

}

cout<<cnt<<endl;

return0;

}【答案解析】样例输入：2018noip有效字符：2、0、1、8、n、o、i、p，去除空格后共7个字符，输出结果为7，与样例一致。第二题龙虎斗（fight）【题目描述】轩轩和凯凯正在玩一款对战游戏，游戏中有两个阵营：龙阵营、虎阵营。战场一共有n个兵营，编号1∼n，每个兵营有初始兵力。对于第i号兵营，若i<m属于龙阵营，i>m属于虎阵营，i=m为中立兵营。已知：1.每个龙阵营兵营的兵力对龙势力的贡献为：兵力数值×距离（m−i）2.每个虎阵营兵营的兵力对虎势力的贡献为：兵力数值×距离（i−m）3.中立兵营无势力贡献现在有s个援兵，需要全部部署到某一个兵营（可以是中立、龙、虎阵营兵营），每个援兵提供1点兵力。要求部署后，龙、虎势力差值的绝对值最小。若有多个兵营答案相同，选择编号最小的兵营。【输入格式】第一行一个整数n，表示兵营数量。第二行n个整数，第i个数表示第i个兵营的初始兵力。第三行两个整数m,s，分别表示中立兵营编号、援兵总数。【输出格式】输出一个整数，表示最优部署的兵营编号。【输入样例】623252442【输出样例】4【数据范围】1≤n≤100000，兵力数值、s均不超过1000。【解题思路】1.先遍历所有兵营，计算原始龙势力总和、虎势力总和；2.枚举每一个兵营，模拟将s个援兵部署到该兵营后的势力差值：-部署在龙阵营兵营：龙势力增加s×(m−i)-部署在虎阵营兵营：虎势力增加s×(i−m)-部署在中立兵营：双方势力无变化3.记录差值绝对值最小的兵营，差值相同时保留最小编号。【满分代码】PlainText

#include<iostream>

#include<cmath>

#include<climits>

usingnamespacestd;

typedeflonglongll;

lla[100010];

intmain()

{

intn;

cin>>n;

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

cin>>a[i];

intm,s;

cin>>m>>s;

lldragon=0,tiger=0;

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

{

if(i<m)

dragon+=a[i]*(m-i);

elseif(i>m)

tiger+=a[i]*(i-m);

}

llmin_diff=LLONG_MAX;

intans=m;

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

{

llnd=dragon,nt=tiger;

if(i<m)

nd+=1LL*s*(m-i);

elseif(i>m)

nt+=1LL*s*(i-m);

lldiff=abs(nd-nt);

if(diff<min_diff)

{

min_diff=diff;

ans=i;

}

}

cout<<ans<<endl;

return0;

}【答案解析】样例数据计算：兵营1、2、3为龙阵营，5、6为虎阵营，4为中立阵营。原始龙势力：2×3+3×2+2×1=14原始虎势力：2×1+4×2=10将2个援兵部署在4号中立兵营，双方势力不变，差值为4，为最小差值，因此答案为4。第三题摆渡车（bus）【题目描述】有n名同学要坐车摆渡，第i名同学到达渡口的时间为ti。摆渡车往返及上下客的固定耗时为m，即一辆车发车后，至少需要间隔m一辆车可以搭载任意数量同学。车辆可以在任意时刻发车，要求：所有已经到达渡口且未乘车的同学，全部上车出发。求所有同学全部乘车离开的最小总等待时间。单个同学等待时间=发车时间-到达时间。【输入格式】第一行两个整数n,m。第二行n个整数，依次为每个同学的到达时间ti【输出格式】输出一个整数，表示所有同学的最小总等待时间。【输入样例】551111011【输出样例】4【数据范围】1≤n≤500，0≤ti≤400【解题思路】本题为动态规划基础题。1.先将所有同学的到达时间从小到大排序，方便批量统计等待人数；2.定义dp[i]表示前i个同学全部送走的最小总等待时间；3.枚举上一趟车送走的最后一名同学j，计算本次发车的最早时间，统计j+1∼i同学的等待总时间，更新dp[i]最小值；4.最终dp[n]即为答案。【满分代码】PlainText

#include<iostream>

#include<algorithm>

#include<cstring>

usingnamespacestd;

constintN=510;

intt[N],dp[N];

intmain()

{

intn,m;

cin>>n>>m;

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

cin>>t[i];

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

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

dp[0]=0;

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

{

for(intj=0;j<i;j++)

{

//上一趟发车时间

intlast=(j==0)?0:t[j]+m;

//本次最早发车时间

intst=max(last,t[i]);

intsum=0;

for(intk=j+1;k<=i;k++)

sum+=st-t[k];

dp[i]=min(dp[i],dp[j]+sum);

}

}

cout<<dp[n]<<endl;

return0;

}【答案解析】样例排序后时间：1、1、1、10、111.第一趟车最早可在1时刻发车，送走前3名同学，等待时间均为0，总等待0；2.下一趟最早发车时间为1+5=6，晚于10，因此10时刻之后发车；3.10时刻发车，第四名等待0，第五名11到达，需等待1，总等待1；最优方案总等待时间为4，与样例输出一致。第四题对称二叉树（tree）【题目描述】一棵二叉树有n个节点，节点编号1∼n，每个节点有权值。定义对称二叉树：1.根节点的左子树与右子树结构完全对称；2.对称位置的节点权值完全相等。请找出这棵二叉树中，节点数量最多的对称子树，输出其节点个数。【输入格式】第一行一个整数n，表示节点数量。第二行n个整数，依次为1∼n号节点的权值。接下来n行，每行两个整数，分别表示当前节点的左孩子、右孩子编号，无孩子则为-1。【输出格式】输出一个整数，为最大对称子树的节点数。【输入样例】71223443234567-1-1-1-1-1-1-1-1【输出样例】7【数据范围】1≤n≤1000。【解题思路】1.递归判断两棵子树是否对称：节点权值相等，且左子树的左孩子与右子树的右孩子对称、左子树的右孩子与右子树的左孩子对称；2.递归统计每棵子树的节点数量；3.遍历所有节点作为根，判断其是否为对称子树，记录最大节点数。【满分代码】PlainText

#include<iostream>

#include<algorithm>

usingnamespacestd;

constintN=1010;

intval[N],lch[N],rch[N];

intn,ans=1;

//判断u和v子树是否对称

boolcheck(intu,intv)

{

if(u==-1&&v==-1)returntrue;

if(u==-1||v==-1)returnfalse;

if(val[u]!=val[v])returnfalse;

returncheck(lch[u],rch[v])&&check(rch[u],lch[v]);

}

//统计子树节点数

intsize(intu)

{

if(u==-1)return0;

return1+size(lch[u])+size(rch[u]);

}

intmain()

{

cin>>n;

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

cin>>val[i];

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

cin>>lch[i]>>rch[i];

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

{

if(check(lch[i],rch[i]))

ans=max(ans,size(i));

}

cout<<ans<<end