ACM程序设计新生赛试题（含详细答案代码）

ACM程序设计新生赛试题（含详细答案代码）比赛说明1.试题共5题，难度由易到难，满分100分，比赛时长120分钟2.编程语言仅限C/C++，所有题目均有多组测试数据/单组数据标注3.输出严格按照格式，禁止多余空格、换行，否则判PE4.代码均为标准比赛AC代码，可直接提交OJProblem1整数求和（10分）题目描述给定两个整数a、b，请你计算a+b的结果并输出。输入多组输入，每组一行两个整数a,b（-1000≤a,b≤1000）。输入直到文件结束（EOF）为止。输出对于每组输入，输出一行一个整数，表示两数之和。样例输入12-53100-200样例输出3-2-100解题思路入门基础题，考察多组数据读取和基础运算。C++中使用while(cin>>a>>b)可以循环读取数据直到输入结束，每次读取完成直接输出求和结果即可。数据范围极小，无需考虑溢出问题。AC代码cpp

#include<iostream>

usingnamespacestd;

intmain()

{

inta,b;

while(cin>>a>>b)

{

cout<<a+b<<endl;

}

return0;

}Problem2奇偶判断（15分）题目描述输入一个正整数n，判断这个数是奇数还是偶数。如果是偶数，输出Even；如果是奇数，输出Odd。输入第一行一个整数T，表示测试数据组数（1≤T≤100）接下来T行，每行一个正整数n（1≤n≤10000）输出每组数据单独一行输出结果。样例输入32799样例输出EvenOddOdd解题思路考察分支结构和取模运算。一个数对2取模，余数为0即为偶数，否则为奇数。先读取数据组数，循环T次判断输出即可。题目数据范围小，无特殊边界情况。AC代码cpp

#include<iostream>

usingnamespacestd;

intmain()

{

intT,n;

cin>>T;

while(T--)

{

cin>>n;

if(n%2==0)

cout<<"Even"<<endl;

else

cout<<"Odd"<<endl;

}

return0;

}Problem3字符统计（20分）题目描述给定一串只包含小写字母的字符串，请统计字符串中字母a出现的次数。输入一行字符串，长度不超过1000，无空格。输出输出一个整数，表示字符a的出现次数。样例输入abacada样例输出4解题思路考察字符串遍历操作。定义计数器初始值为0，逐个遍历字符串的每一位字符，如果字符等于'a'，计数器累加1。遍历结束后输出计数器的值即可。C++string字符串可以直接通过下标访问字符。AC代码cpp

#include<iostream>

#include<string>

usingnamespacestd;

intmain()

{

strings;

cin>>s;

intcnt=0;

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

{

if(s[i]=='a')

cnt++;

}

cout<<cnt<<endl;

return0;

}Problem4最大最小值（25分）题目描述给定n个整数，请你找出这组数据中的最大值和最小值，并按照最小值最大值的格式输出。输入第一行输入一个整数n（1≤n≤100）第二行输入n个整数，范围在[-1000,1000]输出输出两个整数，用空格分隔，先最小值后最大值。样例输入515-293样例输出-29解题思路考察数组遍历和极值查找。初始化最大值为极小值，最小值为极大值。遍历所有数字，不断更新最大、最小值。也可以使用数组存储所有数字后遍历比较。需要注意负数的判断，不能默认初始值为0。AC代码cpp

#include<iostream>

#include<algorithm>

usingnamespacestd;

intmain()

{

intn;

cin>>n;

intmaxn=-1005;

intminn=1005;

intx;

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

{

cin>>x;

if(x>maxn)maxn=x;

if(x<minn)minn=x;

}

cout<<minn<<""<<maxn<<endl;

return0;

}Problem5最短距离（30分）题目描述在一条数轴上有两个点A和B，分别对应坐标x和y。你可以进行两种操作：1.向左或向右移动1单位，花费1秒2.直接瞬移到当前坐标两倍的位置，花费1秒求从坐标x到达坐标y的最短时间。输入两个整数x,y（0≤x<y≤100000）输出输出最短时间样例输入1310样例输出13解释：3→6(瞬移1s)→7(移动1s)→14(瞬移不行)，最优：3→6→12→11→10总3秒样例输入258样例输出23解题思路经典BFS广度优先搜索模板题，求最短步数。每一个坐标为一个状态，每种操作对应一条边，权重为1，BFS天然可以求解无权图最短路径。关键点：1.记录每个坐标的访问时间，避免重复访问2.坐标上限控制在1e5+10，防止越界3.一旦搜到目标坐标立即返回步数，保证最短AC代码cpp

#include<iostream>

#include<queue>

#include<cstring>

usingnamespacestd;

constintMAXN=100010;

intvis[MAXN];

intx,y;

structNode

{

intpos;

intstep;

};

intbfs()

{

memset(vis,0,sizeof(vis));

queue<Node>q;

q.push({x,0});

vis[x]=1;

while(!q.empty())

{

Nodenow=q.front();

q.pop();

if(now.pos==y)

returnnow.step;

//三种移动方式

intnx1=now.pos+1;

intnx2=now.pos-1;

intnx3=now.pos*2;

if(nx1<=MAXN&&!vis[nx1])

{

vis[nx1]=1;

q.push({nx1,now.step+1});

}

if(nx2>=0&&!vis[nx2])

{

vis[nx2]=1;

q.push({nx2,now.step+1});

}

if(nx3<=MAXN&&!vis[nx3])

{

vis[nx3]=1;

q.push({nx3,now.step+1});

}

}

return0;

}

intmain()

{

cin>>x>>y;

cout<<bfs()<<endl;

re