Editorial for Bedao Mini Contest 24 - Robot
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Đặt ~x = x_e - x_s~, ~y = y_e - y_s~.
Xét mọi dãy con độ dài ~k~ trong dãy, giả sử ta chuyển hết dãy con về I.
Gọi ~x'~ là tổng đường đi theo phương ngang, ~y'~ là tổng đường đi theo phương dọc sau khi đã thay đổi dãy. Ta có thể dễ dàng tính được các giá trị này trong ~O(1)~ bằng tổng dồn.
Để robot đến được đích thì ~x' = x~ và ~y' = y~. Khi đó, ta cần thay đổi tối thiểu ~|x - x'| + |y - y'|~ giá trị trong dãy con. Nếu ~|x - x'| + |y - y'| \le k~ thì đáp án là "YES".
Độ phức tạp: ~O(n)~.
#include <bits/stdc++.h> #define ll long long #define pa pair<int, int> #define fi first #define se second using namespace std; const int N = 1e5 + 5; int n, k; int x_s, y_s, x_e, y_e; int x_sum[N], y_sum[N]; string S; bool pass() { int X = x_e - x_s, Y = y_e - y_s; for (int L = 1, R = k; R <= n; L++, R++) { int x_temp = x_sum[L - 1] + (x_sum[n] - x_sum[R]); int y_temp = y_sum[L - 1] + (y_sum[n] - y_sum[R]); if (abs(X - x_temp) + abs(Y - y_temp) <= k) return true; } return false; } int main() { cin.tie(0) -> sync_with_stdio(0); #ifdef LOCAL_MACHINE if (fopen("task.inp", "r")) { freopen("task.inp", "r", stdin); freopen("task.out", "w", stdout); } #endif int t; cin >> t; while(t--) { cin >> n >> k; cin >> x_s >> y_s >> x_e >> y_e; cin >> S; S = ' ' + S; // Build prefix sum for (int i = 1; i <= n; i++) { x_sum[i] = x_sum[i - 1] + (S[i] == 'L' ? -1 : (S[i] == 'R' ? 1 : 0)); y_sum[i] = y_sum[i - 1] + (S[i] == 'U' ? -1 : (S[i] == 'D' ? 1 : 0)); } cout << (pass() ? "YES" : "NO") << '\n'; } return 0; }
Comments
Wrong Answer Solution :))