BZOJ 4245: [ONTAK2015]OR-XOR

2022-11-01 12:17:24

4245: [ONTAK2015]OR-XOR

Time Limit: 10 Sec Memory Limit: 256 MB
Submit: 492 Solved: 269
[Submit][Status][Discuss]

Description

给定一个长度为n的序列a[1],a[2],...,a[n]，请将它划分为m段连续的区间，设第i段的费用c[i]为该段内所有数字的异或和，则总费用为c[1] or c[2] or ... or c[m]。请求出总费用的最小值。

Input

第一行包含两个正整数n,m(1<=m<=n<=500000)，分别表示序列的长度和需要划分的段数。

第一行包含n个整数，其中第i个数为a[i](0<=a[i]<=10^18)。

Output

输出一个整数，即总费用的最小值。

Sample Input

3 2
1 5 7

Sample Output

HINT

第一段为[1]，第二段为[5 7]，总费用为(1) or (5 xor 7) = 1 or 2 = 3。

Source

By Claris

[Submit][Status][Discuss]

从高外向低位考虑答案，如果能是0，就一定要让这一位是0，否则只能是1喽。那就在前缀异或和数组里找一找，有几个地方当前位上是0，如果能够凑出至少m个，并且最后一段（x ~ n)也可以是0，那么答案中的这一位就可以是0喽。如果我们贪心地令当前位是0，那么所以当前位是1的地方就不能在接下来的过程中作为截断点了，即使它的那一位上是0。（写个fread居然也只有Rank10，数据怎么这么大……）

 #include <bits/stdc++.h>

 /*<--- FREAD --->*/

 const int _lim = ;

 char _file[_lim], *_bit = _file;

 template <class Int>

 __inline void read(Int &_num) {

     while (*_bit < '')++_bit;

     while (*_bit >= '')_num = _num* + *_bit++ - '';

 }

 /*<--- VAR --->*/

 const int siz = ;

 typedef long long longint;

 const longint inf = (1LL << ) - ;

 int n, m;

 longint answer;

 longint a[siz];

 longint b[siz];

 /*<--- MAIN --->*/

 signed main(void) {

     fread(_file, , _lim, stdin);

     read(n); read(m);

     for (register int i = ; i <= n; ++i)

         read(a[i]), b[i] = a[i] ^ b[i - ];

     for (register longint i = 1LL << ; i; i >>= 1LL) {

         register int count = ;

         for (register int j = ; j <= n; ++j)

             if ((b[j] & i) == 0LL)++count;

         if (count >= m && (b[n] & i) == 0LL)

             for (register int j = ; j <= n; ++j)

                 b[j] = (b[j] & i) ? inf : b[j];

         else answer += i;

     }

     printf("%lld\n", answer);

 }

@Author: YouSiki

码农公寓