[USACO3.2]纺车的轮子 Spinning Wheels 显示标签 时间限制：C/C++ 1000MS，其他语言 2000MS 内存限制：C/C++ 256MB，其他语言 512MB 难度：普及 分数：100 OI排行榜得分：16(0.1*分数+2*难度) 出题人： 描述 一架纺车有五个纺轮（也就是五个同心圆），这五个不透明的轮子边缘上都有一些缺口。这些缺口必须被迅速而准确地排列好。每个轮子都有一个起始标记（在0度），这样所有的轮子都可以在统一的已知位置开始转动。轮子按照角度变大的方向旋转（即0经过旋转到达1的位置），所以从起始位置开始，在一定的时间内，它们依次转过1度，2度等等（虽然这些轮子很可能不会同时转过这些角度）。 这是一个整数问题。轮子不会转过1.5度或23.51234123度这样的角度。例如，轮子可能在一秒钟内转过20到25度甚至30到40度（如果转得快的话）。 这个问题中的所有角度都限制在 0 <= 角度 <= 359 这个范围内。轮子转过 359 度后接下来就是 0 度。每个轮子都有一个确定的旋转速度，以秒作为单位。1 <= 速度 <= 180。 轮子

```cpp #include <iostream> #include <vector> using namespace std; // 定义轮子结构体，包含旋转速度和缺口信息 struct Wheel { int speed; vector<pair<int, int>> gaps; }; // 检查在给定时间 t 时，是否所有轮子的缺口都能对齐 bool check(const vector<Wheel>& wheels, int t) { // 遍历所有可能的角度 for (int angle = 0; angle < 360; ++angle) { bool allAligned = true; // 检查每个轮子在时间 t 时该角度是否有缺口 for (const auto& wheel : wheels) { bool hasGap = false; for (const auto& gap : wheel.gaps) { int start = (gap.first + wheel.speed * t) % 360; int end = (start + gap.second - 1) % 360; if (start <= end) { if (angle >= start && angle <= end) { hasGap = true; break; } } else { if (angle >= start || angle <= end) { hasGap = true; break; } } } if (!hasGap) { allAligned = false; break; } } if (allAligned) { return true; } } return false; } int main() { vector<Wheel> wheels(5); // 读取每个轮子的信息 for (int i = 0; i < 5; ++i) { int speed, numGaps; cin >> speed >> numGaps; wheels[i].speed = speed; for (int j = 0; j < numGaps; ++j) { int start, width; cin >> start >> width; wheels[i].gaps.emplace_back(start, width); } } // 遍历时间，从 0 到 360 秒 for (int t = 0; t <= 360; ++t) { if (check(wheels, t)) { cout << t << endl; return 0; } } cout << "none" << endl; return 0; } ``` 代码解释： 1. 结构体 `Wheel`：用于存储每个轮子的旋转速度和缺口信息。`speed` 表示轮子的旋转速度，`gaps` 是一个存储缺口起始角度和宽度的向量。 2. 函数 `check`：用于检查在给定时间 `t` 时，是否所有轮子的缺口都能对齐。通过遍历所有可能的角度，对于每个角度，检查每个轮子在该时间是否有缺口覆盖该角度。 3. 主函数 `main`： - 读取每个轮子的信息，包括旋转速度、缺口数量和每个缺口的起始角度和宽度。 - 遍历时间，从 0 到 360 秒，调用 `check` 函数检查是否有缺口对齐的情况。 - 如果找到对齐的时间，输出该时间并结束程序；否则，输出 `none`。 复杂度分析： - 时间复杂度：$O(360 \times 360 \times 5 \times 5)$，其中 360 是时间的最大值，360 是角度的最大值，5 是轮子的数量，5 是每个轮子最多的缺口数量。 - 空间复杂度：$O(5 \times 5)$，主要用于存储每个轮子的缺口信息。 [2026-02-03 15:22:29 | AI问答 | 857点数解答]