题目内容
小红开发了一个大模型AI1,小蓝开发了一个大模型AI2。为了测试谁的大模型更强大,他们决定进行一场AI对战,对战规则如下:
- AI1和AI2各自拥有一个模型参数x和y。
- 裁判在比赛前给定一个区间[l,r],两个大模型需要分别选择一个数a和b,满足l≤a,b≤r(注意:a可以等于b)。
解题思路
异或与最大化
异或运算满足对每一位独立影响的性质,要在区间 [l, r] 中选择一个数 a 使得 x⊕a 最大,可从最高位到最低位逐位“贪心”决策:
- 对第 i 位,观察 x 在该位的值 xi。若想让异或结果该位尽可能为 1,应令 ai=xi⊕1;否则令 ai=xi。
- 但直接取“相反位”可能会导致 a 跳出区间 [l, r],需维护两个状态:
gt
:已构造的高位前缀是否严格大于 l 的前缀;
lt
:已构造的高位前缀是否严格小于 r 的前缀。
- 若
gt
为假,则新位 ai 需满足 ai≥li;若 lt
为假,则需满足 ai≤ri。二者都满足才可取“理想”ai=xi⊕1,否则退而求其次取 ai=xi。
- 每位决策后,根据 ai 与 li,ri 的比较更新
gt
,lt
。