趣味XOR

2024-05-10 22:32
文章标签 趣味 xor

本文主要是介绍趣味XOR，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

sgu275

友情链接

1、题意：给出n个数，选出来一个子集，使得集合的异或最大！

思路：高斯消元，将给出来的数写成一行二进制，依次排下来，如题目给的排成一个矩阵如下

1011

1001

0101

然后去消元，在消元的过程中保证当前的位置的左下角矩阵全为零，即设置一个变量in表示消元到第几列，如果当前列找不到非零的元素，那么可以调到下一列，行数不变。然后消元一直到 "行数>=n或者列数>=m"停止，这里假设行数是n，列数是m，保证消元过的每一列最多只有一个1，然后最后把每一列的元素异或起来，并写成二进制，这个就是异或和最大。

上面消元的矩阵过程如下如下

1011

0010

0101

->

1011

0101

0010

->用最后一行去消元第一行

1001

0101

0010

然后就是所有列异或得到1110(2)=14(10)


ps：假入这里要求我们求出异或出来使得最大值的是哪些数，我们可以在原来矩阵的右边并上一个n行n列的单位矩阵，消元出来之后也是跟着所有列异或，得到一个二进制串，从左到右分别的第i个位分别表示选不选第i个数，然后这个二进制串就是所要求的集合的二进制表示了！


int n,m,cnt;
int a[MM][MM];
int find(int x,int in)
{for(int i=x;i<n;i++)if(a[i][in])return i;return -1;
}
void solve()
{long long x,ans=0;memset(a,0,sizeof(a));for(int i=0;i<n;i++){cin>>x;cnt=0;while(x>0){a[i][cnt++]=x&1;x>>=1;}m=max(m,cnt);}for(int i=0;i<n;i++){for(int j=0;j<m/2;j++)swap(a[i][j],a[i][m-j-1]);}//到这里都是数据的处理，即转化成矩阵for(int i=0,in=0;i<n&&in<m;i++,in++){int x;while((x=find(i,in))==-1&&in<m)in++;//找到一列有非零元素的列if(in==m)break;//找不到非零列，终止if(x!=i)for(int j=0;j<m;j++)swap(a[i][j],a[x][j]);//将非零元素提到当前行for(int j=i-1;j>=0;j--)if(a[j][in]){//当前行向下消元for(int k=0;k<m;k++)a[j][k]^=a[i][k];}for(int j=i+1;j<n;j++)if(a[j][in]){//当前行向上消元for(int k=0;k<m;k++)a[j][k]^=a[i][k];}}for(int j=0;j<m;j++)//全部列异或{int t=0;for(int i=0;i<n;i++)t^=a[i][j];if(t)ans+=1LL<<(m-j-1);}cout<<ans<<endl;
}
int main()
{while(~scanf("%d",&n))solve();return 0;
}

贴一份莫涛的代码，简洁时间复杂度也低O(n*64)，减少了消元的过程，把可以用已经有的数凑出来的数去掉，最后消元的行数剩下63，这63能生成所给的数据，然后对这63行进行异或，再用压缩优化，使复杂度降低到O(n*64)

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
void MAX_XOR(int n)
{long long base[64];memset(base,0,sizeof(base));for(int k=0;k<n;k++){long long x;scanf("%lld",&x);for(int i=62;i>=0;i--){if((x>>i)&1){if(base[i]==0){base[i]=x;break;}else x^=base[i];}}}for(int i=0;i<63;i++){for(int j=i+1;j<63;j++){if((base[j]>>i)&1){base[j]^=base[i];}}}long long ans=0;for(int i=0;i<63;i++)ans^=base[i];printf("%lld\n",ans);
}
int main()
{int n;scanf("%d",&n);MAX_XOR(n);return 0;
}

2、另一类XOR问题

Zeus 和 Prometheus 做了一个游戏，Prometheus 给 Zeus 一个集合，集合中包含了N个正整数，随后 Prometheus 将向 Zeus 发起M次询问，每次询问中包含一个正整数 S ，之后 Zeus 需要在集合当中找出一个正整数 K ，使得 K 与 S 的异或结果最大。

友情链接

对n个数建立一颗二进制前缀树，然后贪心在树上找数就行了，代码如下

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int cnt=1;
long long dp[5100000][2];
void insert(int root,long long x,int now)
{if(now<0)return ;long long &ans=dp[root][(x>>now)&1];if(ans==-1)ans=cnt++;insert(ans,x,now-1);
}
long long query(int root,long long x,long long ans,int now)
{if(now<0)return ans;long long &temp=dp[root][((x>>now)&1)^1];if(temp==-1)query(dp[root][(x>>now)&1],x,ans*2+((x>>now)&1),now-1);else query(temp,x,ans*2+(((x>>now)&1)^1),now-1);
}
int main()
{int T,Case=1;scanf("%d",&T);while(T--){cnt=1;int n,m;scanf("%d%d",&n,&m);memset(dp,-1,sizeof(dp));for(int i=0;i<n;i++){long long x;scanf("%I64d",&x);insert(0,x,32);}printf("Case #%d:\n",Case++);for(int i=0;i<m;i++){long long x;scanf("%I64d",&x);printf("%I64d\n",query(0,x,0,32));}}return 0;
}


3、给定一排数，求连续的子串使得异或和最大。

做法：令F[i,j]，表示下标是i的到下标是j的数的异或和，根据异或的性质我们可以知道F[i,j]=F[1,i-1] XOR F[1,j]，也就是在前缀F中找到一个数t，使得t XOR F[1,j]最大，这样可以转化成第二类问题

题目：LA 4682 - XOR Sum

友情链接：点击打开

以下是我的丑陋的代码：

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int cnt=1;
long long dp[4100000][2];
void insert(int root,long long x,int now)
{if(now<0)return ;long long &ans=dp[root][(x>>now)&1];if(ans==-1)ans=cnt++;insert(ans,x,now-1);
}
long long query(int root,long long x,long long ans,int now)
{if(now<0)return ans;long long &temp=dp[root][((x>>now)&1)^1];if(temp==-1)query(dp[root][(x>>now)&1],x,ans*2+((x>>now)&1),now-1);else query(temp,x,ans*2+(((x>>now)&1)^1),now-1);
}
int main()
{int T;scanf("%d",&T);while(T--){cnt=1;int n,m;long long ans=0,now=0;scanf("%d",&n);memset(dp,-1,sizeof(dp));for(int i=0;i<n;i++){long long x;scanf("%lld",&x);insert(0,now,33);now^=x;ans=max(ans,now^query(0,now,0,33));}cout<<ans<<endl;}return 0;
}

4、给定一个有n个数的数组，求这个数组的子串异或和小于k的个数

思路：同样用上面的方法，只不过在每个节点上面记录有多少个数要经过这个节点，当低位无论怎么异或都无法大于k时，这个时候返回记录的数就可以了，然后一直向下统计就是答案了

友情链接：点击打开链接


丑陋代码如下：


#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int cnt=1;
int dp[4100000][2];
int num[4100000][2];
void insert(int root,int x,int now)
{if(now<0)return ;num[root][(x>>now)&1]++;int &ans=dp[root][(x>>now)&1];if(ans==-1)ans=cnt++;insert(ans,x,now-1);
}
///返回当前树节点值和x的异或和比k小的个数
int query(int root,int x,int ans,int now,int k,int fa)
{int res=0;if(ans>=k)return 0;///重要的剪枝int first=(x>>now)&1,second=((x>>now)&1)^1;if(now<0)return (ans<k?fa:0);if(dp[root][first]!=-1){if(ans+(1<<now+1)<k)res+=num[root][first];///无论后面的异或情况如何，异或出来永远小于kelse res+=query(dp[root][first],x,ans,now-1,k,num[root][first]);}if(dp[root][second]!=-1){if(ans+(1<<now+1)<k)res+=num[root][second];///无论后面的异或情况如何，异或出来永远小于kelse res+=query(dp[root][second],x,ans+(1<<now),now-1,k,num[root][second]);}return res;
}
int main()
{int T;scanf("%d",&T);while(T--){cnt=1;int n,k,now=0;memset(dp,-1,sizeof(dp));memset(num,0,sizeof(num));///对每个节点计数scanf("%d%d",&n,&k);long long ans=0;for(int i=0;i<n;i++){int x;scanf("%d",&x);insert(0,now,25);now^=x;ans+=query(0,now,0,25,k,0);}cout<<ans<<endl;}return 0;
}


这篇关于趣味XOR的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/977741。

相关文章

Python趣味编程

Python趣味编程

文章目录 系列文章每日十练案例1：打印“Hello, World!”案例2：计算两个数的和案例3：求解输入的数字平方案例4：判断数字的奇偶性案例5：计算阶乘案例6：检查列表中的最大值案例7：列表中的元素求和案例8：反转字符串案例9：字典中的键值对遍历案例10：生成随机数 系列文章 序号直达链接表白系列1Python制作一个无法拒绝的表白界面2Python满屏飘字表白代码3
阅读更多...
趣味定时器

趣味定时器

学习完中断后，接下来都是定时中断这一巧妙的中断模式。定时器是在设定时间并且时间一到后就会响应执行设定好的事件，但其只处理一次，如同机械时钟的闹钟功能。而日常中的手机等电子设备设置闹钟后可配置为隔多久再响一次，这需要实现循环定时中断，在下面的内容中会对比说明。 在Linux Kernel中有两种常用的定时器，两者主要是精度的区别，在了解使用它们前，先了解如下几个概念：  1.节拍率（tick r
阅读更多...
趣味 | 暴走漫画的《创造1024》

趣味 | 暴走漫画的《创造1024》

点击上方“朱小厮的博客”，选择“设为星标” 回复”1024“获取独家整理的学习资料 前段时间，暴走漫画出品了一档“综艺”——《创造1024》，视频在网络上疯传，让程序员这个群体火出圈外。 让我们来看看，这个引发圈外人爆笑连连、却让程序员吐槽不止的视频究竟讲了些啥！ 首先出场的是鹅厂推送的三人程序员组合，就这样打着吊瓶来了！ 台下选手顶着厚重的黑眼圈和凌乱
阅读更多...
趣味算法------过河卒

趣味算法------过河卒

目录 ​编辑 题目描述 解题思路 具体代码 总结 问题描述： 解决方案： 代码实现： 关键点： 题目描述 棋盘上 A 点有一个过河卒，需要走到目标 B 点。卒行走的规则：可以向下、或者向右。同时在棋盘上 C 点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。 棋盘用坐标表示，A 点(0,0)  、B 点(n
阅读更多...
趣味算法------拯救阿拉德大陆

趣味算法------拯救阿拉德大陆

目录 ​编辑 题目描述： 思路解析： 具体代码： 总结： 题目描述： 此时一批勇士也随之而来，但其能力也是参差不齐，我们需要挑选出最优秀的勇士来守护这片大陆。每位勇士都有属于自己的编号，而我们现在有四张卡片里面分别标记了一个号码，当勇士的编号为其中某一张卡片中号码的倍数时说明该勇士是优秀的。目前有 n 名勇士（编号 1-n）并且告诉你卡片内的号码,请你计算出能挑选出多
阅读更多...
[oeasy]python031_[趣味拓展]unix起源_Ken_Tompson_Ritchie_multics

[oeasy]python031_[趣味拓展]unix起源_Ken_Tompson_Ritchie_multics

[趣味拓展]unix起源_Ken_Tompson_Ritchie_multics 🥋 回忆上次内容 上次 动态设置了 断点 断点 可以把代码 切成一段一段的可以 更快地调试 调试的目的 是 去除 bug 别害怕 bug 一步步 总能找到 bug这 就是 程序员基本功 调试 debug 在bug出现的时候 甚至还没有出现操作系统 那操作系统 是怎么开始有的呢？？🤔 出
阅读更多...
趣味算法------回文数

趣味算法------回文数

目录 ​编辑 前言         什么是回文数 题目描述 解题思路 具体代码 C语言代码 python代码 总结 ps 前言         什么是回文数                          回文数（Palindrome Number）是一种特殊的数字，它正读和反读都是一样的。例如，121，12321，111，和0都是回文数，而12
阅读更多...
ABC367G-Sum of (XOR^K or 0)

ABC367G-Sum of (XOR^K or 0)

第一次学会多项式的题目。 题意： n n n个数的多重集 S S S，设 S ′ ⊆ S , f ( A ) = [ ∣ A ∣ = t m , t ∈ Z ] ( X O R a i ∈ a a i ) k S' \subseteq S,f(A)=[|A| =tm,t\in Z](XOR_{a_i\in a}ai)^k S′⊆S,f(A)=[∣A∣=tm,t∈Z](XORai​∈a​ai)k
阅读更多...
E - Xor Distances

E - Xor Distances

树和 xor 有些地方 很契合🔥。。 比如树上距离。。很容易想到减去lca公共的那段。 而xor 他异或 刚好也是会抵消公共部分的。。。 题目链接 #include <bits/stdc++.h>using namespace std;#define int long long#define ll __int128_t#define ar array<int, 2>#define a
阅读更多...
buuctf [MRCTF2020]Xor

buuctf [MRCTF2020]Xor

前言：学习笔记。 32位IDA 打开。 先查找字符串 ok，反汇编不了，好吧，只能看汇编代码。 那咱用OD去做。顺便复习汇编语言 接着往下。 没看懂？那把JNZ SHORT xor.00CE10FF 给NOP掉再看看。 再走一遍。 猜测AL是否代表的是下标？ CL是对应值？不确定，再走一遍。 OK，结案，程序是对应值与对应下
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2