首页/新闻资讯/正文详情

蓝桥杯 C++ 算法入门:洛谷 P1598《垂直柱状图》——计数数组与模拟

发布时间:2026/11/17 11:13:39 来源:云帆数科 栏目:资讯中心
蓝桥杯 C++ 算法入门:洛谷 P1598《垂直柱状图》——计数数组与模拟
一、题目来源题目名称P1598 [USACO03FEB] 垂直柱状图Vertical Histogram题目链接https://www.luogu.com.cn/problem/P1598知识点字符串、数组统计、循环、模拟、格式化输出难度定位基础算法入门练习目标掌握字符出现次数统计并学会用嵌套循环输出垂直直方图。说明这是一道经典算法练习题并非蓝桥杯官方真题。通过这道题可以训练蓝桥杯 C B 组需要的基础编程能力。二、题目描述输入四行文本统计其中每个大写英文字母A到Z出现的次数并将统计结果绘制成垂直直方图。每个字母对应一列字母出现一次就在对应列中增加一个星号*。输出要求直方图从最高的一层开始输出。每个字母对应的星号数量等于它的出现次数。星号不足的位置使用空格占位。最后一行按照字母顺序输出A B C ... Z。每行末尾不能有多余空格也不能输出额外的空行。核心问题如何先统计字母出现次数再把统计结果转换成竖直方向的星号图形三、解题思路整个程序可以分为四个步骤。1. 使用数组统计字母次数由于英文字母一共只有 26 个可以定义一个长度为 26 的整数数组intcnt[26]{0};其中cnt[0]表示字母 A 的出现次数。cnt[1]表示字母 B 的出现次数。cnt[2]表示字母 C 的出现次数。……cnt[25]表示字母 Z 的出现次数。利用字符编码可以通过下面的表达式将字母转换为数组下标cnt[ch-A];例如A-A// 结果为 0B-A// 结果为 1C-A// 结果为 2当遇到字母 C 时cnt[ch - A]实际上就是cnt[2]表示 C 的出现次数加一。由于输入是四行文本因此需要循环读取四行再遍历每一行中的字符。for(inti0;i4;i){getline(cin,s);for(charch:s){if(chAchZ){cnt[ch-A];}}}这里使用getline()读取整行能够保留空格等字符。通过判断字符是否处于A到Z之间可以避免将其他字符错误地作为数组下标。2. 找到直方图的最大高度直方图的总高度由出现次数最多的字母决定。例如字母出现次数A4B1C2A 出现了 4 次因此直方图需要输出 4 层星号。代码如下intmaxn0;for(inti0;i26;i){if(cnt[i]maxn){maxncnt[i];}}也可以使用max()更新最大值maxnmax(maxn,cnt[i]);3. 使用嵌套循环输出直方图这是整道题最重要的部分。外层循环控制高度从最大值逐渐减小到 1for(inthmaxn;h1;h--)内层循环依次检查每个字母if(cnt[j]h){cout*;}else{cout ;}判断规则是如果某个字母的出现次数大于等于当前高度就输出*。否则输出空格。为什么要使用cnt[j] h假设 A 出现 4 次那么它应该在第 4、3、2、1 层都有星号。当h 4时cnt[A] 4成立。当h 3时cnt[A] 3仍然成立。一直到h 1A 都应该输出星号。注意每两列之间需要一个空格但是每行末尾不能出现多余空格。因此输出每个字母对应的列之前应先确定当前行最后一个有星号的位置。4. 输出最后一行的字母完成所有星号输出后再输出字母 A 到 Zfor(inti0;i26;i){if(i0){cout ;}coutchar(Ai);}cout\n;这里使用char(A i)将数组下标转换成对应字母。通过判断i 0保证只有从第二个字母开始才输出分隔空格从而避免最后一个字母 Z 后面出现多余空格。四、完整 C 代码下面是可以提交到洛谷的完整参考代码使用 C17 编译标准。#includeiostream#includestringusingnamespacestd;intmain(){intcnt[26]{0};string s;// 第一步读取四行文本统计字母次数for(inti0;i4;i){getline(cin,s);for(charch:s){if(chAchZ){cnt[ch-A];}}}// 第二步寻找直方图最大高度intmaxn0;for(inti0;i26;i){if(cnt[i]maxn){maxncnt[i];}}// 第三步从最高层向下输出星号for(inthmaxn;h1;h--){// 找到当前行最后一个需要输出星号的位置intlast25;while(last0cnt[last]h){last--;}// 输出当前行避免行尾多余空格for(intj0;jlast;j){if(j0){cout ;}if(cnt[j]h){cout*;}else{cout ;}}cout\n;}// 第四步输出 A 到 Zfor(inti0;i26;i){if(i0){cout ;}coutchar(Ai);}cout\n;return0;}五、样例演示下面是一个用于理解算法的自定义样例并非洛谷官方样例。输入ABC A AC A统计结果字母出现次数A4B1C2其他字母的出现次数均为 0。输出* * * * * * * A B C D E F G H I J K L M N O P Q R S T U V W X Y Z输出过程分析当h 4时只有 A 出现了 4 次因此输出*当h 3时仍然只有 A 满足条件*当h 2时A 和 C 满足条件B 不满足条件* *当h 1时A、B、C 都满足条件* * *最后输出字母表A B C D E F G H I J K L M N O P Q R S T U V W X Y Z六、HTML 动画演示为了更直观地理解直方图的生成过程可以使用下面的 HTML 页面。动画使用 A、B、C 三个字母作为演示数据分别出现 4 次、1 次、2 次。页面会逐行显示星号模拟程序从最高层向下输出的过程并提供重新播放按钮。使用方法复制下面全部 HTML 代码。保存为histogram-animation.html。使用浏览器打开文件即可观看动画。修改counts数组中的数值可以观察不同统计结果对应的直方图。!DOCTYPEhtmlhtmllangzh-CNheadmetacharsetUTF-8metanameviewportcontentwidthdevice-width, initial-scale1.0title垂直柱状图动画演示/titlestylebody{font-family:Arial,sans-serif;max-width:680px;margin:40px auto;padding:20px;background:#f5f7fb;color:#243047;}.card{background:white;padding:24px;border-radius:14px;box-shadow:0 4px 18pxrgba(0,0,0,0.08);}h1{font-size:24px;}.description{color:#667085;line-height:1.8;}#histogram{min-height:150px;padding:16px;background:#101828;color:#6ee7b7;border-radius:8px;font-family:Consolas,monospace;font-size:20px;line-height:1.7;white-space:pre;overflow-x:auto;}.line{animation:appear 0.4s ease-out both;}keyframesappear{from{opacity:0;transform:translateY(8px);}to{opacity:1;transform:translateY(0);}}button{margin-top:18px;padding:10px 18px;border:none;border-radius:8px;background:#2563eb;color:white;cursor:pointer;font-size:15px;}button:hover{background:#1d4ed8;}.note{margin-top:16px;font-size:13px;color:#667085;}/style/headbodydivclasscardh1垂直柱状图动画演示/h1pclassdescription演示数据A 出现 4 次B 出现 1 次C 出现 2 次。 程序从最高层开始逐层输出星号。/pdividhistogramaria-livepolite/divbuttonidreplay重新播放动画/buttonpclassnote观察每一层当字母的出现次数大于等于当前高度时 对应位置输出星号否则输出空格。/p/divscript// 每个数字表示对应字母出现的次数constletters[A,B,C];constcounts[4,1,2];consthistogramdocument.getElementById(histogram);lettimers[];// 根据统计结果生成直方图的每一行functionbuildLines(){constmaxCountMath.max(...counts);constlines[];for(lethmaxCount;h1;h--){// 找到当前行最后一个有星号的位置letlastcounts.length-1;while(last0counts[last]h){last--;}letline;for(letj0;jlast;j){if(j0){line ;}if(counts[j]h){line*;}else{line ;}}lines.push(line);}// 最后一行输出字母标签lines.push(letters.join( ));returnlines;}// 逐行播放functionplayAnimation(){timers.forEach(timerclearTimeout(timer));timers[];histogram.innerHTML;constlinesbuildLines();lines.forEach((line,index){consttimersetTimeout((){constrowdocument.createElement(div);row.classNameline;row.textContentline;histogram.appendChild(row);},index*550);timers.push(timer);});}document.getElementById(replay).addEventListener(click,playAnimation);// 页面加载后自动播放playAnimation();/script/body/html注意CSDN 正文通常会将代码块中的 HTML 和 JavaScript 作为文本展示不一定允许直接运行。将代码保存为独立 HTML 文件就可以在浏览器中查看动画。七、常见错误总结1. 忘记使用getline()cins;cin s通常只读取空白字符之前的内容。如果需要读取整行文本应使用getline(cin,s);2. 数组下标计算错误错误写法cnt[ch];如果直接将字符作为下标会访问 ASCII 编码对应的位置而不是 0 到 25 之间的字母位置。正确写法cnt[ch-A];3. 直方图从下往上输出题目要求从最高层向下输出因此高度应该逐渐减小for(inthmaxn;h1;h--)4. 判断条件写错正确判断是if(cnt[j]h)因为出现次数为 4 的字母不仅要在第 4 层输出星号还要在第 3、2、1 层输出星号。如果错误地写成cnt[j] h每个字母只会输出一颗星无法形成柱状图。5. 忽略行尾空格输出格式也是本题的重要考点。如果每一列后面都直接输出空格最后一列之后可能留下多余空格。可以通过确定当前行最后一个有星号的位置避免输出多余的尾随空格。八、时间复杂度与空间复杂度设四行文本的字符总数为 N出现次数最多的字母出现了 H 次。统计阶段遍历所有输入字符时间复杂度为 O(N)。寻找最大值遍历 26 个数组元素时间复杂度为 O(26)。绘制直方图每层最多检查 26 个字母时间复杂度为 O(26H)。因此总时间复杂度可以写为O(N 26H)由于英文字母数量固定为 26空间复杂度为 O(1)不计输入字符串本身的存储空间。九、这道题能学到什么通过这道题我总结出四个重要知识点计数数组使用数组下标记录不同字符出现的次数。字符与整数转换理解ch - A和char(A i)的含义。嵌套循环外层控制高度内层遍历每个字母。输出格式控制注意空格、换行和行尾多余字符。这道题虽然没有复杂的算法但能很好地训练字符串处理、数组统计、循环控制和模拟输出能力。对于正在准备蓝桥杯 C B 组的同学建议先独立完成计数部分再自己编写最大值查找和星号输出循环不要一开始就直接复制完整代码。十、下一步练习完成这道题后可以继续练习字母出现次数统计数字频率统计数组最大值与最小值字符串模拟嵌套循环打印图形蓝桥杯历年基础模拟题。最后总结本题的核心不是统计字母本身而是将统计结果转换成图形。掌握计数数组、最大值查找和分层输出之后就可以将相同思路应用到许多基础模拟题中。题目地址https://www.luogu.com.cn/problem/P1598

相关推荐

经营分析五步法:看趋势、找差距、挖原因、定行动、追结果
经营分析五步法:看趋势、找差距、挖原因、定行动、追结果

很多企业每个月都做经营分析。财务部门整理收入、利润和费用数据;业务部门汇报目标完成情况;管理层根据报表提出改进要求。但到了下个月,同样的问题往往还会出现。收入没有达到目标,要求销售加大客户开发力度;毛利率下… · 2026/11/13 15:28:20

关于stop模式下RTC唤醒不进入main的问题
关于stop模式下RTC唤醒不进入main的问题

项目场景: STM32L073VZT6在Stop模式下RTC唤醒执行完回调函数后不进入mian循环。 项目场景:stop低功耗裸机设计,RTC秒唤醒执行完被置起的任务后进入stop模式。其中有个任务是使用LPUART的DMA发送,接收用IDLE中断。确定的是发送数据… · 2026/11/10 20:41:00

今日开源工具推荐:KeePassXC 2.8.0 + Syncthing 2.1.7,密码与文件一次管好
今日开源工具推荐:KeePassXC 2.8.0 + Syncthing 2.1.7,密码与文件一次管好

今天推荐两个刚更新的开源工具:一个帮你把电脑、手机之间的文件同步起来,一个帮你把越来越多的账号密码收进一个加密库。两个都免费、无广告、不用注册账号。 一、Syncthing 2.1.7:不经过服务器的文件同步 Syncthing 是点对点同步工具&… · 2026/11/15 21:16:56

江苏电工证plc调试内部消息:外省证能不能转过来?别再被忽悠了
江苏电工证plc调试内部消息:外省证能不能转过来?别再被忽悠了

江苏电工证plc调试内部消息:外省证能不能转过来?别再被忽悠了 之前考的证在外省能不能转过来?说实话,很多小伙伴在考完证后才发现, 江苏电工证plc调试… · 2026/11/17 11:12:50

长乐哪里有电工证培训 电工证考不过白交钱?官方报名入口全解析
长乐哪里有电工证培训 电工证考不过白交钱?官方报名入口全解析

长乐哪里有电工证培训 电工证考不过白交钱?官方报名入口全解析 怕考不过白交培训费?别急,先搞清楚长乐哪里有电工证培训,再看官方报名入口在哪里。别被那些打着“包过”旗号的机构骗了,电工证不是靠运气,是靠真本事和准备。下面我给你讲明白,从报名到… · 2026/11/17 11:12:50

电工证望江千万别踩坑,新手如何高效备考上岗
电工证望江千万别踩坑,新手如何高效备考上岗

电工证望江千万别踩坑,新手如何高效备考上岗 你是不是正被“急需特种作业证才能上岗找工作”这个问题折磨得睡不着觉?现在各行各业对电工证的需求越来越严格,特别是像你这样的 信阳浉河区房建工程从业者… · 2026/11/17 11:12:50

大城电工证在哪报名多久拿证 初次报考人员必看避坑指南
大城电工证在哪报名多久拿证 初次报考人员必看避坑指南

大城电工证在哪报名多久拿证 初次报考人员必看避坑指南 你是不是也担心自己学历不高,怕报不了名?别急,大城电工证报名其实没你想的那么难,关键是你得知道怎么操作。今天我们就从郑州金水区初次报考人员的角度,详细讲讲大城电工证在哪报名、多久拿证,以… · 2026/11/17 11:12:50

胶南这边怎么考电工证多少钱 实操考试考什么
胶南这边怎么考电工证多少钱 实操考试考什么

胶南这边怎么考电工证多少钱 实操考试考什么 工地太忙根本没时间复习考试,你是不是也这样?每天忙得连轴转,项目赶工期,培训时间又少得可怜,结果一到考试就傻眼, 多少钱… · 2026/11/17 11:12:50

长乐哪里有电工证培训怎么报名?怕考不过白交培训费?老手教你避坑
长乐哪里有电工证培训怎么报名?怕考不过白交培训费?老手教你避坑

长乐哪里有电工证培训怎么报名?怕考不过白交培训费?老手教你避坑 怕考不过白交培训费?这是很多人在找【长乐哪里有电工证培训】时最担心的事。尤其是像你这样的应届毕业生,刚进入工程行业,对电工证的考试流程、报名方式、通过率一无所知,选错了培训机构… · 2026/11/17 11:11:48

长春初级电工证怎么考?通过率揭秘全在这里
长春初级电工证怎么考?通过率揭秘全在这里

长春初级电工证怎么考?通过率揭秘全在这里 之前考的证在外省能不能转过来?这几乎是每个想从事电工工作的人都会问的问题。特别是那些在外地打拼多年、手里握着一张“外地电工证”的人,到了长春想继续干这一行,第一反应就是“我的证能用吗?”。今天我们就… · 2026/11/17 5:38:05

国内电工证报考条件与考试时间
国内电工证报考条件与考试时间

低压电工证怎么考?学历不高也能报名,官方报名入口全在这 你是不是经常听说“电工证是入行门槛”,但又担心自己学历不够、经验不足,根本报不了名?别急,今天就带你从零了解【国内电工证】的报考流程、考试内容,还有怎么在 官方报名入口… · 2026/11/17 5:38:05

电工作业时如何断电?电子证书到底能不能全国通用?
电工作业时如何断电?电子证书到底能不能全国通用?

电工作业时如何断电?电子证书到底能不能全国通用? 实操考试心里没底怕挂科,特别是电工作业时如何断电这一操作,不仅关系到你能不能拿到证书,更关系到以后能不能顺利上岗。很多人觉得这不过就是“断个电”,但其实这里面的门道可不少,稍有不慎就可能出错… · 2026/11/17 9:06:35

安徽特种工考证学校千万别踩坑,学历不高也能考证上岗
安徽特种工考证学校千万别踩坑,学历不高也能考证上岗

安徽特种工考证学校千万别踩坑,学历不高也能考证上岗 你是不是总觉得学历不高就考不了证,连报名资格都够不上?其实,很多人和你一样,学历不占优势,但想通过考证转行或提升自己的职业竞争力。安徽特种工考证学校虽然门槛不高,但千万别踩坑,稍有不慎就会… · 2026/11/17 0:00:20

你没学历也能考福田特种作业操作证?真实经历告诉你怎么干
你没学历也能考福田特种作业操作证?真实经历告诉你怎么干

你没学历也能考福田特种作业操作证?真实经历告诉你怎么干 你是不是觉得学历不高就考不上福田特种作业操作证?其实不然,我有个老乡,初中毕业,现在在安阳干焊工,每月拿8000多,还评上了高级技师。他的经历我今天就给你说说,看看你能不能照着走。… · 2026/11/17 0:00:20

低压电工证哪里盖章怎么报名 过期了别慌教你一步步复审
低压电工证哪里盖章怎么报名 过期了别慌教你一步步复审

低压电工证哪里盖章怎么报名 过期了别慌教你一步步复审 证书过期了不知道怎么复审延期?低压电工证是很多电工从业者必须持有的证件,一旦到期未及时办理复审,不仅影响工作,还可能面临被单位辞退甚至罚款。今天我就从南阳地区培训机构学员的角度,详细告诉… · 2026/11/17 0:00:20

双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试
双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/16 16:48:43

STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析
STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/16 16:48:57

DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案
DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/16 16:48:48

了解更多?预约专属演示

我们的顾问将为您一对一讲解产品与方案

企业微信二维码