AcWing 1383. 纺轮
原题链接
简单
作者:
Fool_one
,
2021-01-24 20:15:16
,
所有人可见
,
阅读 415
算法:模拟
时间复杂度:$O(360 \times 360 \times 5)$
- 达到 $360$ s 表示无解。
- 按照 每一度 进行划分,打上标记模拟就会更加简单。 (勿按区间)
#include <iostream>
using namespace std;
const int N = 10, M = 360;
int v[N];
bool st[N][M];
int main()
{
for (int i = 0; i < 5; ++i) {
int cnt;
cin >> v[i] >> cnt;
while (cnt--) {
int start, end;
cin >> start >> end;
for (int j = start; j <= start + end; ++j) {
st[i][j % M] = true;
}
}
}
for (int i = 0; i < M; ++i) {
for (int j = 0; j < M; ++j) {
bool flag = false;
for (int k = 0; k < 5; ++k) {
int x = j - i * v[k];
x = (x % M + M) % M;
if (!st[k][x]) {
flag = true;
break;
}
}
if (!flag) {
cout << i << endl;
return 0;
}
}
}
puts("none");
return 0;
}
没看懂
x = (x % N + N) % N;
为什么要%两次?
x%N可能是负数,再加N 再% N可以转化成正数