CS Round#53 E Maxor
2024-08-25 03:06:06
题意:给你N个数,你可以从中选出两个数将它们or起来得到M,求M的最大值及得到最大值的方案数。
刚了半个小时得到了一个貌似时O(N log max(Ai)^2)的方法,想了想发现貌似只能做出第一问,但好像改一下就能搞掉第二问,等等,复杂度炸了。。。无奈之下跑去看题解,然而题解的解法看起来十分玄妙,而且是英文我并不能读懂。。。于是我就跑去翻别人的代码,看到了Blue Mary的代码,发现很短,就去研究了一下。
我的眼睛,这特么不是暴力么。。。
#include<bits/stdc++.h>
using namespace std;
int c[<<],c2[<<];
int main(){
int n,x;
for(scanf("%d",&n); n--;){
scanf("%d",&x);
c[x]++;
}
for(int i=; i<(<<); i++)c2[i] = c[i];
for(int i=; i<; i++)for(int mask=(<<)-; mask>=; mask--)
if(mask&(<<i))c2[mask-(<<i)] += c2[mask];
for(int x = (<<)-; x >= ; x--){
int b = ;long long int all = ;
do{
int A = c[b], B = c2[x-b];
if(A!=&&B!=)all += (long long int)A*B;
}while(b = (b-x)&x);
if(all){
cout << x << " " <<(all - c[x])/ <<endl;
break;
}
}
return ;
}
// By Blue Mary
我至今都不知道它为什么跑那么快。。。。
不过其中用到了一种枚举二进制子集的方法,这里就稍微提一下,就此题看来,相比于直接枚举集合后判断是否为子集,直接枚举子集还是能使程序效率大大提高的
Blue Mary用到的是这一种,是从小到大枚举:
int b=;
do{
......
}while(b=(b-s)&s);
在ssttkkl大佬的博客中,提到了另外一种,是从大到小枚举:
for(int x=s;x;x=(x-)&s){
......
}
虽然只是很小的优化,但在循环嵌套时如此枚举子集能使程序的效率翻倍提升,此题就是明证
正解我有空补上。。。
最新文章
- 直接操作 SDL_Overlay YUV叠加上的像素
- mysql处理高并发,防止库存超卖
- js的数据类型
- jQuery - 9.Ajax
- Visual Studio Code初探
- C语言每日一题之No.9
- 0c-33-@class,循环retain
- 使用Markdown编辑器写博客
- 最近整理的一些行列转换sql(有自己的,有别人的),留作记录
- TransactionScrope
- java 科学计数法表示转换
- MVC创建XML,并实现增删改
- ADXL345加速度传感器驱动
- 总结MySQL大数据量下如何进行优化
- 201621123060《JAVA程序设计》第十二周学习总结
- GlideDemo【Glide3.7.0版本的简单使用以及圆角功能】
- annotation的理解
- pycharm注册码(不断更新)
- rsync增量备份脚本
- quast-lg