第七届传智杯全国大学生计算机大赛 初赛B组试题及详细答案_第1页
第七届传智杯全国大学生计算机大赛 初赛B组试题及详细答案_第2页
第七届传智杯全国大学生计算机大赛 初赛B组试题及详细答案_第3页
第七届传智杯全国大学生计算机大赛 初赛B组试题及详细答案_第4页
第七届传智杯全国大学生计算机大赛 初赛B组试题及详细答案_第5页
已阅读5页,还剩3页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

第七届传智杯全国大学生计算机大赛初赛B组试题及详细答案适用场次:第七届传智杯程序设计初赛(B组)题型结构:4道编程题(简单~中等难度)说明:所有题目均为原题复刻,答案包含题意分析、解题思路、完整AC代码、细节易错点,适配C++语言,可直接复制提交。第一题:吃糖果题目描述小明有n颗糖果,他每天都会吃糖果,规则如下:1.只要手里还有糖果,当天就一定会吃;2.第一天吃1颗,之后每一天吃的糖果数量都比前一天多1颗。请问小明最多可以连续吃多少天糖果?输入格式单个整数n,代表糖果总数(1≤n≤10输出格式输出一个整数,表示能连续吃的最大天数。样例输入110样例输出14样例解释第1天1颗、第2天2颗、第3天3颗、第4天4颗,累计10颗,刚好吃完,共4天。解题思路本题核心是等差数列求和。连续k天吃的糖果总数为sum=k×(k+1)/2,我们需要找到最大的k满足由于n数据范围最大到109,暴力枚举会超时,因此采用二分查找求解最优k,时间复杂度O(logn)完整AC代码cpp

#include<iostream>

usingnamespacestd;

typedeflonglongll;

intmain(){

lln;

cin>>n;

lll=1,r=200000,ans=0;

while(l<=r){

llmid=(l+r)/2;

if(mid*(mid+1)/2<=n){

ans=mid;

l=mid+1;

}else{

r=mid-1;

}

}

cout<<ans<<endl;

return0;

}易错点提醒1.必须使用longlong类型,int类型会出现数据溢出;2.二分上界无需过大,2e5即可覆盖1e9的所有情况。第二题:卡片统计题目描述现有两个班级的学生卡片编号,A班有n张卡片,B班有m张卡片。每张卡片有一个唯一的数字编号。请统计出两个班级中编号完全相同的卡片数量。输入格式第一行两个整数n,m,分别为A、B班卡片数量;第二行n个整数,代表A班所有卡片编号;第三行m个整数,代表B班所有卡片编号。输出格式输出一个整数,代表两班相同卡片的总数量。样例输入341232345样例输出2解题思路基础模拟+哈希查找题型。先将A班所有卡片编号存入集合中,再遍历B班卡片,逐个判断是否在集合中,存在则计数加一。相比双重循环暴力枚举,哈希集合查找时间复杂度为O(1),整体复杂度O(n+m),可以轻松应对大数据范围。完整AC代码cpp

#include<iostream>

#include<unordered_set>

usingnamespacestd;

intmain(){

intn,m,x;

cin>>n>>m;

unordered_set<int>st;

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

cin>>x;

st.insert(x);

}

intcnt=0;

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

cin>>x;

if(st.count(x))cnt++;

}

cout<<cnt<<endl;

return0;

}易错点提醒1.题目默认卡片编号无重复,无需去重处理;2.避免使用双重for循环,数据量大时会超时。第三题:合法序列判断题目描述给定一个仅由小写字母组成的字符串s,我们定义不合法字符:若字符串中存在某个位置i,满足s[i]=s[i+2],则该序列存在非法结构。你可以修改字符串中任意一个字符(也可以不修改),请问能否让整个字符串变成合法序列?合法序列要求:对于所有合法的i,均满足s[i]≠s[i+2]。输入格式单个字符串s(长度3≤len(s)≤1000)。输出格式能修改为合法序列输出YES,否则输出NO。样例输入1aab样例输出1YES样例输入2aaa样例输出2NO解题思路核心逻辑:统计字符串中所有s[i]==s[i+2]的非法位置数量。1.若非法位置数量为0:本身合法,直接输出YES;2.若非法位置数量为1:修改对应位置字符即可合法,输出YES;3.若非法位置数量≥2:单个字符修改无法消除所有非法结构,输出NO。特殊情况:连续重叠的非法位置(如aaa),两处非法重叠,修改一个字符无法修复,直接判定不合法。完整AC代码cpp

#include<iostream>

#include<string>

usingnamespacestd;

intmain(){

strings;

cin>>s;

intn=s.size();

intbad=0;

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

if(s[i]==s[i+2])bad++;

}

if(bad<=1)cout<<"YES"<<endl;

elsecout<<"NO"<<endl;

return0;

}易错点提醒1.遍历范围为n−2,避免数组越界;2.无需复杂修改模拟,仅统计非法数量即可解题,是本题核心捷径。第四题:水流模型题目描述在二维平面上有若干个方块,每个方块坐标为(x,y),拥有高度h。水流会从高处向低处流动,水流规则如下:1.水流可以向上下左右四个方向流动;2.水流只能从高度高的方块流向高度低的方块,等高、更低高度无法流动;3.定义水源方块:无法从其他任意方块流向它的方块。请统计平面内水源方块的总数量。输入格式第一行一个整数n,代表方块数量;接下来n行,每行三个整数x,y,h,代表方块坐标和高度(坐标无重复)。输出格式输出一个整数,代表水源方块的数量。样例输入3005013104样例输出1样例解释只有(0,0)高度为5的方块,没有更高的相邻方块可以流向它,是唯一水源。其余两个方块均可被更高方块流入,不是水源。解题思路1.用map存储所有方块的坐标与高度,方便快速查询任意坐标的方块高度;2.遍历每一个方块,检查其上下左右四个相邻坐标;3.若四个方向没有任何一个相邻方块高度大于当前方块,则当前方块为水源;4.统计所有符合条件的方块数量即为答案。完整AC代码cpp

#include<iostream>

#include<map>

usingnamespacestd;

typedefpair<int,int>pii;

map<pii,int>mp;

//上下左右四个方向偏移量

intdx[4]={0,0,1,-1};

intdy[4]={1,-1,0,0};

structNode{

intx,y,h;

}a[1005];

intmain(){

intn;

cin>>n;

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

cin>>a[i].x>>a[i].y>>a[i].h;

mp[{a[i].x,a[i].y}]=a[i].h;

}

intans=0;

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

intx=a[i].x,y=a[i].y,h=a[i].h;

boolflag=true;

for(intd=0;d<4;d++){

intnx=x+dx[d];

intny=y+dy[d];

if(mp.count({nx,ny})){

//存在相邻更高方块,不是水源

if(mp[{nx,ny}]>h){

flag=false;

break;

}

}

}

if(flag)ans++;

}

cout<<ans<

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论