题解：CF1946D Birthday Gift

xyz105 · 2024-05-03 17:11:33 · 题解

来写个较其它题解更玄学一点的做法。

题目描述

给定两个整数 n,x 和长度为 n 的序列 a，求出最大的 k 使得整个序列 a 可以被分成相邻的 k 个区间 [l_1,r_1],[l_2,r_2],[l_3,r_3],\ldots,[l_k,r_k]，满足：

• 这些区间刚好覆盖 [1,n]，且没有交集。

解题思路

首先形如 (a_l\oplus a_{l+1}\oplus \ldots\oplus a_r) 的表达式让人不由得联想到前缀异或和，即设

特别地，令 s_0=0。则根据异或运算的特性，有

于是题目中最后一个条件变为：

又注意到对于任意 1\le i<k，有 r_i+1=l_{i+1}，所以 l_{i+1}-1=r_i。故上式变为：

其中 (0\oplus s_{r_1}) 实际上就是 s_{r_1}。

引理：对于两个非负整数 a,b，有 a|(a\oplus b)=a|b。

证明：

$\qquad$ 对于任意位，若 $a$ 在该位上是 $1$，则 $a|(a\oplus b)$ 在该位的值必然是 $1$。 $\qquad$ 若 $a$ 在该位上是 $0$，则 $b$ 在该位上只有为 $1$，才能使 $a|(a\oplus b)$ 在该位的值也为 $1$。 $\qquad$ 综上，$a|(a\oplus b)$ 在某一位的值是 $1$ 当且仅当 $a$ 和 $b$ 当中至少一个在该位的值也是 $1$，相当于 $a|(a\oplus b)=a|b$，证毕。

使用上述结论，上式可进一步做如下改变：

最终得出 s_{r_1}|s_{r_2}|s_{r_3}|\ldots|s_{r_k}\le x，限制为 1\le r_1<r_2<r_3<\cdots<r_k=n。

现在考虑贪心的取数过程。假设初始时所有 n 个数字（s_1,s_2,s_3,\ldots,s_n）都选，然后拆二进制位考虑（从高到低），根据 x 的限制逐步删除那些不合法的数字。假定目前选的所有数字在第 i 位上的按位与结果为 a，x 的第 i 位是 b。分类讨论：

• 若 a=0,b=0，选数情况不变。
• 若 a=0,b=1，则更低位的计算无需考虑 x 的限制。此时应立即更新答案并输出结果，否则可能会在对更低位的处理中删掉更多数字。
• 若 a=1,b=1，说明通过现在删数使得 a=0（转化为上一种情况）并更新答案也是可以的（x 的限制也满足啊）。可以对于现在选的这些数字创建一个用来满足 a=0 的“副本”（实际代码实现中不必这么真正地写）。
  • 对于“副本”的操作：把这个“副本”中所有第 i 位是 1 的数字统统删掉，并用“副本”中剩余的数字个数更新答案。注意到 r_k=n，说明最后一个数字不能删，否则该操作不合法，不应执行。
  • 对于原先的那些数字，则保持选数情况不变，进行更低一位的计算。
• 若 a=1,b=0，则不得不在现在选的这些数字上直接进行删数操作。操作过程同上述情况中对于“副本”的操作，但如果该操作不合法则直接停止计算。

这样答案就能得出来了。

参考代码

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int MAXN = 1e5 + 10;

int t, n, x, s[MAXN];

bool no[MAXN];

int main()
{
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d%d", &n, &x);
        for (int i = 1; i <= n; i++)
            scanf("%d", s + i), s[i] ^= s[i - 1];
        memset(no, 0, sizeof(bool) * (n + 5));
        int ans = -1, res = n;
        for (int i = 29; i >= 0; i--)
        {
            bool i1 = 0;
            for (int j = 1; j <= n; j++)
                if (!no[j]) i1 |= ((s[j] >> i) & 1);
            if (!i1 && ((x >> i) & 1)) {ans = max(ans, res); break;}
            if (i1 && ((x >> i) & 1) && !((s[n] >> i) & 1))
            {
                int res1 = res;
                for (int j = 1; j <= n; j++)
                    if ((s[j] >> i) & 1) res1 -= !no[j];
                ans = max(ans, res1);
            }
            if (i1 && !((x >> i) & 1))
            {
                if ((s[n] >> i) & 1) break;
                for (int j = 1; j <= n; j++)
                    if ((s[j] >> i) & 1) res -= !no[j], no[j] = 1;
            }
            if (!i) ans = max(ans, res);
        }
        printf("%d\n", ans);
    }

    return 0;
}