「巴厘岛的雕塑」题解

问题分析

给定 $N$ 个雕塑的年龄 $Y_i$，需要将它们分成恰好 $X$ 组（$A \leq X \leq B$），每组连续。每组的年龄和进行按位或运算，得到最终优美度。要求最小化这个优美度。

关键观察

1. 位运算性质：按位或运算只会使数值增大或不变，不会减小。
2. 最小化思路：从高位到低位考虑，尽可能让最终优美度的每一位为 $0$。
3. 二分答案可行性：由于答案范围可达 $10^{15}$ 级别，直接枚举不可行，考虑按位确定答案。

算法框架

对于小数据，可以采用DP + 按位贪心的方法：

1. 从高到低逐位确定：

   • 从最高位（如第60位，因为总和可能很大）开始考虑
   • 对于当前考虑的位 $k$，我们希望最终优美度的这一位为 $0$

2. DP验证可行性：

   • 设当前已经确定了高位的一些位为 $0$，这些位构成一个掩码 $mask$
   • 我们需要判断：是否存在一种分组方式，使得： a) 组数在 $[A, B]$ 之间 b) 每一组的和与 $mask$ 的按位与为 $0$（即不包含已经确定为 $0$ 的位） c) 每一组的和在第 $k$ 位也为 $0$

3. DP状态设计：

   • $dp[i][j]$：表示考虑前 $i$ 个雕塑，分成 $j$ 组是否可行
   • 转移：$dp[i][j] = \bigvee_{l<j} (dp[l][j-1] \text{ and valid}(l+1, i))$
   • 其中 $valid(l, r)$ 表示区间 $[l, r]$ 作为一组是否满足上述条件

4. 时间复杂度：$O(\text{位数} \times N^3)$，优化后可达 $O(\text{位数} \times N^2)$

当 $A = 1$ 时，问题简化为：最少分组数没有下限，只需要不超过 $B$ 组。

1. 同样从高到低逐位确定

2. 使用一维DP：

   • $dp[i]$：表示前 $i$ 个雕塑最少需要多少组
   • 转移：$dp[i] = \min_{l<i} (dp[l] + 1)$，其中区间 $[l+1, i]$ 满足条件
   • 最终检查 $dp[N] \leq B$ 是否成立

3. 优化：

   • 前缀和加速区间和计算
   • 时间复杂度：$O(\text{位数} \times N^2)$，对于 $N=2000$ 可能较慢
   • 可以进一步优化到 $O(\text{位数} \times N)$，通过记录可行的转移位置

算法步骤详解

步骤1：预处理前缀和

计算 $pre[i] = \sum_{j=1}^i Y_j$，方便计算任意区间和。

步骤2：逐位确定答案

初始化答案 $ans = 0$。

从高位到低位（如从60到0）：

1. 尝试将当前位设为 $0$：$test = ans | (1<<k) - 1$（即当前位为0，低位全1）
2. 用DP验证是否存在分组，使得所有组的和按位与 $test$ 等于自身（即不含 $test$ 中为0的位）
3. 如果存在，则这一位可以设为0，否则必须设为1，更新 $ans |= (1<<k)$

步骤3：DP验证函数

对于一般情况（$A > 1$）：

function check(mask):
    dp[0][0] = true
    for i = 1 to N:
        for j = 1 to min(i, B):
            dp[i][j] = false
            for l = j-1 to i-1:
                if dp[l][j-1] and ((pre[i]-pre[l]) & mask) == (pre[i]-pre[l]):
                    dp[i][j] = true
                    break
    
    检查是否存在 A ≤ j ≤ B 使得 dp[N][j] = true

对于 $A = 1$ 的情况：

function check(mask):
    dp[0] = 0
    for i = 1 to N:
        dp[i] = INF
        for l = 0 to i-1:
            if ((pre[i]-pre[l]) & mask) == (pre[i]-pre[l]):
                dp[i] = min(dp[i], dp[l] + 1)
    返回 dp[N] ≤ B

步骤4：边界情况处理

• 当 $B = N$ 时，可以每个雕塑单独一组
• 当 $A = B$ 时，必须恰好分成 $A$ 组
• 注意 $Y_i$ 可能为0

复杂度分析

：$O(\log V \cdot N^3)$，其中 $V$ 为值域，$N \leq 100$ 可过 $O(\log V \cdot N^2)$，$N \leq 2000$ 需要优化

优化技巧

• 对于 $A = 1$ 的情况，可以使用单调队列或贪心优化到 $O(\log V \cdot N)$
• 提前剪枝：如果当前位必须为1，则直接设置，不需要DP验证
• 使用位运算加速条件判断

算法正确性证明

1. 从高到低贪心的正确性：由于高位为1对数值的影响远大于低位，优先保证高位为0是最优策略。
2. DP验证的正确性：DP准确刻画了分组问题的约束条件，验证了在当前掩码下是否存在合法分组。
3. 最小性保证：通过从高位到低位尽可能置0，得到的答案是最小的。

实现注意事项

1. 数据类型：使用64位整数，因为总和可能超过32位。
2. DP初始化：注意边界条件的设置。
3. 位运算优先级：注意括号的使用。
4. 前缀和索引：$pre[0] = 0$，$pre[i]$ 表示前 $i$ 个数的和。

总结

本题的核心思想是：

• 按位贪心：从高位到低位确定答案
• DP验证：判断在当前位限制下是否存在合法分组
• 分类处理：根据 $A$ 是否为1采用不同的DP方法