bzoj4245 [ONTAK2015]OR-XOR

2018-10-07 20:18:19


题意:一个长度为 $n$ 的序列,要划分为 $m$ 个区间,每个区间的花费是区间内的异或和,总花费是 $m$ 个区间花费的 $or$ ,求最小花费


首先求出异或前缀和 $b$

第 $i$ 个区间的花费就是 $b[r[i]]xorb[r[i-1]]$ ,其中 $r[i]$ 表示区间右端点

考虑最小化总花费

从高位到低位贪心,尽量使当前这一位为 $0$

某一位可以为 $0$ 的条件是: $b$ 数组中这一位为 $0$ 的数的个数不少于 $m$ 个且 $b[n]$ 的这一位为 $0$

如果这一位可以为 $0$ ,那么这一位为 $1$ 的位置都不能作为区间右端点

注意位运算的时候要加 $ll$

这里判断某一位是否为 $1$ 的时候只能用这种写法

不能把 $b[i]$ 右移 $j$ 位,否则会 $WA$

#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#define reg register
using namespace std;
typedef long long ll;
const int N=5e5+5;
int n,m;
ll b[N],ans;
bool vis[N];
inline ll read()
{
    ll x=0,w=1;
    char c=getchar();
    while (!isdigit(c)&&c!='-') c=getchar();
    if (c=='-') c=getchar(),w=0;
    while (isdigit(c))
    {
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar();
    }
    return w?x:-x;
}
int main()
{
    n=read(),m=read();
    for (reg int i=1;i<=n;i++) b[i]=b[i-1]^read();
    for (reg int j=60;~j;j--)
    {
        int cnt=0;
        for (reg int i=1;i<=n;i++)
          if (!vis[i]&&(!(b[i]&(1ll<<j)))) ++cnt;
        if (cnt>=m&&(!(b[n]&(1ll<<j))))
          {for (reg int i=1;i<=n;i++) if (b[i]&(1ll<<j)) vis[i]=1;}
        else ans|=(1ll<<j);
    }
    printf("%lld\n",ans);
    return 0;
}