形式化题目

五个轮子，第 $k$ 个以 $v_k$ 度/秒匀速转动。轮子上有若干缺口，一个起始角度为 $s$、张角为 $len$ 的缺口在时刻 $t$ 覆盖角度

记轮子 $k$ 在时刻 $t$ 被缺口盖住的角度集合为 $C_k(t)$。求最小的整数 $t \geqslant 0$， 使

即存在某个角度被五个轮子的缺口同时盖住（光可以从这个角度穿过去）。若不存在这样的 $t$， 输出 none。

约束：$1 \leqslant v_k \leqslant 180$，$1 \leqslant W_k \leqslant 5$， $0 \leqslant s \leqslant 359$；同一个轮子上任意两个缺口之间至少间隔 1 度。 角度是 $[0, 359]$ 内的整数，时间也按整数秒计。

易错点：张角按闭区间理解。 张角 $len$ 覆盖 $[s, s+len]$，共 $len + 1$ 个角度。 题面样例与全部测试数据都只在这一约定下成立：若误当成半开区间 $[s, s+len)$（即 $len$ 个角度），样例的答案会算成 none 而不是 $9$。后文实现按闭区间处理。

正解

思路

朴素做法

最直接的办法是从 $t = 0$ 开始逐个时刻试：对每个时刻 $t$，再枚举角度 $d = 0, 1, \dots, 359$，检查五个轮子在角度 $d$ 处是否都落在某个缺口里；第一个成功的 $t$ 就是答案。

单个"轮子 $k$ 在角度 $d$ 处是否有缺口"的判断要遍历它的 $W_k$ 个缺口。一次完整检查约 $360 \times 360 \times \sum W_k$ 次基本操作，规模不大，但朴素写法有一个致命的缺口： 枚举上界是什么？ 题目没有给时间上限，如果无解，程序会永远转下去。

第一步：证明只需枚举 360 秒

关键观察是轮子在时刻 $t$ 的缺口位置只依赖一个量。轮子 $k$ 上缺口 $(s, len)$ 在时刻 $t$ 的起点是 $(s + v_k t) \bmod 360$，把整体旋转的角度记作

于是一个轮子在某一时刻的全部挡光位置，完全由 $r_k(t)$ 决定：缺口形状不变，只是整体挪了 $r_k(t)$ 度。而

因为 $360 v_k$ 是 360 的倍数，对模 360 没有影响。五个轮子同时成立，所以

整体挡光图案以 360 秒为周期。 由此得到两件事：

• 只需枚举 $t = 0, 1, \dots, 359$ 这一整圈，就穷尽了所有可能出现的图案；
• 如果这 360 个时刻全都没有公共角度，那么任意 $t \geqslant 360$ 都可以写成 $t' + 360m$（$t' < 360$），图案与 $t'$ 完全相同，同样不会成功。

于是"要么答案在 $[0, 359]$ 内，要么无解"，无限枚举变成了至多 360 次判定，无解也有了 可靠的出口。

不能用更小的周期省事。单个轮子的周期是 $360 / \gcd(v_k, 360)$，但五个轮子要同时 回到原位，取的是它们的最小公倍数，最坏仍然是 360。统一用 360 既正确又省去讨论。

第二步：把 360 个角度压成一个整数

朴素写法每次判断都要在角度上循环。注意到角度恰好只有 360 个整数，可以整体装进一个 Python 大整数里，让"求交"变成一次按位与：

rot_left(mask, k) 就是环上左移：(mask << k | mask >> (360 - k)) & MASK。缺口卷过 0 度时不需要特判，回绕由这次移位自动完成。

两个实现上的好处：

• 旋转只做一次。缺口张角不随时间变化，整轮旋转是统一位移，所以可以先在 $t = 0$ 把 所有缺口的连续段合并成一个掩码，最后整体旋转 $v_k t$ 位，不必对每个缺口单独取模。
• 求交是 $O(1)$。五个轮子的掩码按位与即可，位数固定 360，与数据规模无关；一旦中间 结果变成 0 就能提前结束这一秒。

样例演示

以 spin4（答案 $1$）为例。输入是

1
2
3
4
545 5 140 13 300 17 0 15 20 3 40 1
73 1 200 359
105 2 4 1 50 50
179 3 6 1 8 1 359 3
3 1 300 300

下表列出每个轮子在 $t = 0$ 与 $t = 1$ 时被缺口覆盖的角度区间。第一列是转速，区间按 闭区间书写（例如 140 13 覆盖 $140 \sim 153$ 共 14 个角度）。

读表要点：

• $t = 0$ 时五个区间集合没有共同角度，例如转速 179 的轮子只在 6–9 与 359–2 处有缺口， 而转速 105 的轮子在 4–5 与 50–100 处有缺口，两者只在 4–5 与 6–9 之间相邻却不相交。 所以 $t = 0$ 判定失败。
• $t = 1$ 时转速 45 的轮子转到 185–198，转速 179 的轮子转到 178–188，两者在 185–188 处重叠；同时 185–188 落在转速 73 的整圈缺口与转速 3 的 303–359+0–243 内。 但转速 105 在这一秒的缺口是 109–110 与 155–205——155–205 也包含 185–188。五个集合的 交集为 $\{185, 186, 187, 188\}$，非空，所以答案是 $1$。
• 这正是位掩码在代码里做的事：五个掩码按位与得到一串 1，最低的那一段对应的就是上表的 185–188。答案取的是时间 $t$ 而不是角度，所以输出 $1$。

边界处理

• 张角为 0：如 spin4 里的 40 1。闭区间 $[40, 40]$ 覆盖 1 个角度，段长是 $0 + 1 = 1$。若按半开区间实现会得到空集合，把有解误判成无解。
• 张角为 359：段长 $359 + 1 = 360$，覆盖全部角度。代码里对 width >= 360 直接返回 全 1 掩码，避免构造 $1 \ll 360$ 这种边界移位。
• 无解：恰好枚举 360 次后退出并输出 none。

代码

Python 版：

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#!/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-01 05:07
# update_at: 2026-10-01 05:07

import sys
from itertools import count

DEG = 360              # 角度取模的模数：转过 359 度后回到 0
MASK = (1 << DEG) - 1  # 360 个角度全为 1 的掩码，用作"所有角度都能对准"的起点
N_WHEELS = 5           # 纺轮个数，透光要求五个轮子在同一角度同时存在缺口


def rot_left(mask: int, k: int) -> int:
    """把 360 位的角度集合在环上整体左移 k 位（k 度），这就是轮子旋转的语义。"""
    k %= DEG
    return (mask << k | mask >> (DEG - k)) & MASK


def run(s: int, length: int) -> int:
    """把缺口 [s, s+length] 写成一个 360 位掩码：落在缺口里的角度对应位为 1。

    题面的长度按闭区间算，缺口含首尾共 length+1 个角度，所以连续 1 的段长是
    length+1；段长到 360 说明缺口绕满整圈，此时每个角度都在缺口里。
    """
    width = length + 1
    if width >= DEG:
        return MASK
    head = (1 << width) - 1  # 从 0 度开始、长 width 的一段 1
    return rot_left(head, s)


def notch_mask(speed: int, notches: list[list[int]], t: int) -> int:
    """第 t 秒这个轮子上的缺口盖住的角度集合。

    每个缺口先铺好自己的连续段，最后整轮一起转过 speed*t 度——旋转对所有缺口
    是同一个位移，挪一次等于逐个挪，省掉 W 次旋转。
    """
    mask = 0
    for s, length in notches:
        mask |= run(s, length)
    return rot_left(mask, speed * t)


def collide(wheels: list[tuple[int, list[list[int]]]]) -> int:
    """最早能让光穿过的秒数，无解返回 -1。

    光走直线，所以可用的角度 d 必须同时落在五个轮子的某个缺口里，即五个轮子的
    缺口集合取交集后非空；交集为空就说明这一秒五个缺口排不到同一条线上。

    时间 t 的整体图案只由五个 (speed*t) mod 360 决定，而 0..359 秒已经穷尽了这
    五个余数的所有组合，因此 t 与 t+360 的图案必然相同；没在一圈内出现过的图案
    永远不会出现，枚举满 360 秒即可判定无解。
    """
    for t in count():  # 无限计数，只取前 360 个时刻
        if t == DEG:
            return -1  # 一整圈都试过了
        common = MASK
        for speed, notches in wheels:
            common &= notch_mask(speed, notches, t)
            if not common:
                break  # 已经排不到同一条线，这个秒数不必再算剩下的轮子
        if common:
            return t


def solve() -> None:
    data = list(map(int, sys.stdin.buffer.read().split()))
    wheels: list[tuple[int, list[list[int]]]] = []
    pos = 0
    for _ in range(N_WHEELS):
        speed, surplus = data[pos], data[pos + 1]  # 转速、缺口数 W
        pos += 2
        notches = [[data[pos + 2 * i], data[pos + 2 * i + 1]] for i in range(surplus)]
        wheels.append((speed, notches))
        pos += 2 * surplus

    ans = collide(wheels)
    print("none" if ans < 0 else ans)  # -1 表示转满一圈都没有能对准的时刻


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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/**
 * 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-06 09:47
 * update_at: 2026-10-06 09:47
 */
#include <iostream>
using namespace std;

// 五个轮子共用这些全局数组：ns[k][j] 是轮 k 第 j 个缺口的起始角度，nl[k][j] 是张角
const int DEG = 360; // 角度模数：转过 359 度后回到 0 度
int v[5];            // v[k]：轮 k 的转速（度/秒）
int w[5];            // w[k]：轮 k 的缺口个数
int ns[5][5];        // 缺口起始角度
int nl[5][5];        // 缺口张角（闭区间，覆盖 len+1 个角度）

// 判断轮子 id 在时刻 t、角度 d 处是否被某个缺口盖住
bool covered(int id, int t, int d) {
    for (int j = 0; j < w[id]; ++j) {
        // 缺口在时刻 t 的起点：整体转过 v*t 度再取模
        int start = (ns[id][j] + v[id] * t) % DEG;
        // d 相对缺口起点沿转动方向的偏移，落在 [0, len] 内即被盖住（闭区间）
        int diff = (d - start + DEG) % DEG;
        if (diff <= nl[id][j]) return true;
    }
    return false;
}

int main() {
    // 读入五个轮子：转速、缺口数、每个缺口的起始角度和张角
    for (int k = 0; k < 5; ++k) {
        cin >> v[k] >> w[k];
        for (int j = 0; j < w[k]; ++j) cin >> ns[k][j] >> nl[k][j];
    }
    // 轮子在时刻 t 的图案只由 v*t mod 360 决定，整体图案以 360 秒为周期，
    // 所以只枚举 t = 0..359；一圈都没有公共角度就是无解
    for (int t = 0; t < DEG; ++t) {
        for (int d = 0; d < DEG; ++d) {
            bool ok = true;
            // 检查五个轮子在角度 d 处是否都有缺口（光能否穿过）
            for (int k = 0; k < 5; ++k) {
                if (!covered(k, t, d)) {
                    ok = false;
                    break;
                }
            }
            if (ok) {
                cout << t << endl;
                return 0;
            }
        }
    }
    cout << "none" << endl;
    return 0;
}

复杂度

设五个轮子的缺口总数 $W_{\text{tot}} = \sum_k W_k \leqslant 25$。

• 时间复杂度：每个时刻每个轮子铺 $O(W_k)$ 个连续段并做一次环上移位，五轮求交是常数次 定长（360 位）按位与；时间从 $0$ 枚举到 $359$，共 360 次。总时间 $O(360 \times W_{\text{tot}}) = O(1)$。
• 空间复杂度：$O(W_{\text{tot}}) = O(1)$，只存五个轮子的转速与缺口列表，外加一个 360 位的临时整数。

对比朴素实现（每个 $t$ 对每个 $d$ 扫每个缺口）的 $O(360 \times 360 \times W_{\text{tot}})$， 位掩码把整个角度维压进了大整数的二进制表示中，消掉了那个 360 因子。

实测单次运行约 $0.018$ 秒、峰值内存约 $14.8$ MB，远低于本题 $1000$ ms / $128$ MB 的限制。

图示解析

下图把"五个轮子能否排成一条线"的判定过程画成流程，标出每一步对应的代码函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22输入五行 (v, W, (s,len)×W)
        │
        ▼
  run(s, len)            ── 一个缺口 → 从 s 开始的 len+1 个连续 1
        │
        ▼
 notch_mask(v,notches,t) ── 合并该轮所有缺口，再环上左移 v*t 位
        │
        ▼
  common = MASK                            ← 单位元：所有角度先假定可用
  for 每个轮子: common &= notch_mask(...)   ← 按位与 = 集合求交
        │            └── 若 common == 0 → 提前结束这一秒
        ▼
  common != 0 ?  ──是──▶ 输出 t（最小可行时刻）
        │
        否
        ▼
   t == 360 ?  ──否──▶ t += 1，回到求交
        │
        是
        ▼
   输出 none（图案以 360 为周期，一圈落空则永远落空）

图中最关键的一步是中间的 common &= notch_mask(...)：它在几何上表示"取五个缺口角度 集合的交集"，在实现上只是一次按位与。右下的 t == 360 是唯一的上界判断，它成立的理由 是前面证明的 360 秒周期性——这正是本题区别于纯模拟的地方。

总结

• 本题的算法只有一句话：按秒枚举，判断五个轮子有没有公共缺口角度。
• 让它成为有限算法的关键观察是 $C_k(t + 360) = C_k(t)$：时刻 $t$ 的缺口位置只依赖 $v_k t \bmod 360$，加上 $360 v_k$ 后对 360 取模不变。于是图案以 360 为周期，答案若存在 必在 $[0, 359]$ 内，一圈落空即可输出 none。
• 实现上用 360 位掩码 表示角度集合：缺口是连续 1 段，整轮旋转是环上左移，五轮求交 是按位与。复杂度从朴素写法的 $O(360 \times 360 \times \sum W_k)$ 降到 $O(360 \times \sum W_k)$，都是常数级，但少掉一个 360 因子。
• 最容易踩的坑是张角按闭区间理解（$len$ 覆盖 $len + 1$ 个角度）。样例与全部测试数据 都只在这一约定下成立，写成半开区间会把 spin3、spin6 和样例全部算错。
• 边界上要照顾张角为 0（段长 1）和张角为 359（整圈覆盖，直接返回全 1 掩码）两种情形。