【BZOJ-4245】OR-XOR 按位贪心
4245: [ONTAK2015]OR-XOR
Time Limit: 10 Sec Memory Limit: 256 MBSubmit: 486 Solved: 266
[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 21 5 7
Sample Output
3HINT
第一段为[1]，第二段为[5 7]，总费用为(1) or (5 xor 7) = 1 or 2 = 3。
Source
By Claris
Solution
按位贪心。
首先预处理出前缀异或和，然后对这些异或和分成M段，考虑按位or运算的性质，当前位存在1即为1，所以，贪心的看当前位是否能只取M个0，如果可以则当前位为0，否则在答案中or上$2^{i}$即可。
这么做显然应该按数位从高到低枚举，还需要注意的地方就是，并不是当前位能取M个0当前位就可以选0，同时应该满足第N个数的当前位也必须为0，这里很容易遗漏。
在贪心的把当前位选成0后，要将当前位为1的数打上标记，表示低位不能选此数。
Code
#include#include #include #include #include using namespace std; #define LL long long inline LL read() {LL x=0,f=1; char ch=getchar();while (ch<'0' || ch>'9') {if (ch=='-') f=-1; ch=getchar();}while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}return x*f; } #define MAXN 500010 int N,M,d[MAXN][65],visit[MAXN]; LL a[MAXN],sum[MAXN],ans; void Get(LL x,int dx[]) {int tot=0; while (x) dx[tot++]=x%2,x/=2;} int main() {N=read(),M=read();for (int i=1; i<=N; i++) a[i]=read(),sum[i]=sum[i-1]^a[i];for (int i=1; i<=N; i++) Get(sum[i],d[i]);for (int i=62; i>=0; i--){int tot=0;for (int j=1; j<=N; j++)if (!visit[j] && !d[j][i]) tot++;if (tot>=M && !d[N][i]) for (int j=1; j<=N; j++) if (d[j][i]) visit[j]=1; else;else ans|=(1LL<<i);}printf("%lld\n",ans);return 0; }
转载于:https://www.cnblogs.com/DaD3zZ-Beyonder/p/6130881.html
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！