问题分析

机器人是一个边长为 ( k ) 的正方形，初始位置左下角为 ((0,0))，右上角为 ((k,k))。每次移动会改变机器人的位置，且移动过程中机器人覆盖的所有区域都会被清洁。需要计算所有被清洁区域的总面积（重叠区域只算一次）。

核心难点：机器人移动过程中会形成连续的覆盖区域，需高效计算这些区域的并集面积，避免因 $( n \leq 10^5 )$ 和 $( a_i \leq 10^9 )$ 导致的复杂度爆炸。

关键观察

机器人的移动可分解为 X 轴方向 和 Y 轴方向 的独立位移，且覆盖区域的并集在两个轴上的投影具有单调性：

1. 设机器人在 X 轴方向的投影区间为 $([x_{\text{min}}, x_{\text{max}}])$（初始为 ([0, k])），每次移动后会扩展这个区间（向左/右移动时，新区间是原区间与新位置区间的并集）。
2. Y 轴方向同理，投影区间为 $([y_{\text{min}}, y_{\text{max}}])$（初始为 ([0, k])）。

总面积公式：
机器人覆盖的总面积 = X 轴投影长度 × Y 轴投影长度
其中：

• X 轴投影长度 = $( x_{\text{max}} - x_{\text{min}} )$
• Y 轴投影长度 = $( y_{\text{max}} - y_{\text{min}} )$

算法步骤

1. 初始化区间：

   • X 轴初始区间：$( x_{\text{min}} = 0 )$，$( x_{\text{max}} = k )$
   • Y 轴初始区间：$( y_{\text{min}} = 0 )$，$( y_{\text{max}} = k )$

2. 处理每次移动：
   根据移动方向更新机器人的当前位置，并扩展 X 或 Y 轴的投影区间：

   • E（右移）：新位置的 X 区间为 $([x_{\text{curr}}, x_{\text{curr}} + k])$，更新 $( x_{\text{max}} = \max(x_{\text{max}}, x_{\text{curr}} + k) )$，同时更新当前 X 坐标 $( x_{\text{curr}} )$。
   • W（左移）：新位置的 X 区间为 $([x_{\text{curr}} - a_i, x_{\text{curr}} - a_i + k])$，更新 $( x_{\text{min}} = \min(x_{\text{4min}}, x_{\text{curr}} - a_i) )$，同时更新当前 X 坐标。
   • N（上移）：类似 Y 轴处理，更新 $( y_{\text{max}} )$ 和当前 Y 坐标。
   • S（下移）：类似 Y 轴处理，更新 $( y_{\text{min}} )$ 和当前 Y 坐标。

3. 计算总面积：
   所有移动结束后，总面积 = $((x_{\text{max}} - x_{\text{min}}) \times (y_{\text{max}} - y_{\text{min}}))$。

代实现（Python）

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>

using namespace std;

// 存储大于1且不超过1e18的斐波那契数（从大到小排序）
vector<long long> fibs;
// 记忆化缓存，存储已计算过的n的分解方法数
unordered_map<long long, long long> memo;

// 生成斐波那契数并逆序排列
void generate_fibs() {
    long long a = 1, b = 1;
    while (true) {
        long long c = a + b;
        if (c > 1e18) {
            break;
        }
        fibs.push_back(c);
        a = b;
        b = c;
    }
    // 逆序排列，确保从大到小尝试因子
    reverse(fibs.begin(), fibs.end());
}

// 计算n的分解方法数
long long count_ways(long long n) {
    if (n == 1) {
        return 1; // 空乘积，分解完成
    }
    // 检查缓存，避免重复计算
    if (memo.find(n) != memo.end()) {
        return memo[n];
    }
    
    long long total = 0;
    for (long long f : fibs) {
        if (f > n) {
            continue; // 因子大于n，跳过
        }
        if (n % f == 0) {
            // 若能整除，累加子问题的解
            total += count_ways(n / f);
        }
        // 剪枝：当前因子小于n且不能整除n，更小的因子无需尝试
        if (f < n && n % f != 0) {
            break;
        }
    }
    // 存入缓存
    memo[n] = total;
    return total;
}

int main() {
    generate_fibs(); // 预生成斐波那契数
    
    int t;
    cin >> t;
    while (t--) {
        long long n;
        cin >> n;
        cout << count_ways(n) << endl;
    }
    
    return 0;
}

算法复杂度

• 时间复杂度：( O(n) )，只需遍历所有移动命令一次。
• 空间复杂度：( O(1) )，仅需存储几个区间变量。

算法标签

• 区间合并
• 几何计算
• 模拟
• 贪心（区间扩展）