Problem Solving►UVa

UVa 10528 - Major Scales

Contents

  1. 1. Problem
  2. 2. Solution
  3. 3. Code

Problem

題目網址
中文網址

大致上就是主旋律有好幾種調(e.g. C, D,…)，而每種調會包含共 8 個音符：起始、全全半全全全半。
給出一句弦律，要判斷他可能是哪種調。

Solution

題目有夠難懂啊…

由於不需要去管音符出現的順序，只要該句弦律 沒出現 某調所沒有的 音符，那他就有可能是該調。
(測資應是沒有空字串)

Code

UVa 10528
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <cstdio>
#include <unordered_map>
#include <string>
#define N 12
using namespace std;

int main()
{
    const string S[N] = {"C", "C#", "D", "D#", "E", "F", "F#", "G", "G#", "A", "A#", "B"};
    const int step[7] = {2, 2, 1, 2, 2, 2, 1};

    //Map string to idx
    unordered_map<string, int> M;
    for (int i = 0; i < N; ++i)
        M[S[i]] = i;

    //甚麼調有用到那些音符
    bool scale_used[N][N] = {};
    for (int i = 0; i < N; ++i) //12種調，不同的開頭
    {
        scale_used[i][i] = true;
        for (int j = 0, k = i; j < 7; ++j) //7個step中有出現過那些音符
        {
            k = (k + step[j]) % N;
            scale_used[i][k] = true;
        }
    }

    char str[1005];
    while (fgets(str, 1005, stdin) && str[1] != 'N')
    {
        char tone[5];
        bool used[N] = {};
        bool first = true;

        //該段弦律中有出現那些音符
        for (int i = 0, idx = 0; str[i]; ++i)
        {
            if (str[i] == ' ' || str[i] == '\n')
            {
                tone[idx] = '\0';
                used[M[string(tone)]] = true;
                idx = 0;
            }
            else
                tone[idx++] = str[i];
        }

        for (int i = 0; i < N; ++i)
        {
            bool flag = true;
            for (int k = 0; k < N; ++k)
                if (used[k] && !scale_used[i][k]) //該音符在調中未出現，不可能是該調
                {
                    flag = false;
                    break;
                }

            if (flag)
            {
                if (!first)
                    putchar(' ');
                else
                    first = false;

                printf("%s", S[i].c_str());
            }
        }

        putchar('\n');
    }

    return 0;
}