ACM程序设计竞赛基础题型试题（含详细答案解析）

ACM程序设计竞赛基础题型试题（含详细答案解析）本次试题为ACM入门级正式竞赛题型，适配校赛、省赛基础档位，包含字符串处理、模拟遍历、基础数论、贪心算法四大核心题型，共4道题，每题包含题目描述、输入输出、样例、详细解题思路及AC代码，无套路模板，贴合真实赛场出题逻辑。编译环境：C++11及以上|评测模式：标准IO、无特殊判题、严格匹配输出格式第一题：字符串统计（基础字符串题）题目描述给定一个仅包含大小写英文字母的字符串，统计其中大写字母、小写字母的个数，并输出转换后的全小写字符串。输入格式一行字符串，长度不超过1000，无空格。输出格式第一行输出两个整数，分别为大写字母个数、小写字母个数，中间空格分隔；第二行输出原字符串转换为全部小写的新字符串。样例输入AcM2026Test样例输出37acm2026test解题思路1.定义两个计数变量，初始值为0，分别统计大小写字母数量；2.遍历字符串每一个字符，通过ASCII码范围判断字符类型：A-Z为大写，a-z为小写；3.利用tolower函数将所有字符转为小写，拼接新字符串；4.按格式依次输出计数结果和转换后的字符串。AC代码cpp

#include<iostream>

#include<string>

#include<cctype>

usingnamespacestd;

intmain()

{

strings;

cin>>s;

intupper=0,lower=0;

stringres;

for(charc:s)

{

if(c>='A'&&c<='Z')upper++;

elseif(c>='a'&&c<='z')lower++;

res+=tolower(c);

}

cout<<upper<<""<<lower<<endl;

cout<<res<<endl;

return0;

}第二题：整数奇偶求和（模拟遍历题）题目描述给定n个整数，分别计算所有奇数的和、偶数的和，并统计奇数和偶数的个数。输入格式第一行一个整数n（1≤n≤100），代表数字个数；第二行n个整数，绝对值不超过1000，空格分隔。输出格式共两行输出：第一行：奇数个数奇数和第二行：偶数个数偶数和样例输入512345样例输出3926解题思路1.读取数据个数n，循环读取n个整数；2.设置四个变量，分别记录奇数个数、奇数和、偶数个数、偶数和，初始均为0；3.对每个数字取模2判断奇偶，注意负数取模不影响奇偶判断结果；4.对应累加个数和数值，遍历结束后按格式输出结果。AC代码cpp

#include<iostream>

usingnamespacestd;

intmain()

{

intn;

cin>>n;

intcnt_odd=0,sum_odd=0;

intcnt_even=0,sum_even=0;

intx;

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

{

cin>>x;

if(x%2!=0)

{

cnt_odd++;

sum_odd+=x;

}

else

{

cnt_even++;

sum_even+=x;

}

}

cout<<cnt_odd<<""<<sum_odd<<endl;

cout<<cnt_even<<""<<sum_even<<endl;

return0;

}第三题：素数判断与统计（基础数论题）题目描述给定一个正整数n（2≤n≤1000），统计2~n之间所有素数的个数，并从小到大输出所有素数。素数定义：大于1，且只能被1和自身整除的自然数。输入格式单个整数n。输出格式第一行输出素数的总个数；第二行从小到大输出所有素数，空格分隔。样例输入10样例输出42357解题思路1.单独编写素数判断函数：对于一个数x，遍历2到sqrt(x)，若存在能整除x的数，则不是素数，否则为素数；2.遍历2到n的所有整数，逐个判断是否为素数；3.统计素数数量，同时保存所有素数；4.先输出总数，再遍历输出所有素数。优化点：无需遍历到x-1，遍历到根号x即可，减少循环次数，提升运行效率。AC代码cpp

#include<iostream>

#include<vector>

#include<cmath>

usingnamespacestd;

//素数判断函数

boolisPrime(intx)

{

if(x<2)returnfalse;

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

{

if(x%i==0)returnfalse;

}

returntrue;

}

intmain()

{

intn;

cin>>n;

vector<int>prime;

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

{

if(isPrime(i))

{

prime.push_back(i);

}

}

//输出结果

cout<<prime.size()<<endl;

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

{

if(i>0)cout<<"";

cout<<prime[i];

}

cout<<endl;

return0;

}第四题：最大区间和（简单贪心题）题目描述给定一组整数（可正可负），找出连续子数组的最大和。例如数组[-2,1,-3,4,-1,2,1,-5,4]，最大连续区间和为6（区间4,-1,2,1）。输入格式第一行输入整数n（1≤n≤100）；第二行n个整数，空格分隔。输出格式输出最大连续子区间和。样例输入9-21-34-121-54样例输出6解题思路本题采用经典贪心思路（Kadane算法），逻辑简单高效，适合入门赛场解题：1.定义两个变量，当前区间和cur、最大区间和max_sum，初始均赋值为第一个元素；2.从第二个元素开始遍历数组：判断当前元素是否比「当前区间和+当前元素」更大；3.若当前元素更大，说明之前的区间和为负数，直接舍弃之前区间，重新以当前元素为新区间起点；4.否则继续累加，每次遍历更新最大区间和；5.遍历结束后，max_sum即为答案。AC代码cpp

#include<iostream>

#include<algorithm>

usingnamespacestd;

intmain()

{

intn;

cin>>n;

inta[105];

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

{

cin>>a[i];

}

intcur=a[0];

intmax_sum=a[0];

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

{

cur=max(a[i],cur+a[i]);