当前位置: 首页 > news >正文

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

思路&#xff1a; 通过题目可以得出结论 b1^b2a1 b2^b3a2 ....... bn-1^bnan-1 所以就可以得出 (b1^b2)^(b2^b3)a1^a2 b1^b3a1^a2 有因为当确定一个数的时候就可以通过异或得到其他所有的数&#xff0c;且题目所求的是一个n-1的全排列 那么求出a的前缀异或和arr之后…...

K8S容器持续Terminating无法正常关闭(sider-car容器异常,微服务容器正常)

问题 K8S上出现大量持续terminating的Pod&#xff0c;无法通过常规命令删除。需要编写脚本批量强制删除持续temminating的Pod&#xff1a;contribution-xxxxxxx。 解决 获取terminating状态的pod名称的命令&#xff1a; # 获取media命名空间下&#xff0c;名称带contributi…...

Spring 循环依赖

文章目录 内容总结循环依赖 内容总结 循环依赖 循环依赖只存在于 Spring 中, 是因为 Spring 创建 Bean 的流程中, 依赖注入阶段, 会先从单例池中找, 没有再从定义池中找, 针对定义池中找到的候选项会通过 getBean 创建其单例并缓存到单例池, 此机制导致了存在循环依赖的问题.…...

MySQL 8.0.13升级到8.0.35记录 .NET

1、修改表结构的字符集 utf8 修改成 utf8mb4 utf8_general_ci 修改成 utf8mb4_0900_ai_ci 注&#xff1a;所有地方都要替换。 否则会报错误提示&#xff1a;Character set utf8mb3 is not supported 下面是.NET环境升级遇到的问题 2、MySQL Connector Net 8.0.13 在程…...

flink udtaf 常年不能用

[FLINK-32807] when i use emitUpdateWithRetract of udtagg,bug error - ASF JIRA flink1.18发布的时候 他都显示未解决 但是文档上一直有udtaf...

路由汇总的四要点

1.是基于链路级的还是进程级的? RIP和eigrp都是基于接口的链路级汇总&#xff0c;而OSPF是基于进程的 2.汇总路由什么时候消失? 最后一条明细路由消失的时候&#xff0c;汇总路由消失。 3.汇总之后&#xff0c;汇总路由被通告&#xff0c;本地是否会产生一条指向NULL接口的…...

HashMap存值、取值及哈希碰撞原理分析

HashMap中的put()和get()的实现原理&#xff1a; map.put(k,v)实现原理 首先将k,v封装到Node对象当中&#xff08;节点&#xff09;。 然后它的底层会调用K的hashCode()方法得出hash值。 通过哈希表函数/哈希算法&#xff0c;将hash值转换成数组的下标&#xff0c;下标位置上…...

【SVN】

SVN 1 svn使用1.1 主干合并到分支1.2 分支合并到主干1.3 分支建立1.4 创建分支1.5 切换分支1.6 合并分支1.7 删除分支 2 概念理解 1 svn使用 1.1 主干合并到分支 首先&#xff0c;在本地trunk中先update一下&#xff0c;有冲突的解决冲突&#xff0c;保证trunk和repository已…...

编程语言,脚本语言

脚本语言上手快&#xff0c;快速实现一个小应用如python&#xff1b;编程语言重型&#xff0c;需复杂的设计和较长时间的开发&#xff0c;如java、c...

探索双十一:从技术角度剖析电商狂欢节

每年的11月11日&#xff0c;全球最大的在线购物狂欢节“双十一”在中国掀起了一场规模空前的消费风暴。以阿里巴巴为代表的电商平台和众多品牌商家&#xff0c;不仅为消费者提供了数以亿计的优惠商品&#xff0c;同时也将这一活动打造成了一个科技与商业完美结合的标志事件。本…...

Ubuntu LTS 坚持 10 年更新不动摇

Linux 内核开发者 Jonathan Corbet 此前在欧洲开源峰会上宣布&#xff0c;LTS 内核的支持时间将从六年缩短至两年&#xff0c;原因在于缺乏使用和缺乏支持。稳定版内核维护者 Greg Kroah-Hartman 也表示 “没人用 LTS 内核”。 近日&#xff0c;Ubuntu 开发商 Canonical 发表博…...

Python将多个相同格式的变量存储到列表中

在日常写代码过程中往往会遇到多个相同格式名称的变量需要存储到一个list。 怎么优雅地写出来呢 首先定义变量&#xff0c;然后使用列表推导式存储到列表中 # 定义变量 a_1, a_2 , # 列表推导式完成 a_list [globals()[fa_{i}] for i in range(1, 3)]...

前端字符串转数组对象实现方式-开发bug总结6

问题描述&#xff1a; 后台管理系统&#xff0c;这次投产完线上出现了个问题&#xff01;element-ui组件下拉选项框打开全部都是无数据&#xff0c;而且控制台报错&#xff0c;但是新添加的数据是正常显示的。对比了原因之后发现&#xff0c;新的数据前端传给后端的格式&#…...

99 颜色分类

颜色分类 题解1 双指针题解2 单指针 给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums &#xff0c;原地对它们进行排序&#xff0c;使得相同颜色的元素相邻&#xff0c;并按照红色、白色、蓝色顺序排列。 我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。 必须在…...

计算机视觉与深度学习 | 基于GPS/BDS多星座加权图因子优化的行人智能手机导航

===================================================== github:https://github.com/MichaelBeechan CSDN:https://blog.csdn.net/u011344545 ===================================================== 基于GPS/BDS多星座加权图因子优化的行人智能手机导航 1、引言2、相关工…...

低代码平台,业务开发的“银弹”

目录 一、为什么需要低代码平台 二、低代码平台的搭建能力 三、低代码其他能力 四、写在最后 随着互联网和信息技术的快速发展&#xff0c;各行各业都在积极拥抱数字化转型。在这个过程中&#xff0c;软件开发成为企业实现数字化转型的关键环节。然而&#xff0c;传统的软件开发…...

补偿 FIR 滤波器引入的延迟

补偿 FIR 滤波器引入的延迟 对信号进行滤波会引入延迟。这意味着相对于输入&#xff0c;输出信号在时间上有所偏移。此示例向您说明如何抵消这种影响。 有限冲激响应滤波器经常将所有频率分量延迟相同的时间量。这样&#xff0c;我们就很容易通过对信号进行时移处理来针对延迟…...

图数据库Neo4j详解

文章目录 第一章 图和Neo4j1.1 图数据库概念1.1.1 图论起源1.1.2 节点-关系及图1.1.3 图数据库1.1.4 图数据库分类1.1.4 图数据库应用场景1.1.5 与关系型数据库对比1.1.6 图数据库优势 1.2 Neo4j介绍1.2.1 Neo4j是什么1.2.2 Neo4j特点1.2.3 Neo4j的优势1.2.4 Neo4j的限制1.2.5 …...

系列一、Shiro概述

一、概述 Shiro是一款主流的Java安全框架&#xff0c;不依赖任何容器&#xff0c;可以运行在JavaSE 和 JavaEE项目中&#xff0c;它的主要作用是对访问系统的用户进行身份认证、授权、会话管理、加密等操作。 一句话&#xff1a;Shiro是一个用来解决安全管理的系统框架&#x…...

SpringCloudAlibaba——Sentinel

Sentinel也就是我们之前的Hystrix&#xff0c;而且比Hystrix功能更加的强大。Sentinel是分布式系统的流量防卫兵&#xff0c;以流量为切入点&#xff0c;从流量控制、流量路由、熔断降级等多个维度保护服务的稳定性。 Sentinel采用的是懒加载&#xff0c;这个接口被访问一次&a…...

PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建

制造业采购供应链管理是企业运营的核心环节&#xff0c;供应链协同管理在供应链上下游企业之间建立紧密的合作关系&#xff0c;通过信息共享、资源整合、业务协同等方式&#xff0c;实现供应链的全面管理和优化&#xff0c;提高供应链的效率和透明度&#xff0c;降低供应链的成…...

大语言模型如何处理长文本?常用文本分割技术详解

为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...

MODBUS TCP转CANopen 技术赋能高效协同作业

在现代工业自动化领域&#xff0c;MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步&#xff0c;这两种通讯协议也正在被逐步融合&#xff0c;形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...

反射获取方法和属性

Java反射获取方法 在Java中&#xff0c;反射&#xff08;Reflection&#xff09;是一种强大的机制&#xff0c;允许程序在运行时访问和操作类的内部属性和方法。通过反射&#xff0c;可以动态地创建对象、调用方法、改变属性值&#xff0c;这在很多Java框架中如Spring和Hiberna…...

【HTML-16】深入理解HTML中的块元素与行内元素

HTML元素根据其显示特性可以分为两大类&#xff1a;块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...

CMake 从 GitHub 下载第三方库并使用

有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...

使用 SymPy 进行向量和矩阵的高级操作

在科学计算和工程领域&#xff0c;向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能&#xff0c;能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作&#xff0c;并通过具体…...

Netty从入门到进阶(二)

二、Netty入门 1. 概述 1.1 Netty是什么 Netty is an asynchronous event-driven network application framework for rapid development of maintainable high performance protocol servers & clients. Netty是一个异步的、基于事件驱动的网络应用框架&#xff0c;用于…...

【LeetCode】算法详解#6 ---除自身以外数组的乘积

1.题目介绍 给定一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O…...

day51 python CBAM注意力

目录 一、CBAM 模块简介 二、CBAM 模块的实现 &#xff08;一&#xff09;通道注意力模块 &#xff08;二&#xff09;空间注意力模块 &#xff08;三&#xff09;CBAM 模块的组合 三、CBAM 模块的特性 四、CBAM 模块在 CNN 中的应用 一、CBAM 模块简介 在之前的探索中…...