一、题目来源题目名称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
一、题目来源题目名称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
