ACM-ICPC 竞赛基础试题及详细答案解析

ACM-ICPC竞赛基础试题及详细答案解析说明：本套试题选取ACM-ICPC区域赛、校赛高频基础题型，涵盖模拟、贪心、字符串、简单数学、基础遍历五大核心考点，适配入门及进阶备赛训练。所有题目均附带完整解题思路、详细推导过程以及可直接提交的标准代码，解题思路贴合赛场实战思维，无冗余赘述。适用场景：ACM校赛、省赛基础题训练、算法入门刷题测试试题一：数字反转（模拟题）题目描述：给定一个整数n，将该数的数字反转输出。若反转后的数字前导为0，需要自动去除；若原数为负数，反转后保留负号。输入格式：一行一个整数n，范围−100000≤n≤100000输出格式：输出反转后的整数样例输入1：123样例输出1：321样例输入2：-120样例输出2：-21解题思路本题为ACM基础模拟题型，核心是逐位拆解数字、反向拼接，同时处理符号和前导零问题。首先判断数字正负，记录符号后对绝对值进行反转运算。通过取余运算提取末尾数字，逐步构建反转后的数值，最后还原正负号即可。整个过程无需复杂算法，重点考察代码逻辑严谨性和边界条件处理能力。完整AC代码（C++）cpp

#include<iostream>

usingnamespacestd;

intmain()

{

intn;

cin>>n;

intres=0;

intflag=1;

//处理负数

if(n<0)

{

flag=-1;

n=-n;

}

//逐位反转数字

while(n>0)

{

res=res*10+n%10;

n=n/10;

}

cout<<res*flag<<endl;

return0;

}试题二：最大子段和（贪心/动态规划）题目描述：给定一段包含正负整数的序列，求出该序列中连续子数组的最大和。子数组最少包含一个元素。输入格式：第一行输入一个整数m，表示数组元素个数；第二行输入m个整数，为数组元素。输出格式：输出最大连续子段和样例输入：9-21-34-121-54样例输出：6解释：最优子段为[4,-1,2,1]，和为6。解题思路本题是ACM经典入门算法题，可采用贪心思路高效求解。遍历数组过程中，维护当前子段和与全局最大和。若当前子段和累加当前元素后变为负数，说明当前子段无贡献，直接舍弃，从下一个元素重新开始累计；若为正数则继续累加。每次遍历均更新全局最大和，一次遍历即可完成求解，时间复杂度为O(n)，效率优于普通暴力枚举。完整AC代码（C++）cpp

#include<iostream>

#include<algorithm>

usingnamespacestd;

intmain()

{

intm;

cin>>m;

intnum[1005];

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

{

cin>>num[i];

}

intcurrent=num[0];

intmax_sum=num[0];

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

{

current=max(num[i],current+num[i]);

max_sum=max(max_sum,current);

}

cout<<max_sum<<endl;

return0;

}试题三：字符串统计（字符串基础）题目描述：输入一行仅包含大小写英文字母的字符串，统计并输出字符串中大写字母、小写字母的个数。输入格式：一行字符串，长度不超过1000。输出格式：第一行输出大写字母个数，第二行输出小写字母个数。样例输入：AcM-IcPc样例输出：43解题思路本题考察ACM竞赛中字符串基础操作与字符ASCII码判断规则。遍历字符串每一位字符，通过ASCII码范围区分大小写字母：大写字母A-Z对应ASCII65-90，小写字母a-z对应ASCII97-122。设置两个计数器，遍历过程中分别累加统计，遍历结束后依次输出结果即可，逻辑简单，重点考察代码细节和字符判断规范。完整AC代码（C++）cpp

#include<iostream>

#include<string>

usingnamespacestd;

intmain()

{

strings;

cin>>s;

intupper=0,lower=0;

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

{

if(s[i]>='A'&&s[i]<='Z')

upper++;

elseif(s[i]>='a'&&s[i]<='z')

lower++;

}

cout<<upper<<endl;

cout<<lower<<endl;

return0;

}试题四：素数判断（数学基础）题目描述：给定一个正整数x，判断该数是否为素数。若是素数输出YES，否则输出NO。素数定义：大于1，且除了1和自身外无其他约数的自然数。输入格式：单个正整数x（1≤x≤10000）输出格式：YES或NO样例输入1：7样例输出1：YES样例输入2：10样例输出2：NO解题思路素数判断是数论基础题型，赛场常用优化解法。首先处理特殊情况：小于2的数一定不是素数。对于大于等于2的数，无需遍历全部数值，只需遍历到该数的平方根即可，若区间内存在约数，则不是素数，反之则为素数。该优化方式可大幅减少循环次数，提升代码运行效率，适配竞赛数据范围要求。完整AC代码（C++）cpp

#include<iostream>

#include<cmath>

usingnamespacestd;

boolisPrime(intx)

{

if(x<2)

returnfalse;

for(inti=2;i<=sqrt(x);i++)

{

if(x%i==0)

returnfalse;

}

returntrue;

}

intmain()

{

intx;

cin>>x;

if(isPrime(x))

cout<<"YES"<<endl;

else

cout<<"NO"<<endl;

return0;

}试题五：冒泡排序（基础模拟）题目描述：输入n个整数，使用冒泡排序算法将数组从小到大排序，输出排序后的完整序列，数字之间用空格分隔。输入格式：第一行输入整数n，表示元素个数；第二行输入n个整数。输出格式：一行排序后的整数序列样例输入：531425样例输出：12345解题思路冒泡排序是竞赛基础排序算法，核心逻辑是相邻元素两两比较，若前一个元素大于后一个元素则交换位置，每一轮遍历都会将当前未排序部分的最大值冒泡至末尾。经过n-1轮遍历后，数组即可完成升序排序。本题重点考察基础排序逻辑的手写实现，是算法竞赛入门必掌握题型。完整AC代码（C++）cpp

#include<iostream>

usingnamespacestd;

intmain()

{

intn;

cin>>n;

intarr[105];

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

{

cin>>arr[i];

}

//冒泡排序核心代码

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

{

for(intj=0;j<n-1-i;j++)

{

if(arr[j]>arr[j+1])

{

inttemp=arr[j];

arr[j]=arr[j+1];

arr[j+1]=temp;

}

}

}

//输出结果

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

{