CF2118D1 题解
2025-08-13 23:04:33
发布于：浙江
18阅读
0回复
0点赞
别问我Hard Ver，我不会（（（
题目翻译：你在一个长度为 左右走向的路上，有 个红绿灯，第 个红绿灯位于 ，从第 秒开始变红灯，每 秒变红 秒，其它时候全为绿灯。
你的一开始朝向是向右， 秒移动一格，如果遇到红灯就转向。
问你在 秒内能不能走出这条路（即位置超过了 的区间）。
显然 是 ， 是 ，不在一个数量级，所以不能走出这条路的情况只能是在某几个红绿灯之间卡住了。
太晚了，直接说做法。
我们找到第一个红绿灯，记录到达它的时间，然后只记录到达红绿灯之间的时间和方向，如果发现重复了就说明卡住了。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <memory.h>
#define int long long
using namespace std;
int a[505], b[505];
bool vis[505][505][2];
int n, m;
void solve2(int start){
for(int i = 0; i <= n + 1; i++){
for(int j = 0; j <= m + 1; j++){
vis[i][j][0] = vis[i][j][1] = 0;
}
}
int idx = lower_bound(a + 1, a + n + 1, start) - a;
if(idx > n){
cout << "YES\n";
return;
}
int cur = (a[idx] - start) % m;
int state = 0;
while(1){
if(vis[idx][cur][state]){
cout << "NO\n";
return;
}
vis[idx][cur][state] = 1;
if(cur == b[idx]) state ^= 1;
if(!state){
if(idx == n){
cout << "YES\n";
return;
}
cur = (cur + a[idx + 1] - a[idx]) % m;
idx++;
}else{
if(idx == 1){
cout << "YES\n";
return;
}
cur = (cur + a[idx] - a[idx - 1]) % m;
idx--;
}
}
}
void solve(){
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++) cin >> b[i];
int q;
cin >> q;
while(q--){
int start;
cin >> start;
solve2(start);
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while(t--) solve();
return 0;
}
时间复杂度 ，空间复杂度 。
有帮助，赞一个