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. 对于,
题目保证一定有解,有多组时可以输出任意一组
思路来源
cfAC代码
题解
首先,如果对左侧前i项做一个前缀的异或和,
即可得到
再钦定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的数量的情形,说明低位也一定都是相等的情况
即的数都出现过一遍,此时可以任意两两交换,那么不翻转即可
例如,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,第i个数a[i](0<a[i]<2n) 构造一个长为n的整数序列b,满足: 1. 0到n-1在b数组中每个数恰好出现一次 2. 对于, 题目保证一定有解,有多组时可以输出任意一组 思路来源 …...
【unity实战】实现类似英雄联盟的buff系统
文章目录 先来看看最终效果前言开始BUFF系统加几个BUFF测试1. 逐层消失,升级不重置剩余时间的BUFF2. 一次性全部消失,升级重置剩余时间的BUFF3. 永久BUFF,类似被动BUFF4. 负面BUFF,根据当前BUFF等级计算每秒收到伤害值,…...
【C语言基础教程】函数指针与指针大小
文章目录 前言一、函数指针1.1 函数指针的概念1.2 三个示例代码示例1: 使用函数指针调用不同的函数示例 2: 使用函数指针实现回调函数示例 3: 使用函数指针数组 二、指针的大小2.1 前述2.2 指针大小如何决定?两方面理解 总结 前言 在C语言中,指针是一项…...
Web前端—网页制作(以“学成在线”为例)
版本说明 当前版本号[20231105]。 版本修改说明20231105初版 目录 文章目录 版本说明目录day07-学成在线01-项目目录02-版心居中03-布局思路04-header区域-整体布局HTML结构CSS样式 05-header区域-logo06-header区域-导航HTML结构CSS样式 07-header区域-搜索布局HTML结构CSS…...
Hive【Hive(八)自定义函数】
自定义函数用的最多的是单行函数,所以这里只介绍自定义单行函数。 Coding 导入依赖 <dependency><groupId>org.apache.hive</groupId><artifactId>hive-exec</artifactId><version>3.1.3</version></dependency>…...
linux远程桌面管理工具xrdp
一、概述 我们知道,我们日常通过vnc来远程管理linux图形界面,今天分享一工具Xrdp,它是一个开源工具,允许用户通过Windows RDP访问Linux远程桌面。 除了Windows RDP之外,xrdp工具还接受来自其他RDP客户端的连接…...
100天精通Python(可视化篇)——第106天:Pyecharts绘制多种炫酷桑基图参数说明+代码实战
文章目录 专栏导读一、桑基图介绍1. 桑基图是什么?2. 桑基图应用场景?二、桑基图配置选项1. 导包2. add函数3. 分层设置三、桑基图基础1. 普通桑基图2. 修改标签位置3. 修改节点布局方向4、月度开支桑基图书籍推荐专栏导读 🔥🔥本文已收录于《100天精通Python从入门到就…...
什么是OTP认证?OTP认证服务器有哪些应用场景?
OTP是一次性密码,即只能使用一次的密码。它基于专门的算法,每隔60秒生成一个不可预测的随机数字组合。这种密码的有效期仅在一次会话或交易过程中,因此不容易受到重放攻击。在计算器系统或其他数字设备上,OTP是一种只能使用一次的…...
shell_73.Linux使用新 shell 启动脚本
每次启动新 shell,bash shell 都会运行.bashrc 文件。①对此进行验证,可以使用这种方法:在 主目录下的.bashrc 文件中加入一条简单的 echo 语句,然后启动一个新 shell。 $ cat $HOME/.bashrc # .bashrc # Source global definiti…...
【领域驱动设计】聚合
从战术设计上,DDD 最值得借鉴的就是聚合根 什么是聚合 将实体和值对象在一致性边界之内组合聚合 这里的一致性包括 1、业务概念的完整性 2、业务规则的一致性:多个实体需要在一次操作中保持某种一致性(修改 A,同步必须修改 B&a…...
WiFi模块在智能家居中的应用与优化
智能家居技术的迅速发展已经改变了我们对家庭的定义。WiFi模块作为智能设备连接的核心,扮演着连接和控制智能家居生态系统的关键角色。本文将深入研究WiFi模块在智能家居中的应用,同时探讨如何通过优化来提升其性能和用户体验。 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,所进入到的界面就是Python的交互界面 结构: 版本和版权声明: 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 前言 🔥 优质竞赛项目系列,今天要分享的是 基于机器视觉的身份证识别系统 该项目较为新颖,适合作为竞赛课题方向,学长非常推荐! 🧿 更多资料, 项目分享: https://gitee.com/dancheng-sen…...
[python] logging输出到控制台(标准输出)
要将logging.info输出到控制台(标准输出),可以使用以下代码: import logging# 创建一个logger对象 logger logging.getLogger(__name__)# 创建一个控制台处理器 console_handler logging.StreamHandler()# 设置控制台处理器的输…...
uniapp 离线打包 google 登录
官方文档: Oauth 模块 | uni小程序SDK 其中有 clientid 和反向url clientid 是 xxxx.apps.googleusercontent.com 反向url 是 com.googleusercontent.apps.xxx...
【实战Flask API项目指南】之一 概述
实战Flask API项目指南之 概述 本系列文章将带你深入探索实战Flask API项目指南,通过跟随小菜的学习之旅,你将逐步掌握Flask在实际项目中的应用。让我们一起踏上这个精彩的学习之旅吧! 前言 小菜是一个Python编程爱好者,他目前…...
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.练…...
从今年最硬科幻游戏中的思考
前言 最近有一款“完蛋,我被美女包围了”游戏火爆了,steam上一度达到排行榜第一最低也能到第八(销量据说到了100万份),接下来分享一下自己对于这一款游戏的思考,如果有其他想法,随时可以联系沟…...
Docker 离线安装指南
参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性,不同版本的Docker对内核版本有不同要求。例如,Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本,Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...
【杂谈】-递归进化:人工智能的自我改进与监管挑战
递归进化:人工智能的自我改进与监管挑战 文章目录 递归进化:人工智能的自我改进与监管挑战1、自我改进型人工智能的崛起2、人工智能如何挑战人类监管?3、确保人工智能受控的策略4、人类在人工智能发展中的角色5、平衡自主性与控制力6、总结与…...
JVM垃圾回收机制全解析
Java虚拟机(JVM)中的垃圾收集器(Garbage Collector,简称GC)是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象,从而释放内存空间,避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...
LLM基础1_语言模型如何处理文本
基于GitHub项目:https://github.com/datawhalechina/llms-from-scratch-cn 工具介绍 tiktoken:OpenAI开发的专业"分词器" torch:Facebook开发的强力计算引擎,相当于超级计算器 理解词嵌入:给词语画"…...
Java编程之桥接模式
定义 桥接模式(Bridge Pattern)属于结构型设计模式,它的核心意图是将抽象部分与实现部分分离,使它们可以独立地变化。这种模式通过组合关系来替代继承关系,从而降低了抽象和实现这两个可变维度之间的耦合度。 用例子…...
【网络安全】开源系统getshell漏洞挖掘
审计过程: 在入口文件admin/index.php中: 用户可以通过m,c,a等参数控制加载的文件和方法,在app/system/entrance.php中存在重点代码: 当M_TYPE system并且M_MODULE include时,会设置常量PATH_OWN_FILE为PATH_APP.M_T…...
【Linux】自动化构建-Make/Makefile
前言 上文我们讲到了Linux中的编译器gcc/g 【Linux】编译器gcc/g及其库的详细介绍-CSDN博客 本来我们将一个对于编译来说很重要的工具:make/makfile 1.背景 在一个工程中源文件不计其数,其按类型、功能、模块分别放在若干个目录中,mak…...
【FTP】ftp文件传输会丢包吗?批量几百个文件传输,有一些文件没有传输完整,如何解决?
FTP(File Transfer Protocol)本身是一个基于 TCP 的协议,理论上不会丢包。但 FTP 文件传输过程中仍可能出现文件不完整、丢失或损坏的情况,主要原因包括: ✅ 一、FTP传输可能“丢包”或文件不完整的原因 原因描述网络…...
[USACO23FEB] Bakery S
题目描述 Bessie 开了一家面包店! 在她的面包店里,Bessie 有一个烤箱,可以在 t C t_C tC 的时间内生产一块饼干或在 t M t_M tM 单位时间内生产一块松糕。 ( 1 ≤ t C , t M ≤ 10 9 ) (1 \le t_C,t_M \le 10^9) (1≤tC,tM≤109)。由于空间…...
Cursor AI 账号纯净度维护与高效注册指南
Cursor AI 账号纯净度维护与高效注册指南:解决限制问题的实战方案 风车无限免费邮箱系统网页端使用说明|快速获取邮箱|cursor|windsurf|augment 问题背景 在成功解决 Cursor 环境配置问题后,许多开发者仍面临账号纯净度不足导致的限制问题。无论使用 16…...
