首页 > 代码库 > 【BZOJ4245】[ONTAK2015]OR-XOR 贪心
【BZOJ4245】[ONTAK2015]OR-XOR 贪心
【BZOJ4245】[ONTAK2015]OR-XOR
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
3
HINT
第一段为[1]，第二段为[5 7]，总费用为(1) or (5 xor 7) = 1 or 2 = 3。
题解：首先我们肯定要贪心来搞，我们肯定是切的次数越少越好，如果我们想让第i位为0，那么需要切出来的每一段的第i位xor起来都是0
从大到小枚举第i位，如果第i位为1的数的个数为奇数，那么我们无论怎么切答案的第i位肯定都是1，所以不管；如果第i位为1的数的个数为偶数，那么我们将他们两两配对，每对的中间肯定是不能被切过的，剩余位置切不切无所谓。所以我们统计出不能切的数量sum，如果sum+m<=n-1那么这些位置我们就都不切，否则答案的第i位只能是1，切不切我们不管。
#include <cstdio> #include <cstring> #include <iostream> using namespace std; const int maxn=500010; typedef long long ll; int n,m,sum,tot; ll ans; ll v[maxn]; int s[maxn]; int main() { scanf("%d%d",&n,&m); int i,flag=0; ll j; for(i=1;i<=n;i++) { scanf("%lld",&v[i]); } for(j=1ll<<62;j;j>>=1) { for(sum=0,i=1;i<=n;i++) if(v[i]&j) sum++; if(sum&1) ans^=j; else { for(flag=sum=0,i=1;i<n;i++) { if(v[i]&j) flag^=1; s[i]+=flag,sum+=(s[i]==1)&flag; } if(sum+tot+m>n) { ans^=j; for(flag=sum=0,i=1;i<n;i++) { if(v[i]&j) flag^=1; s[i]-=flag; } } else tot+=sum; } } printf("%lld",ans); return 0; }
【BZOJ4245】[ONTAK2015]OR-XOR 贪心
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。