#4922. 「POI2019 R1」小机器人 Robby the little robot 题解

题目分析

我们有一个机器人在网格平面上移动，初始位置在 $(0,0)$，面向北。给定一个长度为 $n$ 的命令序列 $d_1, d_2, \ldots, d_n$，机器人会循环执行这些命令：

• 第 $i$ 步：向前移动 $d_{((i-1) \bmod n) + 1}$ 个单位，然后右转 $90^\circ$

每个移动或转弯都消耗 $1$ 秒。电池总共能支持 $t$ 秒。我们需要计算在时间 $0$ 到 $t$ 之间，机器人经过目标点 $(x, y)$ 的次数。

关键约束：$t$ 可以达到 $10^{18}$，因此不能直接模拟每一步。

核心观察

1. 方向周期性

机器人的方向变化是周期性的：

• 方向序列：北(0°) → 东(90°) → 南(180°) → 西(270°) → 北(360°)...
• 每 $4$ 步完成一个方向循环

2. 命令周期性

由于命令序列长度为 $n$，完整的运动周期是 $4n$ 步：

• 每 $4n$ 步后，机器人回到初始方向，并完成 $n$ 个完整的命令循环

3. 位置变化的数学表达

设第 $i$ 步移动的距离为 $a_i = d_{((i-1) \bmod n) + 1}$，方向为 $dir_i = (i-1) \bmod 4$。

位置 $(X_k, Y_k)$ 经过 $k$ 步后可以表示为：

$$X_k = \sum_{i=1}^k a_i \cdot \cos(dir_i \cdot 90°) $$$$Y_k = \sum_{i=1}^k a_i \cdot \sin(dir_i \cdot 90°) $$

由于方向只有 4 种，可以简化为：

• 北(+y)：$(0, +a_i)$
• 东(+x)：$(+a_i, 0)$
• 南(-y)：$(0, -a_i)$
• 西(-x)：$(-a_i, 0)$

算法设计

步骤1：预处理前缀和

定义四个方向的前缀和数组：

• sumN[i]：前 $i$ 步中向北移动的总距离
• sumE[i]：前 $i$ 步中向东移动的总距离
• sumS[i]：前 $i$ 步中向南移动的总距离
• sumW[i]：前 $i$ 步中向西移动的总距离

这样，经过 $k$ 步后的位置为：

$$X_k = \text{sumE}[k] - \text{sumW}[k]$$ $$Y_k = \text{sumN}[k] - \text{sumS}[k]$$

步骤2：计算周期位移

计算一个完整周期（$4n$ 步）的位移：

$$\Delta X = X_{4n} - X_0 = \text{sumE}[4n] - \text{sumW}[4n] $$$$\Delta Y = Y_{4n} - Y_0 = \text{sumN}[4n] - \text{sumS}[4n] $$

步骤3：批量处理完整周期

设总步数为 $steps = \min(t, \text{最大可能步数})$，计算完整周期数：

$$cycles = \lfloor steps / (4n) \rfloor$$

剩余步数：$remainder = steps \bmod (4n)$

对于第 $c$ 个周期结束时的位置（$c = 0, 1, \ldots, cycles-1$）：

$$X_{c \cdot 4n} = c \cdot \Delta X$$ $$Y_{c \cdot 4n} = c \cdot \Delta Y$$

步骤4：检查每个时间点的位置

我们需要检查所有时间点 $k = 0, 1, 2, \ldots, steps$ 是否在目标点 $(x, y)$。

对于每个完整周期内的位置：

• 基础位置：$(c \cdot \Delta X, c \cdot \Delta Y)$
• 相对偏移：使用前缀和数组计算 $k \bmod (4n)$ 步后的位置
• 总位置：基础位置 + 相对偏移

步骤5：优化检查过程

由于 $t$ 很大，我们不能检查每个时间点。优化方法：

观察：在一个周期内，每个时间点的位置是固定的。我们只需要：

1. 预处理一个周期内所有可能到达目标点的时间点
2. 对于每个完整周期，检查这些时间点加上周期偏移后是否在时间范围内
3. 对剩余部分单独检查

具体实现

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    ll n, t;
    cin >> n >> t;
    
    vector<ll> d(n);
    for (int i = 0; i < n; i++) {
        cin >> d[i];
    }
    
    ll target_x, target_y;
    cin >> target_x >> target_y;
    
    // 方向：0-北, 1-东, 2-南, 3-西
    vector<ll> sumN(4*n+1, 0), sumE(4*n+1, 0), sumS(4*n+1, 0), sumW(4*n+1, 0);
    
    // 计算前缀和
    for (int i = 1; i <= 4*n; i++) {
        int cmd_idx = (i-1) % n;
        int dir = (i-1) % 4;
        
        sumN[i] = sumN[i-1];
        sumE[i] = sumE[i-1]; 
        sumS[i] = sumS[i-1];
        sumW[i] = sumW[i-1];
        
        if (dir == 0) sumN[i] += d[cmd_idx];      // 北
        else if (dir == 1) sumE[i] += d[cmd_idx]; // 东
        else if (dir == 2) sumS[i] += d[cmd_idx]; // 南  
        else sumW[i] += d[cmd_idx];               // 西
    }
    
    // 计算周期位移
    ll deltaX = sumE[4*n] - sumW[4*n];
    ll deltaY = sumN[4*n] - sumS[4*n];
    
    // 预处理一个周期内能到达目标点的时间
    vector<ll> valid_times;
    for (ll k = 0; k <= min(t, 4*n*1LL); k++) {
        ll xk = sumE[k] - sumW[k];
        ll yk = sumN[k] - sumS[k];
        if (xk == target_x && yk == target_y) {
            valid_times.push_back(k);
        }
    }
    
    ll result = 0;
    ll max_steps = min(t, 4*n * (t / (4*n) + 2)); // 安全上限
    
    // 检查每个完整周期
    ll cycles = max_steps / (4*n);
    for (ll c = 0; c < cycles; c++) {
        ll base_x = c * deltaX;
        ll base_y = c * deltaY;
        
        for (ll time_in_cycle : valid_times) {
            ll total_time = c * 4*n + time_in_cycle;
            if (total_time > t) continue;
            
            ll rel_x = sumE[time_in_cycle] - sumW[time_in_cycle];
            ll rel_y = sumN[time_in_cycle] - sumS[time_in_cycle];
            
            if (base_x + rel_x == target_x && base_y + rel_y == target_y) {
                result++;
            }
        }
    }
    
    // 检查剩余部分
    ll remaining_steps = max_steps % (4*n);
    for (ll k = cycles * 4*n; k <= min(t, cycles * 4*n + remaining_steps); k++) {
        ll cycle_num = k / (4*n);
        ll time_in_cycle = k % (4*n);
        
        ll base_x = cycle_num * deltaX;
        ll base_y = cycle_num * deltaY;
        ll rel_x = sumE[time_in_cycle] - sumW[time_in_cycle];
        ll rel_y = sumN[time_in_cycle] - sumS[time_in_cycle];
        
        if (base_x + rel_x == target_x && base_y + rel_y == target_y) {
            result++;
        }
    }
    
    cout << result << "\n";
    
    return 0;
}

复杂度分析

• 预处理：$O(n)$ 计算前缀和
• 周期内检查：$O(n)$ 预处理有效时间点
• 周期处理：$O(\frac{t}{n} \times n) = O(t)$ 最坏情况，但实际由于 $t$ 很大，需要进一步优化

进一步优化

对于 $t \leq 10^{18}$ 的情况，需要数学推导来直接计算而不遍历所有周期。核心思想：

1. 将问题转化为求解方程：$c \cdot \Delta X + X_r = x$ 和 $c \cdot \Delta Y + Y_r = y$
2. 对于每个周期内的相对位置 $(X_r, Y_r)$，解出满足条件的周期数 $c$
3. 检查这些周期数是否在范围内

这样复杂度降为 $O(n)$，可以处理 $t \leq 10^{18}$ 的情况。

总结

本题的关键在于发现机器人运动的周期性，并通过数学方法批量处理，避免直接模拟每一步。标签应为：周期性分析、模拟优化、数学推导。