「NOIP模拟赛」“与”
题目描述：
给你一个长度为n的序列A，请你求出一对Ai，Aj（1<=i<j<=n）使Ai“与”Aj最大。
Ps：“与”表示位运算and，在c++中表示为&。
输入描述：
第一行为n。接下来n行，一行一个数字表示Ai。
输出描述：
输出最大的Ai“与”Aj的结果。
样例输入：
3
8
10
2
样例输出：
8
样例解释：
8 and 10 = 8
8 and 2 = 0
10 and 2 = 2
数据范围：
20%的数据保证n<=5000
100%的数据保证 n<=3*10^5，0<=Ai<=10^9
题解
从最高位开始，如有大等于2个数该位为1，则该位为0的数全部删除，否则跳过该位
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<set> #include<ctime> #include<queue> #include<cmath> #include<vector> #include<algorithm> #include<map> #define ll long long #define inf 2147483647 using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int bin[35]; int n,ans,mx; int a[300005],b[300005][35]; bool del[300005]; int main() { bin[0]=1;for(int i=1;i<=30;i++)bin[i]=bin[i-1]<<1; n=read(); for(int i=1;i<=n;i++) { a[i]=read(); for(int j=0;j<=30;j++) if(a[i]&bin[j])b[i][j]=1; } if(n<=5000) { for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(i!=j)mx=max(mx,a[i]&a[j]); printf("%d\n",mx); return 0; } for(int i=30;i>=0;i--) { int cnt=0; for(int j=1;j<=n;j++) if(!del[j]&&b[j][i])cnt++; if(cnt>=2) { for(int j=1;j<=n;j++) if(!b[j][i])del[j]=1; ans+=bin[i]; } } printf("%d\n",ans); return 0; } |
计数器 9863477
OI 课件=>
OI 课件=>
数据太弱了，两个最大值取and就可以过