题解：CF1863F Divide, XOR, and Conquer

LSC666 · 2024-07-11 15:14:51 · 题解

题目传送门：CF1863F

定义

• 区间 [l, r] 合法当且仅当它可以由 [1, n] 缩小得来。

解题

想一下在大区间 [l, r] 中选择小区间 [l, k] 的条件是什么？

是 s(l, k) \ge s(k+1, r)。

试比较 a=s(l, k) 和 b=s(k+1, r) 大小。

从二进制考虑。假如 a 和 b 前面有一些数位是相同的，到了第 d 位才出现分别，由于异或运算，第 d 位自然是 s(l, r) 的最高位。那么，要使 a>b（选左边），a 的第 d 位必须是 1；如果要选右边，b 的第 d 位必须是 1 。

特殊情况：s(l, r)=0，此时 s(l, k) = s(k+1, r)，选哪边都行。

因此，选择左边区间 [l, k] 的条件是：

选右边区间同理。

用区间dp，从大区间往小推。对于每个小区间[x, y]，如果我们找到任意一个已知合法的区间 [x, r] (r>y) 或者 [l, y] (l<x)，且满足上面的条件，就可以推出 [x, y] 也是合法的。

可以把所有以l为左端点的合法区间的 highbit 信息压到一个数 hl[l] 中，把所有以r为右端点的合法区间的 highbit 信息压到一个数 hr[r] 中，全部按位或起来即可。

这样，转移方程如下，其中布尔值 f(l, r) 表示区间 [l, r] 合法性：

由于区间长度从大往小算，hl,hr只会记录比当前区间长度长的信息。

但是要注意判断 s(l, r)=0 情况，一旦计算到某个 s(l, r)=0，就标记：所有以l为左端点的区间、以r为右端点的区间都合法！（下面代码用 anyl、anyr 表示这个标记）

#include<bits/stdc++.h>
using namespace std;

#define ofor(i, a, b) for (register int i = a; i < b; i++)
#define cfor(i, a, b) for (register int i = a; i <= b; i++)
#define bfor(i, a, b) for (register int i = a; i >= b; i--)
#define set0(a) memset(a, 0, sizeof(a));
#define X 10005
typedef long long ll;

int T, n;
ll a[X];
ll sum[X]; // 异或前缀和 
ll hl[X], hr[X];
// hl[l]是二进制数，其中从右往左第d位上的数，表示：
// 所有以l为左端点的区间中，有/没有一个合法区间的异或和的最高位为d。
// hr[r]表示所有以r为右端点的区间中，……
bool anyl[X], anyr[X]; // anyl[l] = 1，表示任何以l为左端点的区间都能取 

inline ll highbit(ll x) {
    return 1ll << (63 - __builtin_clzll(x)); // 内置函数
}
inline ll xor_sum(int l,int r) {
    return sum[r] ^ sum[l - 1];
}

int main() {
    cin >> T;
    while (T--) {
        set0(hl);
        set0(hr);
        set0(anyl);
        set0(anyr);
        cin >> n;
        cfor (i, 1, n) cin >> a[i];

        cfor (i, 1, n) sum[i] = sum[i - 1] ^ a[i];

        int r;
        ll xs;
        bool f;
        bfor (len, n, 1) {
            cfor (l, 1, n - len + 1) {
                r = l + len - 1;
                xs = xor_sum(l, r);
                f = (xs & hl[l]) or (xs & hr[r]);
                if (anyl[l] or anyr[r]) f = true;
                if (len == n) f = true;
                if (len == 1) cout << f;
                // 区间dp，f表示区间[l, r]是否合法，不需要用数组存
                if (f) {
                    hl[l] |= highbit(xs), hr[r] |= highbit(xs);
                    if (xs == 0) anyl[l] = anyr[r] = true; // 如果异或和为0，那么选左边右边都可以 
                }
            }
        }
        cout << endl;
    }

    return 0;
}