USACO3.2：纺车的轮子实现思路、代码及复杂度剖析

```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)$，主要用于存储每个轮子的缺口信息。 ######[AI问答 | 857点数解答 | 2026-02-03 15:22:29]