D. 生日礼物 详细题解

题目核心理解

给定一个长度为 $n$ 的数组 $a$ 和一个整数 $x$。 需要把数组恰好划分成 $k$ 个连续、不重叠、覆盖全部的子段，满足：

1. 第一段从 $1$ 开始，最后一段到 $n$ 结束。
2. 每一段内部求异或和。
3. 把所有段的异或和再做一次按位或，结果 $\le x$。

求能满足条件的最大 $k$，如果不存在合法划分则输出 $-1$。

核心思路

1. 关键性质

• 按位或只会只增不减，因此高位约束更强，适合从高位到低位贪心构造。
• 我们要构造一个掩码 $mask$，使得所有分段的异或和满足：$$(cur \mid mask) \le x$$
• 尽可能在每一个满足条件的位置立即分段，这样得到的段数 $k$ 最大。

2. 判定规则

对一个固定掩码 $mask$，判断是否存在合法划分：

• 遍历数组，维护当前段异或和 $cur$。
• 每加入一个数：$cur = cur \oplus a[i]$。
• 若 $(cur \mid mask) \le x$，则在此处分段，计数 $+1$，并清空 $cur$。
• 遍历结束后，若 $cur=0$ 且划分完成，则返回段数；否则返回 $-1$。

3. 掩码构造

从高位到低位（第 $29$ 位到第 $0$ 位）依次尝试：

• 尝试将当前位加入掩码。
• 如果新掩码仍然可以合法划分，则保留该位。
• 否则不保留，继续处理下一位。

算法流程

1. 初始化掩码 $mask=0$。
2. 从第 $29$ 位到第 $0$ 位逐位尝试加入掩码，并检查是否仍可合法划分。
3. 用最终得到的掩码再跑一次贪心分段。
4. 输出得到的最大段数，无法划分则输出 $-1$。

公式与复杂度分析

合法分段条件：

复杂度

• 逐位构造掩码：$O(30)$
• 单次贪心遍历：$O(n)$
• 总时间复杂度：$O(30n)$

可轻松处理 $n \le 10^5$、多组数据 $\sum n \le 10^5$ 的范围。