「POI2014 R3」太阳能板 Solar Panels 题解

题目大意

有 $n$ 块太阳能板，每块板的尺寸范围是：

• 宽度：$[s_{\min}, s_{\max}]$
• 高度：$[w_{\min}, w_{\max}]$

太阳能板由相同大小的正方形电池组成。我们需要为每块板找到最大的电池边长 $k$，使得：

• 存在某个宽度 $s \in [s_{\min}, s_{\max}]$
• 存在某个高度 $w \in [w_{\min}, w_{\max}]$
• $k$ 能整除 $s$ 和 $w$（即 $s$ 和 $w$ 都是 $k$ 的倍数）

问题分析

数学形式化

对于每个查询 $(s_{\min}, s_{\max}, w_{\min}, w_{\max})$，我们需要找到最大的整数 $k$，使得：

$$\exists s \in [s_{\min}, s_{\max}], \exists w \in [w_{\min}, w_{\max}] \text{ 满足 } k \mid s \text{ 且 } k \mid w $$

等价于：

$$\exists s \in [s_{\min}, s_{\max}] \text{ 满足 } k \mid s \quad \text{且} \quad \exists w \in [w_{\min}, w_{\max}] \text{ 满足 } k \mid w $$

关键观察

1. 区间整除条件：对于区间 $[a, b]$ 和除数 $k$，存在 $x \in [a, b]$ 被 $k$ 整除当且仅当：

   $$\left\lfloor \frac{b}{k} \right\rfloor - \left\lfloor \frac{a-1}{k} \right\rfloor \geq 1 $$

   即区间 $[a, b]$ 内至少包含一个 $k$ 的倍数。

2. 最大可能的 $k$：显然 $k \leq \min(s_{\max}, w_{\max})$。

算法思路

方法一：直接枚举（适用于小数据）

对于 $n \leq 10$ 且数据范围较小的情况，可以直接枚举可能的 $k$：

int solve(int smin, int smax, int wmin, int wmax) {
    int ans = 1;
    int maxk = min(smax, wmax);
    
    for (int k = maxk; k >= 1; k--) {
        // 检查宽度区间是否有k的倍数
        bool width_ok = (smax / k - (smin - 1) / k) >= 1;
        // 检查高度区间是否有k的倍数  
        bool height_ok = (wmax / k - (wmin - 1) / k) >= 1;
        
        if (width_ok && height_ok) {
            ans = k;
            break;
        }
    }
    return ans;
}

复杂度：$O(n \cdot \min(s_{\max}, w_{\max}))$，对于大数据不可行。

方法二：数学优化

观察：我们只需要检查所有可能的候选 $k$，这些候选是：

• 所有 $\leq \min(s_{\max}, w_{\max})$ 的整数
• 但可以跳过一些明显不可能的值

更聪明的方法：从 $\min(s_{\max}, w_{\max})$ 开始向下枚举，但利用整除性质提前终止。

方法三：高效算法

关键思路：最大可能的 $k$ 一定是某个区间端点的约数，或者是某些特定值。

算法步骤：

1. 设 $M = \min(s_{\max}, w_{\max})$
2. 从 $k = M$ 开始向下检查
3. 对于每个 $k$，检查：
   • 宽度区间 $[s_{\min}, s_{\max}]$ 是否包含 $k$ 的倍数
   • 高度区间 $[w_{\min}, w_{\max}]$ 是否包含 $k$ 的倍数
4. 找到第一个满足条件的 $k$ 就是答案

优化：使用整除分块的思想，跳过一些不可能的值。

代码实现

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

// 检查区间[a, b]中是否存在k的倍数
bool has_multiple(int a, int b, int k) {
    return (b / k) > ((a - 1) / k);
}

int solve(int smin, int smax, int wmin, int wmax) {
    int ans = 1;
    int maxk = min(smax, wmax);
    
    // 从大到小枚举k
    for (int k = maxk; k >= 1; k--) {
        // 优化：如果当前答案已经大于等于k，直接返回
        if (ans >= k) break;
        
        if (has_multiple(smin, smax, k) && has_multiple(wmin, wmax, k)) {
            ans = k;
            break;
        }
    }
    return ans;
}

// 更高效的版本
int solve_fast(int smin, int smax, int wmin, int wmax) {
    int ans = 1;
    int maxk = min(smax, wmax);
    
    // 使用一些启发式优化
    for (int k = maxk; k >= 1; k--) {
        // 快速检查：如果k已经小于等于当前答案，没必要继续
        if (k <= ans) break;
        
        // 检查宽度区间
        if (smax / k == (smin - 1) / k) continue;
        
        // 检查高度区间
        if (wmax / k == (wmin - 1) / k) continue;
        
        ans = k;
        break;
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    for (int i = 0; i < n; i++) {
        int smin, smax, wmin, wmax;
        cin >> smin >> smax >> wmin >> wmax;
        
        int result = solve_fast(smin, smax, wmin, wmax);
        cout << result << "\n";
    }
    
    return 0;
}

复杂度分析

最坏情况

• 每次查询需要检查最多 $\min(s_{\max}, w_{\max})$ 个值
• 总复杂度：$O(n \cdot \min(s_{\max}, w_{\max}))$

实际性能

• 由于从大到小枚举，通常很快找到答案
• 对于随机数据，期望检查次数远小于 $\min(s_{\max}, w_{\max})$
• 可以通过额外优化进一步加速

进一步优化

优化一：利用区间性质

如果 $s_{\max} - s_{\min} \geq k$，那么区间 $[s_{\min}, s_{\max}]$ 一定包含 $k$ 的倍数。

优化二：只检查候选值

最大可能的 $k$ 一定是：

• $s_{\max}$ 的约数
• $w_{\max}$ 的约数
• 或者是某些边界值

优化三：二分答案

虽然答案不满足单调性（大的k满足时小的k一定满足，但反过来不成立），但可以结合其他技巧。

样例分析

样例1：3 9 8 8

• 最大可能 $k = \min(9, 8) = 8$
• 检查 $k=8$：宽度区间 $[3,9]$ 有 $8$，高度区间 $[8,8]$ 有 $8$
• 答案：$8$

样例2：1 10 11 15

• 最大可能 $k = \min(10, 15) = 10$
• $k=10$：宽度区间有 $10$，但高度区间 $[11,15]$ 没有 $10$ 的倍数
• $k=9$：宽度区间有 $9$，高度区间没有 $9$ 的倍数
• ...
• $k=7$：宽度区间有 $7$，高度区间有 $14$
• 答案：$7$

总结

这道题的核心在于：

1. 理解整除在区间中的存在性条件
2. 从大到小枚举的贪心策略
3. 利用整数除法的性质进行快速检查