前置

  • 模拟

解法

为了方便描述每个音节的长度，我们定义一个 最小单位时间，四分音符 长 \(96\) 的单位时间。

为什么是 \(96\) ？

大部分电脑音游用的 96。

\(96 = 2^5 \times 3\)，可以整除本题所有的 音符时长。

记录

我们将每个音符记为多个事件：

1
2
3
4
5
struct Event {
    ll t;     // 时间点
    int type; // 0 为 Hold 起始，1 为 Hold 结束，2 为 Tap
    int btn;  // 按键编号 
};

可以将每一时刻的事件存在一起，方便处理。

注：C++ 中 stoi 函数可以将 string 直接转为数字。

多押无理

在任意时刻，按下的按键不能大于 2。

按下的按键包括：

  1. Tap 和 Hold 的开始。

  2. 已按下的 Hold（包括刚好结束）。

直接开 bool 储存每一按键当前是否按下，再结合当前时刻的按键数累加判断。

嵌套无理

在任意时刻，同一个按键不能按下两次。

按下的按键同上。

同上，判断 bool 中当前按键是否按下，再结合当前时刻的按键判断。

每次记得更新 bool 中的状态。

上述两个无理只要有 其中之一，就为 No。

时间复杂度：\(O(T(n log n + n))\)，\(n\) 为事件总数。

代码

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
75
76
77
78
79
80
81
82
83
84
85
86
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Event {
    Event(ll t, int type, int btn) :
        t(t), type(type), btn(btn) {}
    ll t;     // 时间点
    int type; // 0 为 Hold 起始，1 为 Hold 结束，2 为 Tap
    int btn;  // 按键编号
};
const int BASE = 96; // 一拍占用的最小单位时间
int T;
int n;
string t, line;
vector<Event> events;            // 时间
vector<string> notes;            // 每个音符
map<ll, vector<Event>> timeline; // 每个时刻的事件
unordered_map<int, int> hold;    // 当前按下的按键
int main() {
    scanf("%d", &T);
    getline(cin, t);
    while (T--) {
        cin >> n;
        events.clear(), getline(cin, t);
        ll now = 0;
        for (int i = 0; i < n; ++i) {
            getline(cin, line);
            int pos = line.find('}'); // 结束位置
            int value = stoi(line.substr(1, pos - 1));
            ll unit = BASE * 4 / value; // 计算单位时间
            string body = line.substr(pos + 2), tmp;
            notes.clear();
            for (char ch : body)
                if (ch == ',')
                    notes.push_back(tmp), tmp.clear();
                else
                    tmp += ch;
            for (int i = 0; i < notes.size(); ++i) {
                ll time = now + i * unit; // 按键时间
                if (notes[i].empty()) continue;
                stringstream ss(notes[i]);
                string token;
                while (getline(ss, token, '/')) { // 以 '/' 分割音符
                    if (token.find('h') == string::npos) {
                        int btn = stoi(token);
                        events.push_back(Event(time, 2, btn));
                    } // Tap
                    else {
                        int btn = stoi(token.substr(0, token.find('h')));
                        int l = token.find('['), m = token.find(':'), r = token.find(']');
                        int value = stoi(token.substr(l + 1, m - l - 1));
                        int cnt = stoi(token.substr(m + 1, r - m - 1));
                        ll duration = (BASE * 4 / value) * cnt;           // Hold 持续时间
                        events.push_back(Event(time, 0, btn));            // Hold 起始
                        events.push_back(Event(time + duration, 1, btn)); // Hold 结束
                    } // Hold
                }
            }
            now += unit * notes.size();
        }

        timeline.clear(), hold.clear();                                                // 记得初始化
        for (auto [t, type, btn] : events) timeline[t].push_back(Event(t, type, btn)); // 储存每个时刻的事件
        bool flag = false;
        for (auto [t, event] : timeline) {
            int sum = 0;
            for (auto [k, v] : hold)
                if (v > 0) sum++; // 统计当前按下的按键数
            for (auto e : event)
                if (e.type == 2 || e.type == 0) {
                    if (hold[e.btn] > 0) flag = true; // 重复按下
                    sum++;                            // 按下按键
                }
            if (sum > 2) flag = true;
            if (flag) break;
            for (auto e : event) {
                if (e.type == 0)
                    hold[e.btn]++;
                else if (e.type == 1)
                    hold[e.btn]--;
            } // 更新按键状态
        }
        cout << (flag ? "No" : "Yes") << '\n';
    }
    return 0;
}