UVa 595 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个音阶。代码实现// A Major Problem// UVa ID: 595// Verdict: Accepted// Submission Date: 2026-06-04// UVa Run Time: 0.010s//// 版权所有C2026邱秋。metaphysis # yeah dot net#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分别是独立的合法调性不可混用。输入行末尾的星号需要正确解析并跳过。通过本题可以体会到在规则明确、状态有限的问题中手动枚举 查表往往比复杂的动态构造更可靠、更易实现。