bzoj 4976 宝石镶嵌

bzoj 4976 宝石镶嵌

传送门：www.lydsy/JudgeOnline/problem.php?id=4976

题意：

　　给n(n<=100000)个宝石，每个有个val(val<=100000)，求取(n-k(k<=100))个宝石使其OR后最大值。

题解：

　　因为是val的二进制下最多也就20位（实际上最多差不多是16,17位吧。。），对于某一位i选一个数第i为为1就行了，这样也就选20个。所以当n-k>20的时候直接或一遍所有的值输出就行啦。。

　　剩下的问题也就是给最多120个数，从中选20个使其OR后最大。这个数据量拿个set，xjb暴力一下就过了。。。（比赛的时候交的时候总感觉会超时，但是过了。。。）

 

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int maxn=1e5+100;
const double eps=1e-10;
int n,k,ans;
int a[maxn];
set<int> s[20];
int main() {
#ifdef acfreopen("in.txt" , "r" , stdin);
//    freopen("out.txt" , "w" , stdout);
#endifscanf("%d%d",&n,&k); ans=0;for(int i=1;i<=n;++i) {scanf("%d",&a[i]); ans|=a[i];}if(n-k>19) {printf("%d\n",ans); return 0;}int all=n-k;s[1].insert(a[1]);for(int i=2;i<=n;++i) {for(int j=all-1;j;--j) {for(set<int>::iterator it=s[j].begin();it!=s[j].end();++it) {s[j+1].insert(a[i]|(*it));}}s[1].insert(a[i]);}set<int>::iterator it=s[all].end(); it--;printf("%d\n",*it);return 0;
}

View Code

 

转载于:.html