小众但惊艳的公司名称,seo优化工具的种类,编程培训网站,wordpress页面编辑题意#xff1a;给你N个数#xff0c;你可以从中选出两个数将它们or起来得到M#xff0c;求M的最大值及得到最大值的方案数。 刚了半个小时得到了一个貌似时O(N log max(Ai)^2)的方法#xff0c;想了想发现貌似只能做出第一问#xff0c;但好像改一下就能搞掉第二问#…题意给你N个数你可以从中选出两个数将它们or起来得到M求M的最大值及得到最大值的方案数。 刚了半个小时得到了一个貌似时O(N log max(Ai)^2)的方法想了想发现貌似只能做出第一问但好像改一下就能搞掉第二问等等复杂度炸了。。。无奈之下跑去看题解然而题解的解法看起来十分玄妙而且是英文我并不能读懂。。。于是我就跑去翻别人的代码看到了Blue Mary的代码发现很短就去研究了一下。 我的眼睛这特么不是暴力么。。。 #includebits/stdc.h
using namespace std;
int c[117],c2[117];
int main(){int n,x;for(scanf(%d,n); n--;){scanf(%d,x);c[x];}for(int i0; i(117); i)c2[i] c[i];for(int i0; i17; i)for(int mask(117)-1; mask0; mask--)if(mask(1i))c2[mask-(1i)] c2[mask];for(int x (117)-1; x 0; x--){int b 0;long long int all 0;do{int A c[b], B c2[x-b];if(A!0B!0)all (long long int)A*B;}while(b (b-x)x);if(all){cout x (all - c[x])/2 endl;break;}}return 0;
}
// By Blue Mary 我至今都不知道它为什么跑那么快。。。。 不过其中用到了一种枚举二进制子集的方法这里就稍微提一下就此题看来相比于直接枚举集合后判断是否为子集直接枚举子集还是能使程序效率大大提高的 Blue Mary用到的是这一种是从小到大枚举 int b0;
do{......
}while(b(b-s)s); 在ssttkkl大佬的博客中提到了另外一种是从大到小枚举 for(int xs;x;x(x-1)s){......
} 虽然只是很小的优化但在循环嵌套时如此枚举子集能使程序的效率翻倍提升此题就是明证 正解我有空补上。。。转载于:https://www.cnblogs.com/NINGLONG/p/7693520.html
