企业官网建设流程全解析

题目描述

在西方音乐中，记谱法使用的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个音符组成，从某个音符开始，按照全-全-半-全-全-全-半的规律从左到右选取，必要时循环回开头。大调音阶必须满足以下两条规则：

1. 音阶中字母A到G每个恰好出现一次，首字母在结尾重复一次。
2. 音阶中不能同时包含升号和降号。

开始音阶的音符称为该音阶的调性（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

题目分析

本题的核心是：给定源调和目标调，判断它们是否构成合法的大调音阶，若是，则将源调音阶中的音符按位置映射到目标调音阶。

问题的难点在于：

1. 音符的多种记法：同一音高可能有不同名称（如C#与Db），需要在输入和输出时正确识别和转换。
2. 大调音阶的合法性判定：一个调性是否合法，取决于以其起始的音阶能否满足“每个字母恰好出现一次”且“不混用升降号”。
3. 音阶的生成规则：必须严格按照全-全-半-全-全-全-半的音程生成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 B
• F#大调：F# G# A# B C# D# E#
• Db大调：Db Eb F Gb Ab Bb C

注意音阶只存储777个不同字母的音符（首音不重复存储），因为位置映射只需要前777个位置。

算法的核心步骤

1. 预处理：建立从调性名称到其音阶（777个音符的数组）的映射表。
2. 输入解析：逐行读取，分离源调、目标调和待转换音符列表。
3. 有效性检查：通过查表判断源调和目标调是否存在于映射表中。
4. 音符合法性检查与转调：
   • 若源调或目标调无效，输出错误信息并跳过。
   • 否则，对于每个待转换音符，在源调的音阶中查找其位置（下标）。
   • 若位置有效（即音符属于源调音阶），则取目标调音阶中相同位置的音符作为转换结果；否则输出“不是有效音符”的信息。

正确性说明

• 手工构造的音阶均满足大调音阶的两条规则，因此查表法可准确判断调性合法性。
• 音符的查找通过比较字符串即可完成，无需考虑等音问题，因为音阶中的音符名称是确定的。
• 输出格式严格按照题目要求：首行无缩进，后续行缩进两个空格，行间空行。

复杂度分析

• 预处理：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#include<bits/stdc++.h>usingnamespacestd;map<string,vector<string>>scales;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;boolfirstCase=true;while(getline(cin,line)){if(line=="*")break;stringstreamss(line);string srcKey,dstKey;ss>>srcKey>>dstKey;vector<string>notes;string note;while(ss>>note&&note!="*")notes.push_back(note);if(!firstCase)cout<<"\n";firstCase=false;boolsrcValid=scales.count(srcKey),dstValid=scales.count(dstKey);if(!srcValid||!dstValid){if(!srcValid)cout<<"Key of "<<srcKey<<" is not a valid major key\n";elsecout<<"Key of "<<dstKey<<" is not a valid major key\n";continue;}vector<string>&src=scales[srcKey],dst=scales[dstKey];cout<<"Transposing from "<<srcKey<<" to "<<dstKey<<":\n";for(conststring&m:notes){cout<<" "<<m;intidx=find(src.begin(),src.end(),m)-src.begin();if(idx>=src.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分别是独立的合法调性，不可混用）。
• 输入行末尾的星号需要正确解析并跳过。

通过本题可以体会到：在规则明确、状态有限的问题中，手动枚举 + 查表往往比复杂的动态构造更可靠、更易实现。