把 hh:mm:ss 折成秒,对 5 种乐器各开一个差分数组做区间加一,前缀和还原每秒演奏状态,询问时按 PVCDB 拼字符。
OJ: roj
题目 ID: 1994
难度:普及-
标签:差分前缀和python
创建: 2026-10-08 06:59
更新: 2026-10-08 06:59
形式化题目
乐器只有 5 种,编号顺序固定为 P、V、C、D、B。音乐会从 00:00:00 开始,
时刻 hh:mm:ss 代表从这一秒到下一秒的一整秒时间片,因此可以把它唯一地折成一个整数
由数据范围
输入给出 l r T(
- 把在
时刻演奏的所有乐器按 PVCDB顺序拼起来,字母之间不加空格; - 若一个乐器也没有,输出
None。
规模:
正解
思路
朴素做法。 最直接的写法是「每个询问扫一遍全部记录」:对询问时刻
瓶颈在哪? 慢不是因为「区间判断」这一步本身贵,而是因为我们把同样的区间
重复检查了
关键观察:时间轴极短,应当先离线预处理,再
- 区间加
次,但每次都作用在一条只有 36000 长的数轴上; - 既然值域这么小,与其用线段树,不如直接把整条数轴的状态算出来—— 一维差分数组正是为此而生。
先把区间加变成两个单点操作。 对区间 diff[l] += 1; diff[r + 1] -= 1,再做一次前缀和就能还原出每个时刻被覆盖的次数。
注意这里是闭区间:hh:mm:ss 表示「从这一秒到下一秒」的那一秒,
所以右端点
5 种乐器就是 5 条独立的数轴。 每条差分数组只记录一种乐器的覆盖次数,
互不干扰。前缀和还原后,cover[k][t] > 0 就表示乐器 > 0 而不是 == 1——题面提示「两位朋友提供的资料可能会出现重叠」,
同一乐器同一秒可能被多条记录覆盖,计数会大于 1。
单次询问 cover[k][q],把大于 0 的乐器字母追加到结果里。因为 P, V, C, D, B,拼出来的字符串天然满足题目要求的 PVCDB 顺序。
一个都没有命中时输出 None。
以样例为例:把 5 条记录折成秒分别是 [2,5]P、[9,9]V、[4,7]P、[1,2]V、[5,6]V。
在差分上做完前缀和后,PV),
P),PV。
Python 版与 C++ 版是同一个算法:C++ 用 int diff[5][36005] 做差分 + 前缀和,
Python 用 5 行 list + itertools.accumulate,只是把「每一秒的 5 个计数」
进一步压成一个 5 位的整数掩码 mask[t],把询问阶段的 5 次判断缩成一次按位扫描。
代码
Python 版:
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-08 06:59
# update_at: 2026-10-08 06:59
import sys
from itertools import accumulate
NAME = "PVCDB" # 输出优先级顺序;位 i(i 从 0 起)对应 NAME[i] 这件乐器
MAXT = 9 * 3600 + 59 * 60 + 59 # 题目给的 hh<=9,最大秒 35999,时间轴只有 36000 秒
LEN = MAXT + 2 # 差分要在 r+1<=36000 处减一,故多留两格
# 类型别名(Python 3.12+ 的 type 语句),相当于 C++ 的 using / typedef
type DiffTable = list[list[int]] # 每件乐器一条差分数组,行下标 = 乐器编号
def to_sec(token: str) -> int:
"""把 hh:mm:ss 折成绝对秒,即 3600*hh + 60*mm + ss。"""
hh, mm, ss = token.split(':')
return int(hh) * 3600 + int(mm) * 60 + int(ss)
def build_mask(diff: DiffTable) -> list[int]:
"""差分数组求前缀和,还原成"每一秒的乐器掩码":位 i 为 1 表示该秒有 NAME[i] 在响。"""
mask = [0] * LEN
for instrument, row in enumerate(diff):
bit = 1 << instrument
for t, cover in enumerate(accumulate(row)): # cover = 该秒被多少条记录覆盖
if cover > 0: # 多条记录重叠,只要非零就算在演奏
mask[t] |= bit
return mask
def render(mask: int) -> str:
"""把某一秒的掩码渲染成一行答案:按 PVCDB 顺序拼字母,无人演奏则 None。"""
return ''.join(ch for i, ch in enumerate(NAME) if mask >> i & 1) or "None"
def solve() -> None:
tokens = iter(sys.stdin.buffer.read().decode().split())
n = int(next(tokens))
diff: DiffTable = [[0] * LEN for _ in range(5)]
for _ in range(n):
left = to_sec(next(tokens))
right = to_sec(next(tokens))
instrument = NAME.index(next(tokens))
diff[instrument][left] += 1 # 闭区间 [left, right] 区间加一
diff[instrument][right + 1] -= 1
mask = build_mask(diff)
m = int(next(tokens))
times = [to_sec(next(tokens)) for _ in range(m)]
print('\n'.join(render(mask[t]) for t in times))
if __name__ == "__main__":
solve()C++ 版(同一算法):
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-08 06:59
* update_at: 2026-10-08 06:59
*
* 1994《音乐会》:n 条闭区间演奏记录(5 种乐器)+ m 次单点询问,
* 每种乐器一个差分数组,区间加 1 后前缀和还原,单点询问 O(1) 拼出 PVCDB。
* 时间折成秒:t = 3600*hh + 60*mm + ss,由 0<=hh<=9 知 t 最大 35999。
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXT = 36000; // 秒 0..35999,差分还要用 t = 36000 这一格
const int MAXN = 20005;
int diff[5][MAXT + 5]; // 每种乐器的差分数组,下标 0..36000
int state[5][MAXT + 5]; // 前缀和还原后:该秒该乐器是否在演奏(>0 即演奏)
const char* name = "PVCDB"; // 输出优先级顺序
/**
* hh:mm:ss 折成绝对秒。
*/
int to_sec(int hh, int mm, int ss) {
return hh * 3600 + mm * 60 + ss;
}
/**
* 读入一个 hh:mm:ss 时间串并折成秒,冒号交给 scanf 吞掉。
*/
int read_time() {
int hh, mm, ss;
scanf("%d:%d:%d", &hh, &mm, &ss);
return to_sec(hh, mm, ss);
}
/**
* 乐器字母映射成 0..4 的下标,顺序与 name 一致。
*/
int to_id(char c) {
for (int i = 0; i < 5; ++i) {
if (name[i] == c) return i;
}
return -1;
}
int main() {
ll n = 0, m = 0;
scanf("%lld", &n);
char op[8];
for (ll i = 0; i < n; ++i) {
int l = read_time();
int r = read_time();
scanf("%s", op);
int id = to_id(op[0]);
if (id < 0) continue;
// 闭区间 [l, r]:l 处 +1,r+1 处 -1;r 最大 35999,故差分开到 36000。
diff[id][l] += 1;
diff[id][r + 1] -= 1;
}
// 对每种乐器求前缀和,得到每个秒时刻的覆盖层数
for (int id = 0; id < 5; ++id) {
int cur = 0;
for (int t = 0; t <= MAXT; ++t) {
cur += diff[id][t];
state[id][t] = cur;
}
}
scanf("%lld", &m);
for (ll i = 0; i < m; ++i) {
int t = read_time();
int cnt = 0; // 本时刻演奏中的乐器数
for (int id = 0; id < 5; ++id) {
if (state[id][t] > 0) {
putchar(name[id]);
++cnt;
}
}
if (cnt == 0) printf("None"); // 一个乐器都没有
putchar('\n');
}
return 0;
}复杂度
- 时间:读入并打差分标记
;对 5 种乐器各做一遍长度 36000 的前缀和, 即 ;回答询问 (每次 5 次比较)。 总计 , 、 时 计算量约 次操作,实测 1 ms 量级(限时 1000 ms)。 - 空间:
个 int,约 720 KB;Python 版多存一份掩码数组。 两者都远低于 256 MB 限制。 - 与 C++ 解法的关系:
main.cpp用二维差分数组 + 二维前缀和,Python 版把 「同一秒的 5 个覆盖计数」压成掩码,复杂度同阶且都是, 不存在 Python 特有的 TLE 风险。
总结
- 先看值域,再选数据结构:
把时间轴压到 36000 个点, 这是本题从「离散化 + 线段树」降到「差分 + 前缀和」的唯一原因。 「区间加、单点查」在值域小时不需要任何树。 - 闭区间的差分要落在
:题面的 hh:mm:ss表示整整一秒,右端点必须算进去; 同时差分数组要预留一格承接时的 。 次询问共用一次预处理:把 次重复的区间判断换成一次离线前缀和, 是 的关键一步。 - 输出顺序来自乐器编号本身:把编号顺序取成
PVCDB之后,顺序要求就不需要任何 额外排序逻辑,直接按编号从小到大拼接即可。 - 计数用
> 0判断:题面明确提示资料可能重叠,同一乐器同一秒可能被多次覆盖。
说明
- 本题题面与数据均为仓库内重建:素材源目录带有
data.py生成脚本,data/的 10 个测试点由该脚本自造,题面参考自公开博客 (https://www.cnblogs.com/lyc-lb-blogs/p/14969873.html 等)。 因此本题的「官方判题意图」可能与原书存在偏差,上述分析以题面与重建数据为准。 std.cpp与本分析采用同一算法(5 条差分数组 + 前缀和), 已用真实数据编译核对,10 个点全部一致,未发现该标程与题面不符。