sgu 275 To xor or not to xor 线性基 最大异或和
2024-08-26 14:46:31
题目链接
题意
给定\(n\)个数,取其中的一个子集,使得异或和最大,求该最大的异或和。
思路
先求得线性基。
则求原\(n\)个数的所有子集的最大异或和便可转化成求其线性基的子集的最大异或和。
因为线性基可排列成一个行简化梯形矩阵,每一行的最左边的\(1\)的位置递增,且该\(1\)所在列的其余元素全为\(0\).
故显见最大值即为将全部异或起来。
Code
#include <stdio.h>
#include <string.h>
#define maxl 60
using namespace std;
typedef long long LL;
struct LinearBasis {
LL a[maxl+1];
LinearBasis() { memset(a, 0, sizeof(a)); }
void insert(LL t) {
for (int i = maxl; i >= 0; --i) {
if (!(t >> i & 1)) continue;
if (a[i]) t ^= a[i];
else {
for (int j = 0; j < i; ++j) if (t >> j & 1) t ^= a[j];
for (int j = i+1; j <= maxl; ++j) if (a[j] >> i & 1) a[j] ^= t;
a[i] = t;
return;
}
}
}
LL sum() {
LL ret = 0;
for (int i = 0; i <= maxl; ++i) ret ^= a[i];
return ret;
}
};
int main() {
int n;
scanf("%d", &n);
LinearBasis lb;
for (int i = 0; i < n; ++i) {
LL x;
scanf("%lld", &x);
lb.insert(x);
}
printf("%lld\n", lb.sum());
return 0;
}
最新文章
- 警告: [unchecked] 对作为原始类型IScheme的成员的write(TProt ocol,T)的调用未经过检查
- windows8.1 安装Redis
- 【BZOJ1486】【HNOI2009】最小圈 分数规划 dfs判负环。
- centos7破解mariadb密码
- linux下svn的安装与配置
- [Alpha阶段]第三次Scrum Meeting
- ASUS RT-AC68U 刷梅林固件及安装***插件记录(详细)
- Repeater 实现 OnSelectedIndexChanged
- Spring MVC 返回Json数据环境记录
- hbase的api操作之过滤器
- 关于Java方法重载
- centos病毒
- 从零开始单排学设计模式「策略模式」黑铁 II
- /etc/hosts和/etc/hostname区别
- C# 中的 ConfigurationManager类引用方法
- Mock session,cookie,querystring in ASB.NET MVC
- XHR工厂的实现
- H.264 White Paper学习笔记(二)帧内预测
- virtual dom &; mvvm
- 希尔排序&mdash;&mdash;Python实现
热门文章
- Spring中注解大全和应用
- 【CodeBase】PHP立即输出结果
- 【CSS】非常简单的css实现div悬浮页面底部
- JAVA使用JDBC连接,修改MySQL数据库(比较乱)
- Python入门第一课——Python的起源、发展与前景!
- x01.xiangqi: 走动棋子
- DFS:POJ1190-生日蛋糕(基础搜索)
- linux centos6 系统优化脚本-经典
- sql中比较大小
- django 连接MYSQL时,数据迁移时报:django.db.utils.InternalError: (1366, ";Incorrect string value: &#39;\\xE9\\x97\\xAE\\xE9\\xA2\\x98&#39; for column &#39;name&#39; at row 5";)