Usuwanie 题解

算法思路

核心思想

这是一个奇偶性配对问题。由于每次操作要求两个数的和为偶数，这意味着只能选择：

• 两个奇数相加（奇 + 奇 = 偶）
• 两个偶数相加（偶 + 偶 = 偶）

因此，问题转化为：在区间 $[a, b]$ 中，最多能配成多少对相同奇偶性的数。

关键观察

1. 配对限制：只能奇数与奇数配对，偶数与偶数配对
2. 最大匹配：每个奇数可以与另一个奇数配对，每个偶数可以与另一个偶数配对
3. 剩余元素：如果某类数字个数为奇数，会剩下一个无法配对

算法详解

1. 统计奇偶数量

vector<long long> cnt(2);
cnt[a % 2] += (b - a + 2) / 2;
cnt[(a % 2) ^ 1] += (b - a + 1) - cnt[a % 2];

计算原理：

• cnt[0] 存储偶数数量，cnt[1] 存储奇数数量
• 从 $a$ 开始，序列的奇偶性模式是固定的
• (b - a + 2) / 2 计算从 $a$ 开始，与 $a$ 同奇偶性的数字个数
• 总数减去上述结果得到另一种奇偶性的数字个数

2. 计算最大可移除数量

cout << cnt[1] / 2 * 2 + cnt[0] / 2 * 2 << "\n";

计算逻辑：

• cnt[1] / 2 * 2：奇数中可以配对的数量（向下取整后 ×2）
• cnt[0] / 2 * 2：偶数中可以配对的数量（向下取整后 ×2）
• 总和就是最大可移除的元素数量

数学推导

设区间 $[a, b]$ 中：

• 奇数个数为 $odd$
• 偶数个数为 $even$

则最大可配对数 = $\lfloor \frac{odd}{2} \rfloor \times 2 + \lfloor \frac{even}{2} \rfloor \times 2$

因为每配对成功一对就移除 2 个元素。

正确性证明

为什么这是最优解

1. 配对限制：由于只能同奇偶性配对，奇数与偶数之间无法配对
2. 独立配对：奇数内部和偶数内部的配对互不影响
3. 最大匹配：每类数字都尽可能两两配对，剩下的单个数字无法再配对

边界情况验证

• 当所有数字都是奇数：移除 $odd - (odd \% 2)$ 个
• 当所有数字都是偶数：移除 $even - (even \% 2)$ 个
• 当奇偶数量都很多：分别配对，互不干扰

复杂度分析

• 时间复杂度：$O(1)$，只进行常数次算术运算
• 空间复杂度：$O(1)$，只使用固定大小的变量
• 对于 $b \leq 10^{18}$ 的极端数据范围完全可行

算法标签

• 数学推理 (Mathematical Reasoning)
• 奇偶性分析 (Parity Analysis)
• 组合优化 (Combinatorial Optimization)
• 贪心算法 (Greedy Algorithm)
• 数论 (Number Theory)

特殊技巧

1. 直接公式计算：避免遍历大区间，直接通过数学公式求解
2. 奇偶模式利用：利用等差数列的奇偶分布规律
3. 整数除法特性：利用整数除法的向下取整自动处理剩余元素

样例验证

样例1：$a=3, b=7$

• 数字：3(奇), 4(偶), 5(奇), 6(偶), 7(奇)
• 奇数：3个 → 可配对 2 个
• 偶数：2个 → 可配对 2 个
• 总计：4个 ✓

样例2：$a=1, b=10$

• 奇数：1,3,5,7,9 → 5个 → 可配对 4个
• 偶数：2,4,6,8,10 → 5个 → 可配对 4个
• 总计：8个 ✓

总结

本题通过简单的奇偶性分析，将复杂的配对问题转化为基础的数学计算。算法的精髓在于：

1. 问题转化：将操作限制转化为奇偶性分类
2. 独立处理：分别处理奇数和偶数的配对
3. 公式求解：直接计算最大可配对数量

体现了数学建模在解决组合问题中的强大威力，通过深入分析问题本质，找到最简单高效的解决方案。