https://blog.csdn.net/noone0/article/details/78289517

目前沒有題目鏈接。

題意:長度為n的序列a,選出兩個元素,其或運(yùn)算結(jié)果的最大值為多少,并求出a[i]|a[j]==mx的方案數(shù)?
n<=1e5,0<=a[i]<=2^17,m<=17.

假如最大值為mx,若x|y=mx 則x和y肯定為mx的子集.否則或運(yùn)算結(jié)果肯定不為mx.
枚舉最大值 在枚舉mx的子集x. 則此時y要包含(mx-i)這個子集.(若y比mx多出某個為1的bit位 則后面最大值還會更新.)

求個數(shù),則需要知道序列中有多少個元素有子集mask=(mx-i).

F(mask) 序列中有多少個數(shù)存在一個子集為mask,暴力O(3^m)枚舉水過..
?

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define F first #define S second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 2e5 + 5; int a[MAX],num[MAX]; int f[MAX],a[MAX]; int main() {int n;cin>>n;for(int i = 1; i<=n; i++) {scnf("%d",a+i);num[a[i]]++;}int up = 1<<17;for(int sta = 0; sta<up; sta++) {for(int i = sta; i; i = sta&(i-1)) {//枚舉子集 f[i] += num[sta];}f[0] += num[sta];}ll ans = 0;int maxx = 0;for(int sta = 0; sta<up; sta++) {ll res = 0;for(int i = sta; i; i = sta&(i-1)) {res += num[i] * f[sta-i];}res += num[0] * f[sta];res -= num[sta];if(res) {ans = res/2;maxx = sta;}}printf("%d %d\n",maxx,ans); return 0 ; }

?

總結(jié)

以上是生活随笔為你收集整理的二进制枚举子集 CS Maxor 或运算,DP(SOS)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。