编程题  远航  时间限制:5000MS  内存限制:786432KB  题目描述:  船队要远航之前会先探测航行时的风向。根据探测队的情报，这个地区的风是周期性无限循环的,每个周期持续n天。同时，风力都处处相同，只有每天的风向不同:  U:表示风会把一个物体从(x,y)吹向(x,y+1);  D:表示风会把一个物体从(x,y)吹向(x,y-1);  L:表示风会把一个物体从(x,y)吹向(x-1,y);  R:表示风会把一个物体从(x,y)吹向(x+1,y);  有时候船队会利用或者抵抗风的作用。每一天，船队可以选择一个方向进行航行，向该方向前进一格。船队自己的作用与风的作用会叠加，例如船队在(x,y)向上(U)开，而此时风向为L时，船队会从(x,y)到达(x-1,y+1).  船队从(sx,sy)出发，目的地是(ex,ey)。在航行之前，身为船长的你需要知道最快需要多少天才能到达目的地，或者无法到达。假设这片海域无限大。     输入描述  第一行一个正整数T,表示数据组数。  对于每一组数据,第一行四个整数sx,sy,ex,ey;  第二行一个正整数n;  第三行一个长度为n的仅包含UDLR四种字符的字符串，表示一个周期内每天的风向。  对于100%的数据，1≤n≤10^5,0<sy,sy,ex,ey<10^9,1≤T≤5，(sx,sy)≠(ex,ey)  输出描述  对于每一组数据，如果船队能够到达目的地,输出最少需要的天数;否则,输出-1。  样例输入  2  0 0 3 5  3  URU  0 0 3 3  1  D  样例输出  4  -1  提示  对于样例一，船的操作为RRUU  坐标变化为(0,0)→(1,1)→(3,1)→(3,3)→(3,5)  #include <iostream>#include <string>#include <vector>#include <numeric>#include <cmath>using namespace std;// 预计算的风位移long long prefix_wind_x[100005];long long prefix_wind_y[100005];long long cycle_x, cycle_y;int n;long long dx, dy;/** * @brief 检查 K 天是否足够 * @param K 天数 * @return true 如果 K 天可能到达，否则 false */bool check(long long K) {    if (K == 0) return (dx == 0 && dy == 0);    long long num_cycles = K / n;    long long remaining_days = K % n;    long long wind_x = num_cycles * cycle_x;    long long wind_y = num_cycles * cycle_y;    if (remaining_days > 0) {        wind_x += prefix_wind_x[remaining_days - 1];        wind_y += prefix_wind_y[remaining_days - 1];    }    long long required_ship_x = dx - wind_x;    long long required_ship_y = dy - wind_y;    long long required_dist = abs(required_ship_x) + abs(required_ship_y);    // 约束 1: 距离足够    // 约束 2: 奇偶性相同 (K % 2 == required_dist % 2)    // 我们的主函数已经预先检查了奇偶性，这里 K 和 required_dist 奇偶性自动相同    return K >= required_dist;}long long solve() {    long long sx, sy, ex, ey;    cin >> sx >> sy >> ex >> ey;    string wind_s;    cin >> n >> wind_s;    dx = ex - sx;    dy = ey - sy;    // 关键奇偶性预检查    // f(0) = 0 - (abs(dx) + abs(dy))    // f(K) 必须为偶数，且 f(K) 的奇偶性 = f(0) 的奇偶性    // 因此 f(0) 必须为偶数，即 abs(dx) + abs(dy) 必须为偶数    if ((abs(dx) + abs(dy)) % 2 != 0) {        return -1;    }    // 预处理风的前缀和    prefix_wind_x[0] = 0;    prefix_wind_y[0] = 0;    for (int i = 0; i < n; ++i) {        // (i > 0) 的情况        if (i > 0) {            prefix_wind_x[i] = prefix_wind_x[i - 1];            prefix_wind_y[i] = prefix_wind_y[i - 1];        }                // (i = 0) 的情况，从 (0,0) 开始        if (i == 0) {             prefix_wind_x[0] = 0;             prefix_wind_y[0] = 0;        }        if (wind_s[i] == 'U') prefix_wind_y[i]++;        else if (wind_s[i] == 'D')