题意
给定一个数列,确定选数顺序,假设每次取出为x,要使得ans|x 最大,并且令ans|=x,求选数顺序。
题解
我们可以建一个大根堆,设堆顶为z,判断一下z&ans是否等于0,如果是那就是要选的数,否则就将z弹出,将z-=z&ans放入堆中。
code
#include<cstdio>
#include<algorithm>
#include<queue>
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
using namespace std;
const int N=2e5+5;
typedef long long ll;
int a[N],n,tot;
ll b[40],ans,xx,yy;
struct node{
int x,y;
};
node k;
priority_queue<node> q;
bool operator < (const node &a, const node &b){
return a.x<b.x;
}
int main(){
// freopen("data.in","r",stdin);
int T;
scanf("%d",&T);
b[0]=1;
fo(i,1,30) b[i]=b[i-1]*2;
while (T--){
scanf("%d",&n);
fo(i,1,n) scanf("%d",&a[i]);
fo(i,1,n) q.push((node){a[i],a[i]});
ans=0;
tot=0;
while (tot<n) {
while (1) {
k=q.top();
q.pop();
xx=k.x;
yy=k.y;
if ((ans&xx)) {
xx-=ans&xx;
q.push((node){xx,yy});
}
else{
ans|=xx;
printf("%d ",yy);
tot++;
break;
}
}
}
printf("\n");
}
return 0;
}
原文地址:http://www.cnblogs.com/ganking/p/16793876.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性