XOR Construction

2023-11-10 17:20
文章标签 xor construction

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

思路:

        通过题目可以得出结论
        b1^b2=a1

        b2^b3=a2

        .......

        bn-1^bn=an-1

所以就可以得出

        (b1^b2)^(b2^b3)=a1^a2

        b1^b3=a1^a2

有因为当确定一个数的时候就可以通过异或得到其他所有的数,且题目所求的是一个n-1的全排列

那么求出a的前缀异或和arr之后就得到bi=b1^arri

实际上实在寻找一个 b1 使得异或出来的所有值越小越好,所以拆位,假设所有数字的第 i位为 1 的个数大于为 0 的个数,那我们最好异或上一个 2^i,这样可以使大部分数字变小。

#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<stack>
#include<string>
#include<algorithm>
#include<unordered_map>
#include<map>
#include<bitset>
#include<cstring>
#include <unordered_set>
//#include<priority_queue>
#include<queue>
#include<deque>
#include<set>
#include<stdlib.h>
#define dbug cout<<"*****hear*****"<<endl;
#define rep(a,b,c) for(ll a=b;a<=c;a++)
#define per(a,b,c) for(ll a=b;a>=c;a--)
#define no cout<<"NO"<<endl;
#define yes cout<<"YES"<<endl;
#define endl "\n"//交互题一定要关!!!!!!!!!
#define lowbit(x) (x&-x)
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//priority_queue<int,vector<int>,greater<int> >q;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> PII;
typedef pair<long double,long double> PDD;ll  INF = 0x3f3f3f3f;
//const ll LINF=LLONG_MAX;
// int get_len(int x1,int y1,int x2,int y2)
// {
//   return (x2-x1)*(x2-x1) + (y2-y1)*(y2-y1);
// }
const ll N = 2e5+ 10;const ll mod1 =998244353;const ll mod2 =1e9+7;
// const ll hash_num = 3e9+9;
ll n,m,ca;
ll arr[N],brr[N],crr[N],drr[N];
//ll h[N],ne[N],e[N],w[N],book[N],idx;
//ll idx;// void add(ll a, ll b , ll c)
// {
//   e[idx] = b, w[idx] = c,ne[idx] = h[a], h[a] =idx ++ ; 
// }void solve()
{cin >> n;arr[0]=0;rep(i,1,n-1){cin >> arr[i];arr[i] ^= arr[i-1];}ll ans=0;rep(i,0,20){ll sum1=0;ll sum2=0;rep(j,0,n-1){if(arr[j]>>i&1)sum1++;else{sum2++;}}if(sum1>sum2)ans|=1<<i;}rep(i,0,n-1)arr[i]^=ans;rep(i,0,n-1)cout << arr[i]<<' ';
}int main()
{IOS;ll _;_=1;//scanf("%lld",&_);//cin>>_;ca=1;while(_--){solve(); ca++;}    return 0;
}

 

这篇关于XOR Construction的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/384156

相关文章

数据结构 - Codeforces Round #353 (Div. 2) D. Tree Construction

Tree Construction  Problem's Link  ---------------------------------------------------------------------------- Mean:  给定n个数,按照构造Binary Search Tree的方式来构造BST树,按顺序输出每一个非root结点的父节点的值。 analyse

【网络流】- LA5905-Pool construction

链接:我是链接啊啊啊哈哈哈 题意:  泳池最外一圈必须全搞成# 对其他的点有三种处理方式 1.放着不动 2.花费 d 把 # 变成 . 3.花费 f 把 . 变成 # 最后 # 和 . 不能相邻,要在他们之间修围墙 围墙单位边造价是b 问最小总花费 图最后变成什么样都行,只要能让花费最小  思路: 一看是修围墙,那就

poj 3352 Road Construction(边连通+tarjan+缩点)

http://poj.org/problem?id=3352 题意:简化一下原题题意,意思就是给定一个连通图,问至少要加入几条边使得整个图变成一个边连通图,即图中任意两点都有两条以上的路径(不一定直接相连)。 思路:tarjan算法,设置一个low数组,在建立深搜树的过程中,我们会得到每个节点的low值,对于low值相等的节点在同一个双连通分量中。由于在同一个边连通分量中的点的“地

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

建筑业AI的崛起The Rise of AI and Machine Learning in Construction

Apr 3, 2024 16 min read NSDT工具推荐: Three.js AI纹理开发包 - YOLO合成数据生成器 - GLTF/GLB在线编辑 - 3D模型格式在线转换 - 可编程3D场景编辑器 - REVIT导出3D模型插件 - 3D模型语义搜索引擎 - AI模型在线查看 - Three.js虚拟轴心开发包 - 3D模型在线减面 - STL模型在线切割

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

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

uva10720 - Graph Construction(Havel-Hakimi定理)

题目:uva10720 - Graph Construction(Havel-Hakimi定理) 题目大意:给出N个点,并且给出每个点的度,问能否形成简单图。 解题思路:一开始自己写想了些形成简单图的条件,例如度数之和是偶数,度数的一半也就是简单图的边不能超过n * (n - 1) / 2,每个顶点的度数都应该小于总的顶点个数,但后面发现这些只是必要的条件。后来看了题解发现大神们都

[POJ 3764] The xor-longest Path (Tire树 + 贪心)

POJ - 3674 题意是给你一个树,每条边有一个权值,求得树上一条路径,使路径上每条边权值的异或和最大 首先用一个 DFS把根到任意点的路径的异或和求出来 xorv[i] 由异或的性质可得点 u和点 v的异或和即为 xorv[u]^xorv[v] ( 根到两点 LCA的异或和会消去) 然后问题就转化成在区间内找两个值,使得他们的异或和最大 与 LightOJ - 1269一样的做法,

To xor or not to xor 高斯消元求异或

【题目】 给你n个long long范围内的整数,你可以选取1个或多个数进行异或操作,使得结果最大,求最大的结果。 【题目分析】 真是一道好题,不是真正理解高斯消元是无法做这题的。 题意:给你n个数,可以选择任意个数异或,但是要使得最后的异或值最大。 我们把每个数用二进制表示,要使得最后的异或值最大,就是要让高位尽量为1,高位能不能为1就必须用高斯消元判断了。 1. 根据数的二进制表示,建立