CSU 1216异或最大值
程序员文章站
2022-10-04 16:04:11
Description 给定一些数,求这些数中两个数的异或值最大的那个值 Input 多组数据。第一行为数字个数n,1 Hint Source CSGrandeur的数据结构习题 异或运算符(^ 也叫xor(以后做题会遇到xor,就是异或)) 规则:0^0 = 0,0^1=1,1^0=1,1^1=0 ......
Description
给定一些数,求这些数中两个数的异或值最大的那个值
Input
多组数据。第一行为数字个数n,1 <= n <= 10 ^ 5。接下来n行每行一个32位有符号非负整数。
Output
任意两数最大异或值
Sample Input
3
3
7
9
Sample Output
14
Hint
Source
CSGrandeur的数据结构习题
异或
异或运算符(^ 也叫xor(以后做题会遇到xor,就是异或))
规则:0^0 = 0,0^1=1,1^0=1,1^1=0 参加位运算的两位只要相同为0,不同为1
例子:3^5 = 6(00000011^00000101=00000110)
暴力(不用说)
#include <iostream> #include <algorithm> #include <cstdio> using namespace std; const int maxN = 1e5 + 7; int a[maxN]; int main() { int n; scanf("%d",&n); for(int i = 1;i <= n;++ i) { scanf("%d",a[i]); } int maxn = 0; for(int i = 1;i < n;++ i) { for(int j = i + 1;j <= n;++ j) { maxn = max(maxn,a[i] xor a[j]); } } printf("%d",maxn); }
正解:我们可以发现异或的一些性质,不同为1,根据等比数列求和,等比数列求和
$2^1 + 2^2 + 2^3 + 2^4 < 2^5 $
证明: 设$2^1 + 2^2 + 2^3 + 2^4$为S,那么$2S = 2^2 + 2^3 + 2^4 + 2^5 - S$;
等于$2^5 - 1 < 2^5 $
为什么要涉及到这个呢,因为我们要贪心的选取,一定要看看有没有特殊情况.
我们从高位开始选择与其不同的二进制位.就Ok了.
code
#include <iostream> #include <algorithm> #include <cstdio> #include <cstring> #define ll long long using namespace std; const int maxN = 1e5 + 7; int a[maxN]; int son[maxN * 20][3],cnt; void init() { memset(son,0,sizeof(son)); cnt = 0; return; } void build(ll a) { int now = 0; for(int i = 32;i >= 0;-- i) { int qwq = (a >> i & 1); if( !son[now][qwq] )son[now][qwq] = ++ cnt; now = son[now][qwq]; } } ll find(ll a) { ll res = 0,now = 0; for(int i = 32;i >= 0;-- i) { bool tmp = ((a >> i & 1) ^ 1); if(son[now][tmp]) now = son[now][tmp],res = res | (1LL << i); else now = son[now][tmp ^ 1]; } return res; } int main() { int n; while(~scanf("%d", &n)) { init(); for(int i = 1;i <= n;++ i) scanf("%d",&a[i]); for(int i = 1;i <= n;++ i) build(a[i]); ll Ans = 0; for(int i = 1;i <= n;++ i) { Ans = max(Ans,find(a[i])); } printf("%lld\n",Ans);//一定要注意:换行!!!! } }
上一篇: QT 启动shell脚本
下一篇: CSS进阶