UVa 1005 A Major Problem
题目描述在西方音乐中记谱法使用的121212个音符用大写字母A到G表示后面可能跟随升号#或降号b。所有音符按半音阶排列如下C/B# C#/Db D D#/Eb E/Fb F/E# F#/Gb G G#/Ab A A#/Bb B/Cb其中斜线表示同一音符的不同记法。任意两个相邻音符相差一个半音中间隔一个音符则相差一个全音。一个大调音阶由888个音符组成从某个音符开始按照全-全-半-全-全-全-半的规律从左到右选取必要时循环回开头。大调音阶必须满足以下两条规则音阶中字母A到G每个恰好出现一次首字母在结尾重复一次。音阶中不能同时包含升号和降号。开始音阶的音符称为该音阶的调性key\texttt{key}key。将一个音阶中的音符转换到另一个音阶只需将音符替换为另一个音阶中相同位置的音符。本题要求给定若干行输入每行包含源调、目标调以及若干待转换音符输出转换结果并指出无效的调性或音符。输入格式输入包含若干行除最后一行外每行包含两个音乐调性如C、Db后跟若干个待转换音符最后以单个星号*结束。所有音符与星号之间由单个空格分隔。最后一行仅包含一个星号*表示输入结束。输出格式对于每个定义转调问题的输入行输出如下如果源调和目标调均有效第一行输出Transposing from X to Y:其中XXX为源调YYY为目标调。如果任一调性无效输出一行Key of K is not a valid major key其中KKK为无效的调性。若两者均无效仅报告源调并跳过该行剩余音符。对于源调和目标调均有效的输入行其后为每个待转换音符输出一行若音符在源调音阶中有效输出M transposes to N其中MMM为原音符NNN为转换后的音符。若音符无效输出M is not a valid note in the X major scale其中XXX为源调。每个输入行的输出数据之间打印一个空行。每行输出包括有效时的第一行的开头没有额外空格无效或转换行开头有恰好两个空格。样例输入C Db F * Db C Gb * C B# A B * C D A A# B Bb C * A# Bb C * *输出Transposing from C to Db: F transposes to Gb Transposing from Db to C: Gb transposes to F Key of B# is not a valid major key Transposing from C to D: A transposes to B A# is not a valid note in the C major scale B transposes to C# Bb is not a valid note in the C major scale C transposes to D Key of A# is not a valid major key题目分析本题的核心是给定源调和目标调判断它们是否构成合法的大调音阶若是则将源调音阶中的音符按位置映射到目标调音阶。问题的难点在于音符的多种记法同一音高可能有不同名称如C#与Db需要在输入和输出时正确识别和转换。大调音阶的合法性判定一个调性是否合法取决于以其起始的音阶能否满足“每个字母恰好出现一次”且“不混用升降号”。音阶的生成规则必须严格按照全-全-半-全-全-全-半的音程生成888个音高再为每个音高选择符合规则的名称。直接对每个输入动态生成音阶并进行回溯选择是可行的但实现较复杂。注意到有效的大调调性是有限且已知的我们可以预先手动构造所有合法的大调音阶然后通过查表快速处理每个输入。解题思路有效大调调性的枚举根据音阶构造规则可以枚举出所有合法的大调调性。它们分为两组升号调C、G、D、A、E、B、F#、C#降号调F、Bb、Eb、Ab、Db、Gb、Cb共计151515个不同的调性名称C#和Db音高相同但名称不同均视为合法。每个调性对应的音阶可以通过手工推导得到。例如C大调C D E F G A BF#大调F# G# A# B C# D# E#Db大调Db Eb F Gb Ab Bb C注意音阶只存储777个不同字母的音符首音不重复存储因为位置映射只需要前777个位置。算法的核心步骤预处理建立从调性名称到其音阶777个音符的数组的映射表。输入解析逐行读取分离源调、目标调和待转换音符列表。有效性检查通过查表判断源调和目标调是否存在于映射表中。音符合法性检查与转调若源调或目标调无效输出错误信息并跳过。否则对于每个待转换音符在源调的音阶中查找其位置下标。若位置有效即音符属于源调音阶则取目标调音阶中相同位置的音符作为转换结果否则输出“不是有效音符”的信息。正确性说明手工构造的音阶均满足大调音阶的两条规则因此查表法可准确判断调性合法性。音符的查找通过比较字符串即可完成无需考虑等音问题因为音阶中的音符名称是确定的。输出格式严格按照题目要求首行无缩进后续行缩进两个空格行间空行。复杂度分析预处理O(1)O(1)O(1)常数个调性。每个输入行设待转换音符个数为mmm查找音符在音阶中的位置需O(7)O(7)O(7)时间因此单行处理时间为O(m)O(m)O(m)。总时间复杂度O(∑m)O(\sum m)O(∑m)完全满足题目要求。空间复杂度O(1)O(1)O(1)存储151515个音阶。代码实现注本题与UVa 595 A Major Problem\texttt{UVa 595 A Major Problem}UVa 595 A Major Problem为重复题目。// A Major Problem// UVa ID: 1005// Verdict: Accepted// Submission Date: 2026-07-25// UVa Run Time: 0.010s// https://blog.csdn.net/metaphysis/article/details/163184828#includebits/stdc.husingnamespacestd;mapstring,vectorstringscales;voidtrick(){scales[C]{C,D,E,F,G,A,B};scales[C#]{C#,D#,E#,F#,G#,A#,B#};scales[Db]{Db,Eb,F,Gb,Ab,Bb,C};scales[D]{D,E,F#,G,A,B,C#};scales[Eb]{Eb,F,G,Ab,Bb,C,D};scales[E]{E,F#,G#,A,B,C#,D#};scales[F]{F,G,A,Bb,C,D,E};scales[F#]{F#,G#,A#,B,C#,D#,E#};scales[Gb]{Gb,Ab,Bb,Cb,Db,Eb,F};scales[G]{G,A,B,C,D,E,F#};scales[Ab]{Ab,Bb,C,Db,Eb,F,G};scales[A]{A,B,C#,D,E,F#,G#};scales[Bb]{Bb,C,D,Eb,F,G,A};scales[B]{B,C#,D#,E,F#,G#,A#};scales[Cb]{Cb,Db,Eb,Fb,Gb,Ab,Bb};}intmain(){trick();string line;boolfirstCasetrue;while(getline(cin,line)){if(line*)break;stringstreamss(line);string srcKey,dstKey;sssrcKeydstKey;vectorstringnotes;string note;while(ssnotenote!*)notes.push_back(note);if(!firstCase)cout\n;firstCasefalse;boolsrcValidscales.count(srcKey),dstValidscales.count(dstKey);if(!srcValid||!dstValid){if(!srcValid)coutKey of srcKey is not a valid major key\n;elsecoutKey of dstKey is not a valid major key\n;continue;}vectorstringsrcscales[srcKey],dstscales[dstKey];coutTransposing from srcKey to dstKey:\n;for(conststringm:notes){cout m;intidxfind(src.begin(),src.end(),m)-src.begin();if(idxsrc.size())cout is not a valid note in the srcKey major scale\n;elsecout transposes to dst[idx]\n;}}return0;}总结本题的核心在于有限状态空间的预计算。通过分析大调音阶的构造规则可以提前枚举出所有合法的调性及其音阶从而将问题简化为查表与字符串匹配。关键技巧手工推导并固定所有有效调性的音阶避免了动态生成带来的复杂性和潜在错误。利用map\texttt{map}map建立调性到音阶的映射实现O(1)O(1)O(1)查找。使用find\texttt{find}find在音阶数组中定位音符位置代码简洁且正确性高。注意事项输出格式要求严格行首空格和空行必须精确。注意处理等音情况如C#和Db分别是独立的合法调性不可混用。输入行末尾的星号需要正确解析并跳过。通过本题可以体会到在规则明确、状态有限的问题中手动枚举 查表往往比复杂的动态构造更可靠、更易实现。

相关新闻

金融科技中的高效行情数据处理:stock-sdk-mcp技术解析

金融科技中的高效行情数据处理:stock-sdk-mcp技术解析

1. stock-sdk-mcp 技术方案解析在金融科技领域,行情数据的高效处理一直是量化交易和投资分析系统的核心需求。stock-sdk-mcp 作为一套专业级市场数据采集与处理框架,其设计理念源于对证券行业数据特性的深度理解。这个方案最显著的特点是采用多通道并行&…

2026/11/2 9:13:31 阅读更多 →
健康管理的基础定义

健康管理的基础定义

健康管理的基础定义健康管理是近年来受到不少人关注的健康服务品类,主要是围绕普通人群的日常健康生活相关需求,提供对应的配套服务内容。健康管理的常见服务方向当前市面上的健康管理相关服务覆盖多个不同的方向,大家可以根据自身的日常健康…

2026/11/16 21:25:18 阅读更多 →
C/C++文件操作进阶:从基础API到健壮架构设计的实践指南

C/C++文件操作进阶:从基础API到健壮架构设计的实践指南

1. 项目概述:从文件操作到架构思维的跨越最近在社区里看到不少朋友在讨论C/C的文件操作,尤其是遇到一些像“页面文件太小”或者“文件被占用无法删除”这类让人头疼的运行时错误。这让我想起自己刚入行那会儿,也是埋头写读写文件的代码&#…

2026/11/15 13:31:18 阅读更多 →

最新新闻

Electron桌面应用开发实战:从环境搭建到打包发布全流程

Electron桌面应用开发实战:从环境搭建到打包发布全流程

做前端这些年,我大部分时间都在跟浏览器标签页打交道,直到第一次把桌面应用跑起来,才发现原来自己一直被限制在地址栏和刷新按钮围起来的框框里。Electron这个词,最开始是在某段时间频繁出现在同事的讨论里,一个用HTML…

2026/11/17 8:22:52 阅读更多 →
滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

简介:亚太天能T109滑盖智能锁产品说明书是一份PDF格式的官方技术文档,主要面向智能锁安装人员、终端用户及售后维护者,帮助快速掌握产品安装、配置与常见故障处理。全包仅1个PDF文件,大小4.37MB,内容结构清晰&#xff…

2026/11/17 12:46:04 阅读更多 →
PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

上个月我在调试一台高速AGV的驱动系统,整车要求空载跑到8m/s,电机转速已经拉到额定点,驱动器的输出电压也顶到了母线电压极限附近。再往上踩速度指令,转速纹丝不动,三相电流反而开始震荡。那会儿我的第一反应就是&…

2026/11/17 12:46:04 阅读更多 →
C++核心知识点:从内存管理到STL的实战指南

C++核心知识点:从内存管理到STL的实战指南

C 这门语言我前前后后折腾了十几年,用它写过嵌入式驱动、做过游戏服务端,也搭过基础组件库。每次看到新人一头扎进"C 核心知识点"这个搜索词,我其实挺感慨的——这门语言的难点从来不是语法多,而是知识点之间的耦合太深…

2026/11/17 11:26:33 阅读更多 →
T109滑盖智能锁怎么装?安装调试与故障排查全攻略

T109滑盖智能锁怎么装?安装调试与故障排查全攻略

简介:亚太天能T109滑盖智能锁产品说明书以PDF格式发布,适合智能锁用户、安装人员与售后维修人员阅读。内容围绕T109系列指纹密码刷卡锁展开,先介绍前面板、后面板、锁体、机械钥匙、电池盒盖等部件名称与功能,再给出完整安装步骤&…

2026/11/17 12:46:05 阅读更多 →
LLM知识降熵:从信息垄断到理解权下放

LLM知识降熵:从信息垄断到理解权下放

你有没有过这种经历:翻开源码注释、论文摘要或者一份专业报告,每个字都认识,连在一起却像天书。想找人聊聊,身边要么没人懂,要么懂的懒得跟你解释。后来我试着把同一段内容丢给一个大语言模型,几秒钟之后&a…

2026/11/17 12:46:05 阅读更多 →

日新闻

周新闻

月新闻