当前位置: 首页 > 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;随时可以联系沟…...

设计模式和设计原则回顾

设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...

【OSG学习笔记】Day 18: 碰撞检测与物理交互

物理引擎&#xff08;Physics Engine&#xff09; 物理引擎 是一种通过计算机模拟物理规律&#xff08;如力学、碰撞、重力、流体动力学等&#xff09;的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互&#xff0c;广泛应用于 游戏开发、动画制作、虚…...

简易版抽奖活动的设计技术方案

1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...

什么是库存周转?如何用进销存系统提高库存周转率?

你可能听说过这样一句话&#xff1a; “利润不是赚出来的&#xff0c;是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业&#xff0c;很多企业看着销售不错&#xff0c;账上却没钱、利润也不见了&#xff0c;一翻库存才发现&#xff1a; 一堆卖不动的旧货…...

生成 Git SSH 证书

&#x1f511; 1. ​​生成 SSH 密钥对​​ 在终端&#xff08;Windows 使用 Git Bash&#xff0c;Mac/Linux 使用 Terminal&#xff09;执行命令&#xff1a; ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" ​​参数说明​​&#xff1a; -t rsa&#x…...

【Web 进阶篇】优雅的接口设计:统一响应、全局异常处理与参数校验

系列回顾&#xff1a; 在上一篇中&#xff0c;我们成功地为应用集成了数据库&#xff0c;并使用 Spring Data JPA 实现了基本的 CRUD API。我们的应用现在能“记忆”数据了&#xff01;但是&#xff0c;如果你仔细审视那些 API&#xff0c;会发现它们还很“粗糙”&#xff1a;有…...

12.找到字符串中所有字母异位词

&#x1f9e0; 题目解析 题目描述&#xff1a; 给定两个字符串 s 和 p&#xff0c;找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义&#xff1a; 若两个字符串包含的字符种类和出现次数完全相同&#xff0c;顺序无所谓&#xff0c;则互为…...

[Java恶补day16] 238.除自身以外数组的乘积

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

网络编程(UDP编程)

思维导图 UDP基础编程&#xff08;单播&#xff09; 1.流程图 服务器&#xff1a;短信的接收方 创建套接字 (socket)-----------------------------------------》有手机指定网络信息-----------------------------------------------》有号码绑定套接字 (bind)--------------…...

10-Oracle 23 ai Vector Search 概述和参数

一、Oracle AI Vector Search 概述 企业和个人都在尝试各种AI&#xff0c;使用客户端或是内部自己搭建集成大模型的终端&#xff0c;加速与大型语言模型&#xff08;LLM&#xff09;的结合&#xff0c;同时使用检索增强生成&#xff08;Retrieval Augmented Generation &#…...