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

…细节决定成败…

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