首页 > 其他分享 >P10471 最大异或对 The XOR Largest Pair(01trie)

P10471 最大异或对 The XOR Largest Pair(01trie)

时间:2024-09-14 10:49:59浏览次数:10  
标签:typedef XOR 01trie int P10471 ne long vx return

#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef vector<string> VS;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
vector<int> vx;
inline int mp(int x) {return upper_bound(vx.begin(),vx.end(),x)-vx.begin();}
inline int log_2(int x) {return 31-__builtin_clz(x);}
inline int popcount(int x) {return __builtin_popcount(x);}
inline int lowbit(int x) {return x&-x;}
const int N = 3e6+10;
int idx;
int ne[N][2];
//注意01trie的i的范围是受a[i]值域的影响而非个数
void insert(int t)
{
	int p = 0;
	for(int i=30;i>=0;--i)
	{
		int x = t>>i&1;
		if(!ne[p][x]) ne[p][x] = ++idx, p = idx;
		else p = ne[p][x];
	}
}
int query(int t)
{
	int p = 0;
	int res = 0;
	for(int i=30;i>=0;--i)
	{
		int x = t>>i&1;
		if(ne[p][x^1]) res += 1<<i, p = ne[p][x^1];
		else p = ne[p][x];
	}
	return res;
}
void solve()
{
	int n;
	cin>>n;
	int maxn = 0;
	for(int i=0;i<n;++i)
	{
		int t;
		cin>>t;
		maxn = max(maxn,query(t));
		insert(t);
	}
	cout<<maxn<<'\n';
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T = 1;
	//cin>>T;
	while(T--)
	{
		solve();
	}
}

标签:typedef,XOR,01trie,int,P10471,ne,long,vx,return
From: https://www.cnblogs.com/ruoye123456/p/18413487

相关文章

  • CF1993E Xor-Grid Problem
    结论,异或,状压DP2300Link:https://codeforces.com/problemset/problem/1993/E。先考虑一维的情况。若只有一维,每次操作的结果和[AGC016D]XORReplace是一样的。对\(a_i\)进行一次操作相当于令\(a_i:=\oplus_{1\lei\len}a_i\),再对\(j\)进行一次操作相当于令\(a_j:=......
  • [ABC367G] Sum of (XOR^K or 0)
    MyBlogs[ABC367G]Sumof(XOR^Kor0)考虑求出\(ans_i\)表示选了\(m\)的倍数个数,异或和是\(i\)的方案数再统计答案。先考虑\(m=1\)怎么做。相当于是\(ans_i=[x^i]\prod_j(x^0+x^{a_j})\),这里的乘法是异或卷积。如果直接xor-FWT复杂度不如暴力。令\(F_i(x)\)表......
  • 两幅图像间的逻辑操作,与、或、非、异或:bitwise_and( ) bitwise_or( ) bitwise_not( )
    学OpenCV===============================================================================================这里额外看了下使用mask的情形 ===============================================================================================代码1#include<iostre......
  • QxOrm环境搭建以及接口编写
    1.常用ORM库比较2.QxOrm库编译集成2.1.下载地址https://www.qxorm.com/qxorm_en/home.html2.2.编译2.2.1.源码下载2.2.2.cmake编译2.2.3.打开QxOrm工程编译VisualStudio2015(v140)版本库2.2.4.编译好的库生成目录3.注册3.1.注册类其中传入的模......
  • ABC366 G - XOR Neighbors 题解
    发现题目实质上就是让你构造一组\(a_{1,2,\dots,n}\),有一些限制,要求一些\(a\)异或起来是\(0\)。看到\(n\le60\),果断列异或方程组,用异或高斯消元。具体地,有\(n\)个方程组,\(a_{i,j}\)表示第\(i\)个方程中\(j\)的系数。对于每一个变量\(i\),要把\(j>i\)的方程中的第......
  • D - Xor Sum 2
    原题链接题解异或就是不进位的加法,所以区间内,每一位最多只有一个一暴力方法:遍历每一位区间,查看异或和加和\(O(n^3)\)前缀和优化:找每个右端点合法的左端点\(O(n^2)\)利用性质优化:由于最多只有一个1,所以这样的左端点不会随着右端点的递增而递增\(O(n)\)code#include<bi......
  • ABC201E Xor Distances 题解
    ABC201EXorDistances题解题目大意给定一个带权树,求树上每两点的简单路径上的边权的异或和的和。形式化的,定义\(dis(i,j)\)为\(i\)到\(j\)的简单路径上的边权的异或和,求\(\large\sum\limits_{i=1}^n\sum\limits_{j=i+1}^n\text{dis}(i,j)\)。Solve令\(\largef(u)=......
  • [AGC052B] Tree Edges XOR
    好题,可以直接作为套路记录一下。[AGC052B]TreeEdgesXOR题目大意:给你一棵树,有奇数个点,每个边有边权\(w_i\)。每次你可以选出一条边,将和这条边的所有相邻的边都异或这条边的边权,问你能否得到最终状态(操作次数不定)。思路:首先,上来会发现每次操作影响的边十分多,肯定无法直接维......
  • [lnsyoj2246/luoguCF979D]Kuro and GCD and XOR and SUM
    题意给定集合\(S\),初始为空,进行\(q\)次修改或查询操作:修改操作将\(x\)加入集合;查询操作给定\(x,s,k\),要求找到满足\[\max_{u\inS,u+x\les,k|\gcd(u,x)}\{u\oplusx\}\]的最小的\(u\)。sol集合、异或、可查可改,可以自然地想到0/1-Trie。我们假设\(k=1\),此时不需......
  • E - Xor Sigma Problem
    原题链接题解首先,位运算很容易想到按位枚举。而这道题的关键是如何快速求区间异或和。对此,我们构建一个后缀异或数组即可,甚至这个数组可以进一步优化为cnt1和cnt0两个变量。(具体实现看code理解)code #include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;......