Educational Codeforces Round 60 (Rated for Div. 2) - C. Magic Ship

Problem Educational Codeforces Round 60 (Rated for Div. 2) - C. Magic Ship

Time Limit: 2000 mSec

Problem Description

Input

Output

The only line should contain the minimal number of days required for the ship to reach the point (x2,y2)(x2,y2).

If it's impossible then print "-1".

Sample Input

0 0
4 6
3
UUU

Sample Output

题解：第一感觉是bfs，然后大概背包一下之类的，但是数据范围不允许呀，做出这个题的关键点就是注意到运动独立性（呵呵），和如果在第x天能到，那么对于y >= x的都能到，因此就可以二分，固定了天数之后，风吹的距离就是固定的，并且可以用前缀和O(1)求，然后就是判断风吹到的点和目标点的哈密顿距离是否<=天数即可。

 #include <bits/stdc++.h>

 using namespace std;

 #define REP(i, n) for (int i = 1; i <= (n); i++)

 #define sqr(x) ((x) * (x))

 const int maxn =  + ;

 const int maxm =  + ;

 const int maxs =  + ;

 typedef long long LL;

 typedef pair<int, int> pii;

 typedef pair<double, double> pdd;

 const LL unit = 1LL;

 const int INF = 0x3f3f3f3f;

 const double eps = 1e-;

 const double inf = 1e15;

 const double pi = acos(-1.0);

 const int SIZE =  + ;

 const LL MOD = ;

 LL sx, sy, ex, ey;

 LL x[maxn], y[maxn];

 LL n;

 string str;

 bool Judge(LL lim)

 {

     LL m = lim / n, remain = lim % n;

     LL xx = sx + m * x[n] + x[remain];

     LL yy = sy + m * y[n] + y[remain];

     if (abs(xx - ex) + abs(yy - ey) <= lim)

         return true;

     return false;

 }

 int main()

 {

     ios::sync_with_stdio(false);

     cin.tie();

     //freopen("input.txt", "r", stdin);

     //freopen("output.txt", "w", stdout);

     cin >> sx >> sy >> ex >> ey;

     cin >> n;

     cin >> str;

     LL len = str.size();

     for (LL i = ; i < len; i++)

     {

         if (str[i] == 'U')

         {

             x[i + ] = x[i];

             y[i + ] = y[i] + ;

         }

         else if (str[i] == 'D')

         {

             x[i + ] = x[i];

             y[i + ] = y[i] - ;

         }

         else if (str[i] == 'L')

         {

             x[i + ] = x[i] - ;

             y[i + ] = y[i];

         }

         else

         {

             x[i + ] = x[i] + ;

             y[i + ] = y[i];

         }

     }

     LL le = , ri = LLONG_MAX / ;

     LL ans = -;

     while (le <= ri)

     {

         LL mid = (le + ri) / ;

         if (Judge(mid))

         {

             ri = mid - ;

             ans = mid;

         }

         else

         {

             le = mid + ;

         }

     }

     cout << ans << endl;

     return ;

 }