[LOJ#113]最大异或和
2024-08-29 21:15:52
[LOJ#113]最大异或和
试题描述
这是一道模板题。
给由 n 个数组成的一个可重集 S,求一个集合 T⊆S,使 T1 xor T2 xor … xor T|T| 最大
输入
第一行一个数 n。
第二行 n 个数,表示集合 S。
第二行 n 个数,表示集合 S。
输出
T1 xor T2 xor … xor T|T| 的最大值。
输入示例
输出示例
数据规模及约定
1≤n≤50,0≤Si≤250
题解
练一下线性基模板。
果然打错了好多地方。。。
首先在插入一个元素的时候,要注意只有最高位是 1 并且这个 1 在当前位的时候才尝试插入。
然后在最终算答案时,要从高位向地位枚举。。。
线性基的各种性质可以去 http://blog.csdn.net/qaq__qaq/article/details/53812883 学习一下。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;
#define LL long long const int BufferSize = 1 << 16;
char buffer[BufferSize], *Head, *Tail;
inline char Getchar() {
if(Head == Tail) {
int l = fread(buffer, 1, BufferSize, stdin);
Tail = (Head = buffer) + l;
}
return *Head++;
}
LL read() {
LL x = 0, f = 1; char c = Getchar();
while(!isdigit(c)){ if(c == '-') f = -1; c = Getchar(); }
while(isdigit(c)){ x = x * 10 + c - '0'; c = Getchar(); }
return x * f;
} #define maxn 55 int n;
LL bit[maxn]; int main() {
n = read();
for(int i = 1; i <= n; i++) {
LL a = read();
for(int j = maxn - 1; j; j--) if(a >> j-1 & 1) {
if(!bit[j]){ bit[j] = a; break; }
else a ^= bit[j];
}
} LL ans = 0;
for(int i = maxn - 1; i; i--) if((ans ^ bit[i]) > ans) ans ^= bit[i];
printf("%lld\n", ans); return 0;
}
我真是太 zz 了。。。
最新文章
- iOS实现用控制器作为弹框效果(modalPresentationStyle)
- 纪勇破解QQ号问题
- C#泛型代理、泛型接口、泛型类型、泛型方法
- Win10下PB停在欢迎窗口界面
- TabBarController
- POJ1351 Number of Locks(数学)
- web开发中的 emmet 效率提升工具
- 写了一个字符串的二维表: TSta
- asp.net 的脚本
- C语言 &#183; 数字三角形 &#183; 算法训练
- iTween_ValueTo函数
- 百度地图Label 样式:label.setStyle
- 基于visual Studio2013解决C语言竞赛题之0522和为素
- EasyUI - 后台管理系统 - 增加,删除,修改
- POJ 3537 Crosses and Crosses(SG/还未想完全通的一道SG)
- parseint和parsefloat总结number。隐形转换
- 使用SigbalR发送通知
- Linux下修改Oracle数据库字符集命令
- 19.3 Table 1-2.S3C2440A 289-Pin FBGA Pin Assignments (Sheet 4 of 9) (Continued)
- JS 获取链接中的参数