Cansult's blog

即使愿望永远无法实现
我也不愿就这样放手

0%

水题笔记 [ONTAK2015] OR-XOR [贪心]

Posted on Edited on In

...细节决定成败...

注意在进行爆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了...

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**************************************************************
    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