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

Educational Codeforces Round 157 (Rated for Div. 2) D. XOR Construction (思维题)

题目

给定长为n-1(n<=2e5)的整数序列a,第i个数a[i](0<=a[i]<=2n)

构造一个长为n的整数序列b,满足:

1. 0到n-1在b数组中每个数恰好出现一次

2. 对于i \epsilon [1,n-1]b_{i}\bigoplus b_{i+1}=a_{i}

题目保证一定有解,有多组时可以输出任意一组

思路来源

cfAC代码

题解

a[1]=b[1]\bigoplus b[2]\\ a[2]=b[2]\bigoplus b[3]\\ ...\\ a[n-1]=b[n-1]\bigoplus b[n]\\

首先,如果对左侧前i项做一个前缀的异或和,

即可得到b[1]\bigoplus b[i]= \bigoplus_{j=1}^{i}a_{j}

再钦定b[1]=0,即可得到一组b值,满足第二个条件

但是,这组数并不一定是[0,n-1]连续的,如第二个样例:

6

1 6 4 6 1

ans:0 1 7 6 2 3

发现并不连续,然后就不会做了,最终写了个分治的O(nlogn)的乱搞

事实上,按每位考虑[0,n-1]时,0的数量一定是>=1的数量的

所以,如果0的数量小于1的数量,就将这一位翻转即可

如果右起第i位出现0的数量等于1的数量的情形,说明低位也一定都是相等的情况

[0,2^i-1]的数都出现过一遍,此时可以任意两两交换,那么不翻转即可

例如,i=0时,表示一半奇数一半偶数,

表示此时i和i^1是成对出现的,

是否翻转都不会改变当前连号的状态

代码1(性质)

// Problem: D. XOR Construction
// Contest: Codeforces - Educational Codeforces Round 157 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1895/problem/D
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<ll,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define scll(a) scanf("%lld",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N=2e5+10;
int t,n,a[N],xo;
void sol(){sci(n);//printf("m:%d\n",m);rep(i,1,n-1){sci(a[i]);a[i]^=a[i-1];}per(j,20,0){int cnt=0;rep(i,0,n-1){cnt+=(a[i]>>j&1);}if(cnt>n-cnt)xo|=(1<<j);}
}
int main(){t=1;//(t); // t=1while(t--){sol();		rep(i,0,n-1){printf("%d%c",a[i]^xo," \n"[i==n-1]);}}return 0;
}

代码2(赛中乱搞)

// Problem: D. XOR Construction
// Contest: Codeforces - Educational Codeforces Round 157 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1895/problem/D
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<ll,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define scll(a) scanf("%lld",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N=2e5+10;
int t,n,a[N],xo;
vector<int>b,c;
bool dfs(int b,vector<int>l,vector<int>r){if(SZ(l)!=SZ(r))return 0;if(!SZ(l) && !SZ(r))return 1;if(b<0)return 1;if(!SZ(l) || !SZ(r))return 0;vector<int>LL,LR,RL,RR;for(auto &v:l){if(v>>b&1)LL.pb(v);else LR.pb(v);}for(auto &v:r){if(v>>b&1)RL.pb(v);else RR.pb(v);}if(xo>>b&1){return dfs(b-1,LR,RL) && dfs(b-1,LL,RR);}if(dfs(b-1,LL,RL) && dfs(b-1,LR,RR))return 1;xo|=1<<b;return dfs(b-1,LR,RL) && dfs(b-1,LL,RR);
}
void sol(){sci(n);b.pb(0);c.pb(0);//printf("m:%d\n",m);rep(i,1,n-1){sci(a[i]);a[i]^=a[i-1];b.pb(a[i]);c.pb(i);}dfs(18,b,c);
}
int main(){t=1;//(t); // t=1while(t--){sol();		rep(i,0,n-1){printf("%d%c",a[i]^xo," \n"[i==n-1]);}}return 0;
}

相关文章:

Educational Codeforces Round 157 (Rated for Div. 2) D. XOR Construction (思维题)

题目 给定长为n-1(n<2e5)的整数序列a&#xff0c;第i个数a[i](0<a[i]<2n) 构造一个长为n的整数序列b&#xff0c;满足&#xff1a; 1. 0到n-1在b数组中每个数恰好出现一次 2. 对于&#xff0c; 题目保证一定有解&#xff0c;有多组时可以输出任意一组 思路来源 …...

【unity实战】实现类似英雄联盟的buff系统

文章目录 先来看看最终效果前言开始BUFF系统加几个BUFF测试1. 逐层消失&#xff0c;升级不重置剩余时间的BUFF2. 一次性全部消失&#xff0c;升级重置剩余时间的BUFF3. 永久BUFF&#xff0c;类似被动BUFF4. 负面BUFF&#xff0c;根据当前BUFF等级计算每秒收到伤害值&#xff0c…...

【C语言基础教程】函数指针与指针大小

文章目录 前言一、函数指针1.1 函数指针的概念1.2 三个示例代码示例1: 使用函数指针调用不同的函数示例 2: 使用函数指针实现回调函数示例 3: 使用函数指针数组 二、指针的大小2.1 前述2.2 指针大小如何决定&#xff1f;两方面理解 总结 前言 在C语言中&#xff0c;指针是一项…...

Web前端—网页制作(以“学成在线”为例)

版本说明 当前版本号[20231105]。 版本修改说明20231105初版 目录 文章目录 版本说明目录day07-学成在线01-项目目录02-版心居中03-布局思路04-header区域-整体布局HTML结构CSS样式 05-header区域-logo06-header区域-导航HTML结构CSS样式 07-header区域-搜索布局HTML结构CSS…...

Hive【Hive(八)自定义函数】

自定义函数用的最多的是单行函数&#xff0c;所以这里只介绍自定义单行函数。 Coding 导入依赖 <dependency><groupId>org.apache.hive</groupId><artifactId>hive-exec</artifactId><version>3.1.3</version></dependency>…...

linux远程桌面管理工具xrdp

一、概述 我们知道&#xff0c;我们日常通过vnc来远程管理linux图形界面&#xff0c;今天分享一工具Xrdp&#xff0c;它是一个开源工具&#xff0c;允许用户通过Windows RDP访问Linux远程桌面。 除了Windows RDP之外&#xff0c;xrdp工具还接受来自其他RDP客户端的连接&#xf…...

100天精通Python(可视化篇)——第106天:Pyecharts绘制多种炫酷桑基图参数说明+代码实战

文章目录 专栏导读一、桑基图介绍1. 桑基图是什么?2. 桑基图应用场景?二、桑基图配置选项1. 导包2. add函数3. 分层设置三、桑基图基础1. 普通桑基图2. 修改标签位置3. 修改节点布局方向4、月度开支桑基图书籍推荐专栏导读 🔥🔥本文已收录于《100天精通Python从入门到就…...

什么是OTP认证?OTP认证服务器有哪些应用场景?

OTP是一次性密码&#xff0c;即只能使用一次的密码。它基于专门的算法&#xff0c;每隔60秒生成一个不可预测的随机数字组合。这种密码的有效期仅在一次会话或交易过程中&#xff0c;因此不容易受到重放攻击。在计算器系统或其他数字设备上&#xff0c;OTP是一种只能使用一次的…...

shell_73.Linux使用新 shell 启动脚本

每次启动新 shell&#xff0c;bash shell 都会运行.bashrc 文件。①对此进行验证&#xff0c;可以使用这种方法&#xff1a;在 主目录下的.bashrc 文件中加入一条简单的 echo 语句&#xff0c;然后启动一个新 shell。 $ cat $HOME/.bashrc # .bashrc # Source global definiti…...

【领域驱动设计】聚合

从战术设计上&#xff0c;DDD 最值得借鉴的就是聚合根 什么是聚合 将实体和值对象在一致性边界之内组合聚合 这里的一致性包括 1、业务概念的完整性 2、业务规则的一致性&#xff1a;多个实体需要在一次操作中保持某种一致性&#xff08;修改 A&#xff0c;同步必须修改 B&a…...

WiFi模块在智能家居中的应用与优化

智能家居技术的迅速发展已经改变了我们对家庭的定义。WiFi模块作为智能设备连接的核心&#xff0c;扮演着连接和控制智能家居生态系统的关键角色。本文将深入研究WiFi模块在智能家居中的应用&#xff0c;同时探讨如何通过优化来提升其性能和用户体验。 1. 智能家居中WiFi模块的…...

LeetCode75——Day27

文章目录 一、题目二、题解 一、题目 933. Number of Recent Calls You have a RecentCounter class which counts the number of recent requests within a certain time frame. Implement the RecentCounter class: RecentCounter() Initializes the counter with zero r…...

P6462补刀

灵光一现,突然就做出来了 正好写一下思路过程 一开始寻思是个数论的问题,貌似需要用到扩展欧几里得,不管那么多,直接写上,接着不断缝缝补补修修改改,此处省略一小时.... 做不出来....好难受 星期天,无聊,做个题.. 突然,不对啊 这个题实际上不就是我当前打还是不打的一个选…...

Python教程---Python交互界面

当我们通过命令行来输入Python&#xff0c;所进入到的界面就是Python的交互界面 结构&#xff1a; 版本和版权声明&#xff1a; Python 3.6.5 (v3.6.5:f59c0932b4, Mar 28 2018, 16:07:46) [MSC v.1900 32 bit (Intel)] on win32 Type "help", "copyright"…...

基于计算机视觉的身份证识别系统 计算机竞赛

0 前言 &#x1f525; 优质竞赛项目系列&#xff0c;今天要分享的是 基于机器视觉的身份证识别系统 该项目较为新颖&#xff0c;适合作为竞赛课题方向&#xff0c;学长非常推荐&#xff01; &#x1f9ff; 更多资料, 项目分享&#xff1a; https://gitee.com/dancheng-sen…...

[python] logging输出到控制台(标准输出)

要将logging.info输出到控制台&#xff08;标准输出&#xff09;&#xff0c;可以使用以下代码&#xff1a; import logging# 创建一个logger对象 logger logging.getLogger(__name__)# 创建一个控制台处理器 console_handler logging.StreamHandler()# 设置控制台处理器的输…...

uniapp 离线打包 google 登录

官方文档&#xff1a; Oauth 模块 | uni小程序SDK 其中有 clientid 和反向url clientid 是 xxxx.apps.googleusercontent.com 反向url 是 com.googleusercontent.apps.xxx...

【实战Flask API项目指南】之一 概述

实战Flask API项目指南之 概述 本系列文章将带你深入探索实战Flask API项目指南&#xff0c;通过跟随小菜的学习之旅&#xff0c;你将逐步掌握Flask在实际项目中的应用。让我们一起踏上这个精彩的学习之旅吧&#xff01; 前言 小菜是一个Python编程爱好者&#xff0c;他目前…...

AD面试总结

文章目录 CK的面试1.自我介绍2.学习动机3.一天花多久时间4.兴趣爱好5.sql5.1 第二周那道题5.2 对时间盲注和布尔盲注的简单介绍5.3 盲注中可以替代sleep的替代函数 6.反序列化6.1 列举几个函数的触发时机6.2 __wakeup绕过的多种方法6.3 GC垃圾回收机制 7.死亡exit8.mysql8.1.练…...

从今年最硬科幻游戏中的思考

前言 最近有一款“完蛋&#xff0c;我被美女包围了”游戏火爆了&#xff0c;steam上一度达到排行榜第一最低也能到第八&#xff08;销量据说到了100万份&#xff09;&#xff0c;接下来分享一下自己对于这一款游戏的思考&#xff0c;如果有其他想法&#xff0c;随时可以联系沟…...

SpringBoot-17-MyBatis动态SQL标签之常用标签

文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...

23-Oracle 23 ai 区块链表(Blockchain Table)

小伙伴有没有在金融强合规的领域中遇见&#xff0c;必须要保持数据不可变&#xff0c;管理员都无法修改和留痕的要求。比如医疗的电子病历中&#xff0c;影像检查检验结果不可篡改行的&#xff0c;药品追溯过程中数据只可插入无法删除的特性需求&#xff1b;登录日志、修改日志…...

FastAPI 教程:从入门到实践

FastAPI 是一个现代、快速&#xff08;高性能&#xff09;的 Web 框架&#xff0c;用于构建 API&#xff0c;支持 Python 3.6。它基于标准 Python 类型提示&#xff0c;易于学习且功能强大。以下是一个完整的 FastAPI 入门教程&#xff0c;涵盖从环境搭建到创建并运行一个简单的…...

iPhone密码忘记了办?iPhoneUnlocker,iPhone解锁工具Aiseesoft iPhone Unlocker 高级注册版​分享

平时用 iPhone 的时候&#xff0c;难免会碰到解锁的麻烦事。比如密码忘了、人脸识别 / 指纹识别突然不灵&#xff0c;或者买了二手 iPhone 却被原来的 iCloud 账号锁住&#xff0c;这时候就需要靠谱的解锁工具来帮忙了。Aiseesoft iPhone Unlocker 就是专门解决这些问题的软件&…...

Linux简单的操作

ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...

渲染学进阶内容——模型

最近在写模组的时候发现渲染器里面离不开模型的定义,在渲染的第二篇文章中简单的讲解了一下关于模型部分的内容,其实不管是方块还是方块实体,都离不开模型的内容 🧱 一、CubeListBuilder 功能解析 CubeListBuilder 是 Minecraft Java 版模型系统的核心构建器,用于动态创…...

C++ 基础特性深度解析

目录 引言 一、命名空间&#xff08;namespace&#xff09; C 中的命名空间​ 与 C 语言的对比​ 二、缺省参数​ C 中的缺省参数​ 与 C 语言的对比​ 三、引用&#xff08;reference&#xff09;​ C 中的引用​ 与 C 语言的对比​ 四、inline&#xff08;内联函数…...

高危文件识别的常用算法:原理、应用与企业场景

高危文件识别的常用算法&#xff1a;原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件&#xff0c;如包含恶意代码、敏感数据或欺诈内容的文档&#xff0c;在企业协同办公环境中&#xff08;如Teams、Google Workspace&#xff09;尤为重要。结合大模型技术&…...

vue3+vite项目中使用.env文件环境变量方法

vue3vite项目中使用.env文件环境变量方法 .env文件作用命名规则常用的配置项示例使用方法注意事项在vite.config.js文件中读取环境变量方法 .env文件作用 .env 文件用于定义环境变量&#xff0c;这些变量可以在项目中通过 import.meta.env 进行访问。Vite 会自动加载这些环境变…...

学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2

每日一言 今天的每一份坚持&#xff0c;都是在为未来积攒底气。 案例&#xff1a;OLED显示一个A 这边观察到一个点&#xff0c;怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 &#xff1a; 如果代码里信号切换太快&#xff08;比如 SDA 刚变&#xff0c;SCL 立刻变&#…...