P7362 [eJOI 2020 Day2] XOR Sort
P7362 [eJOI 2020 Day2] XOR Sort
题意
给你一个长度为 \(n\) 的序列,每次操作可以将一个数异或上相邻的一个数,求将序列改为严格单调递增序列或严格单调不降序列的操作次数的操作序列。
注意,改为严格单调递增序列的数据 \(n\leq 200\) 且每个数不相同,改为严格单调不降序列的数据 \(n\leq 1000\)。
不要求操作次数最小,次数需不大于 \(40000\),元素大小小于 \(2^{20}\)。
思路
严格单调递增序列的数据实测如果改了数列很容易造成数字相同然后挂掉的情况出现。反而严格单调不降的条件用异或容易满足且数据范围大。我们考虑对数据分治。
- 严格单调递增序列
我们考虑冒泡排序的思想,每次用异或交换相邻两项,可以过第一档部分分。
考虑优化这个过程。考虑每次将一个最大的数换到序列最后的方法。设
\]
若此时 \(d\) 是最大的数,我们想把它换到最后面,设 $\oplus $ 表示二进制异或操作,我们可以先将序列变为
\]
对于 \(d\oplus e\) 后面的元素,我们将它们按顺序与前一项异或,容易发现序列变为
\]
那么我们就将 \(d\) 换到队尾去了。为了消除 \(d\) 的影响,我们将前面的元素也进行类似的操作
\]
此时对于缩小了一个长度的序列重复进行求解即可。注意每次寻找的是原数列上的最大值而非每次更新完后的值。
操作次数为 \(\frac 12\times 2n^2=n^2\)。
- 严格单调不降序列
从高位向低位考虑,每次我们仅考虑序列这一位的数,若非全 \(0\) 则一定能通过异或将其变为只剩一个 \(1\) 。从左往右考虑清零,若 \(a_i\) 该位为 \(1\),那么我们让 \(a_{i+1}\oplus a_i\) 使该位为 \(1\)(若本为 \(1\) 则不操作)。操作完后使最后一位为 \(1\),并将序列长度减 \(1\)(结尾位置前移)。
注意当有一位为全 \(0\) 的时候我们不能将序列长度缩短,因为我们保证序列单调不降的方法是后面的最高位二进制位数比前面的大,全 \(0\) 的话会导致不满足并被卡。虽然实际上该题数据没有卡这个。
实现
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cstring>
#include<cmath>
#include<utility>
using namespace std;
inline int read(){
int w=0,x=0;char c=getchar();
while(!isdigit(c))w|=c=='-',c=getchar();
while(isdigit(c))x=x*10+(c^48),c=getchar();
return w?-x:x;
}
namespace star
{
const int maxn=1005;
int n,a[maxn];
int Ans;
pair<int,int> ans[1000005];
inline void work1(){
static int b[maxn];
for(int i=1;i<=n;i++) a[i]=b[i]=read();
for(int len=n-1;~len;len--){
int x=0;
for(int i=1;i<=len+1;i++) if(b[i]>b[x]) x=i;
for(int i=1;i<=len+1 and i<n;i++) a[i]^=a[i+1],ans[++Ans]=make_pair(i,i+1);
for(int i=x;i<=len;i++) a[i+1]^=a[i],ans[++Ans]=make_pair(i+1,i),swap(b[i],b[i+1]);
for(int i=x-1;i>1;i--) a[i-1]^=a[i],ans[++Ans]=make_pair(i-1,i);
}
}
inline void work2(){
for(int i=1;i<=n;i++) a[i]=read();
for(int cnt=0,k=19;~k;k--){
bool ok=false;
for(int i=1;i<=n-cnt;i++) ok|=(a[i]>>k)&1;
if(!ok) continue;
for(int i=1;i<n-cnt;i++) if((a[i]>>k)&1){
if((a[i+1]>>k)&1^1) a[i+1]^=a[i],ans[++Ans]=make_pair(i+1,i);
a[i]^=a[i+1],ans[++Ans]=make_pair(i,i+1);
}
++cnt;
}
}
}
signed main(){
star::n=read();
if(read()==1) star::work1();
else star::work2();
printf("%d\n",star::Ans);
for(int i=1;i<=star::Ans;i++) printf("%d %d\n",star::ans[i].first,star::ans[i].second);
return 0;
}
最新文章
- IT公司的女流之辈
- mybatis generator maven插件自动生成代码
- C++中有符号/无符号数比较
- MyBatis学习之路之configuration配置
- Linux 执行ThinkPHP 文件的计划任务
- JAVA_SE复习(basic)
- LeetCode_Reverse Nodes in k-Group
- 【干货】.NET开发通用组件发布(二) 邮件发送组件
- RCTF Re300 Writeup
- 二叉搜索树Java实现(查找、插入、删除、遍历)
- [Hadoop] - TaskTracker源码分析(状态发送)
- Analyzing &#39;enq: HW - contention&#39; Wait Event (Doc ID 740075.1)
- Mybatis pageHelper.startPage(...)是物理分页
- TypeError: __init__() got an unexpected keyword argument &#39;t_command&#39;
- 激活函数--(Sigmoid,tanh,Relu,maxout)
- Mysql数据库改名
- w3school前端教程合集
- Android开发——异步任务中Activity销毁时的问题
- springmvc 事务回滚说明
- selenium测试(Java)--操作cookie(十七)
热门文章
- Python_Selenium 之以login_page为例实现对basepage封装好的方法调用和对common中公共方法的调用
- Centos7 安装 Zabbix Server 4.0
- 【NX二次开发】通过两点创建单位向量
- 一次SQL查询优化原理分析(900W+数据,从17s到300ms)
- 一次性搞清Java中的类加载问题
- Android系统Bitmap内存分配原理与优化
- 解决 ORA-12154 TNS无法解析指定的连接标识符
- salesforce零基础学习(一百零五)Change Data Capture
- WebService:CXF的JaxWsDynamicClientFactory实现调用WebService接口
- php mkdir 创建多级目录以及修改权限