…细节决定成败…

注意在进行爆int的位运算的时候要把前面的数这样写1ll << i

懵逼的 题目

qwq

扯淡的 题解

这就是前几天说的那个题

我们发现按位贪心的时候前面贪过的位会对当前位的判定产生影响, 那我们就把前面的位带上转移(其实真正的思路来源于ARC092D)

这样 我们就可以按位贪心, 判断当前的位是否能够为$0$(具体的说就是满足分成的所有块的$xor$和都满足(xorsum & (ans + (1 << i) - 1)) == ans + (1 << i) - 1, 就可以不在第i位放$1$了)

我们发现, 在判断的时候, 如果能分成的份数$re$如果满足$m \le re$, 那么我们就可以知道当前要判断的数可以被满足(因为被异或后只可能变小不可能变大), 所以我们可以把$a[]$分成尽可能多的份, 最后判断份数和$m$的关系就可以了

我们还发现, 如果最后剩下的一份不满足当前给的数, 那么也一定不可能再消掉最后那个块里的$1$(因为如果消掉最后一块的$1$, 前面的块中就必然有一个$1$多出来)

沙茶的 代码

十分尴尬的忘记给位运算的$1$赋成LL了…

/**************************************************************
    Problem: 4245
    User: Cansult
    Language: C++
    Result: Accepted
    Time:1756 ms
    Memory:5196 kb
****************************************************************/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (500000 + 5)
#define LL unsigned long long
using namespace std;
int n, m;
LL ans, a[MAXN];
bool pd(LL x)
{
    int re = 0, i = 0;
    while (i < n)
    {
        LL dq = a[++i];
        while ((x | dq) != x && i < n)
            dq ^= a[++i];
        if ((x | dq) == x)
            ++re;
        else if (i == n)
            return false;
    }
    return re >= m;
}
void solve()
{
    for (int i = 63; i >= 0; i--)
        if (!pd((ans | ((1ll << i) - 1))))
            ans |= (1ll << i);
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%llu", &a[i]);
    solve();
    printf("%llu\n", ans);
    return 0;
}

By 沙茶 Cansult