Magic Ship

Created by LXC on Sat Nov 4 20:48:49 2023

https://codeforces.com/problemset/problem/1117/C

ranting: 1900

tag: binary search

problem

在无边无际的大海上，有一艘船所在位置为(x1,y1)，需要到达目的地(x2,y2)。

现在船每天可以朝四个方向中的某一个方向移动一个单位或者不动。

此外由于天气原因，每天的风向会让船向某个方向移动一个单位。

告诉你接下来n天的天气，n天之后的天气是周期性变化的。

现在问到达目的地的最少天数。

solution

我们可以分离风吹的移动和船自身的移动，最后再叠加到一起就是最终位置。

假设第i天船被风吹到位置(x,y)，这个时候我们可以以(x,y)为起点移动不超过i步到达的任意位置都是第i天船可能的位置。

假设第i天能够到达终点，那么i+1天显然也能到达终点，于是答案具有二段性。可以二分查找。

可以预处理出n天经过的位移向量。
只需计算i天经过了几个周期，然后叠加向量即可。可以$O(1)$算出第i天的位置。

code

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

void sol() {
    ll x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    int n;
    cin >> n;
    string s;
    cin >> s;
    vector<pair<ll, ll>> v(1, {0, 0});
    ll x = 0, y = 0;
    for (auto i : s) {
        if (i == 'U') {
            y++;
        }
        if (i == 'D') {
            y--;
        }
        if (i == 'L') {
            x--;
        }
        if (i == 'R') {
            x++;
        }
        v.emplace_back(x, y);
    }
    ll l = 0, r = 1e18 + 7;
    while (l < r) {
        ll m = l + r >> 1;
        ll K = m / n, R = m % n;
        ll cx = x1 + K * x + v[R].first, cy = y1 + K * y + v[R].second;
        if (abs(x2 - cx) + abs(y2 - cy) <= m) {
            r = m;
        } else {
            l = m + 1;
        }
    }
    if (r == 1e18 + 7) {
        cout << "-1\n";
    } else {
        cout << r << "\n";
    }
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}