2024HNCPC G - Utakotoba

直接贴码了,注释可能有误,欢迎指出

#include<bits/stdc++.h>
using namespace std;/*
注意掉操作过程其实是可逆的
swap有一种方法就是x=x^y y = x^y x = x^y,灵感来源?
所以说其实a,b数组是由基向量生成出来的,如果a数组可以变成b数组,那么他们的基向量得是等价的,既然是等价的必然可以相互转化
所以有了构造思路就是把数组变成同一组0000+基向量的形式
那么答案就是a变成基的正向过程+b变成基的逆向过程details: 
(1)对两个不同位置的数操作其实就是把一个数swap到另一个数旁边异或一下,再swap回去
*/
int n;
inline void solve(){cin>>n;vector<int>c(n+1),b(n+1);for(int i = 1;i<=n;++i) cin>>b[i];for(int i = 1;i<=n;++i) cin>>c[i];auto get=[&](vector<int> &a)->vector<pair<int,int>>{vector<int> base(20),pos(20,-1),ff(n+1,-1);//基,基的位置,位置的基(逆映射)vector<pair<int,int>> op;auto swp=[&](int x,int y)->void{op.push_back({x,y});op.push_back({y,x});op.push_back({x,y});};auto insert=[&](int x,int po)->void{for(int i = 15;i>=0;--i){if(!((x>>i)&1)) continue;if(!base[i]){base[i] = x;pos[i]=po;ff[po]=i;break;}else x^=base[i];}};auto XOR=[&](int l,int r)->void{if(l<=r){for(int i = l+1;i<=r-1;++i) swp(i,i-1);op.push_back({r-1,r});for(int i = r-2;i>=l;--i) swp(i,i+1);}else{for(int i = r;i<=l-2;++i) swp(i,i+1);op.push_back({l,l-1});for(int i = l-1;i>r;--i) swp(i,i-1);}};//插入线性基for(int i = 1;i<=n;++i) insert(a[i],i);//将线性基从高位到低位提前int l = 0;//目前基的个数for(int i = 14;i>=0;--i){if(!base[i]) continue;++l;for(int j = pos[i];j>l;--j){if(ff[j]!=-1) pos[ff[j]]=j-1;if(ff[j-1]!=-1) pos[ff[j-1]]=j;swap(ff[j],ff[j-1]);swap(a[j],a[j-1]);swp(j,j-1);}}//构造线性基,类似于高等代数里面的化成阶梯型/*1 1 0 0 1    (1)1 0 1 0 0    (2)0 1 1 1 0    (3)1 0 0 1 0    (4)0 0 0 1 1    (5)先把第一列第一行下面的1全消掉先把第二列第二行下面的1全消掉...*///整个过程是看i这个可以变成基向量元素前面不应该是1的位置把它处理掉for(int i = 1;i<=l;++i){//从高位到低位处理for(int j = 14;j>=0;--j){//从高位到低位处理if(pos[j]==i) break;if(base[j]&&((a[i]>>j)&1)){a[i]^=base[j];XOR(i,pos[j]);}}}//化成最简形式,类似于把阶梯型矩阵化成行最简形式//把第i行第j列上下的1全部消掉,因为已经是阶梯型,所以只有那些基里的1要消了for(int i = 14;i>=0;--i){for(int j = i-1;j>=0;--j){if(base[j]&&(base[i]>>j)&1){a[pos[i]]^=base[j];base[i]^=base[j];XOR(pos[i],pos[j]);}}}//把最前面的L个线性基换到最后面,将后面经过的全部位置变成0for(int i = l,r=0;i>=1;--i,++r){for(int j = i;j<n-r;++j){swp(j,j+1);swap(a[j],a[j+1]);int now = a[j];for(int k = 14;k>=0;--k){if(base[k]&&(now>>k&1)){now^=base[k];if(pos[k]==i){//刚好用的是当前这个异或操作且需要异或a[j]^=base[k];op.push_back({j,j+1});}}}}}return op;};vector<pair<int,int>>op1 = get(b);vector<pair<int,int>>op2 = get(c);reverse(op2.begin(),op2.end());cout<<op1.size()+op2.size()<<"\n";for(auto i:op1) cout<<i.first<<" "<<i.second<<"\n";for(auto i:op2) cout<<i.first<<" "<<i.second<<"\n";
}signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t=1;//cin>>t;while(t--){solve();}return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/469059.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

分享三个python爬虫案例

一、爬取豆瓣电影排行榜Top250存储到Excel文件 近年来&#xff0c;Python在数据爬取和处理方面的应用越来越广泛。本文将介绍一个基于Python的爬虫程序&#xff0c;用于抓取豆瓣电影Top250的相关信息&#xff0c;并将其保存为Excel文件。 获取网页数据的函数&#xff0c;包括以…

怎么禁止Ubuntu自动更新升级

怎么禁止Ubuntu自动更新升级 笔者在做MIT 6.S081的时候发现他给我的qemu自动更新了又卡住了&#xff0c;故关闭了自动更新 文章目录 怎么禁止Ubuntu自动更新升级一、图形化修改二、基于命令行修改配置文件的方法 一、图形化修改 1.打开设置->软件和更新->更新 2.选择自…

论文1—《基于卷积神经网络的手术机器人控制系统设计》文献阅读分析报告

论文报告&#xff1a;基于卷积神经网络的手术机器人控制系统设计 摘要 本研究针对传统手术机器人控制系统精准度不足的问题&#xff0c;提出了一种基于卷积神经网络的手术机器人控制系统设计。研究设计了控制系统的总体结构&#xff0c;并选用PCI插槽上直接内插CAN适配卡作为上…

水库大坝安全监测预警方法

一、监测目标 为了确保水库大坝的结构安全性和运行稳定性&#xff0c;我们需要采取一系列措施来预防和减少因自然灾害或其他潜在因素所引发的灾害损失。这不仅有助于保障广大人民群众的生命财产安全&#xff0c;还能确保水资源的合理利用和可持续发展。通过加强大坝的监测和维护…

赖茅:“酱香酒+羽毛球”营销理念的先驱者与领航者

前言&#xff1a;贵州赖茅酒业有限公司成立于2014年&#xff0c;由贵州茅台酒股份有限公司与中石化易捷销售有限公司强强联合&#xff0c;引入民营资本组建。2018年签约成为世界羽联首家内地官方合作伙伴&#xff0c;突破白酒企业传统模式&#xff0c;创新打造“酱香酒&#xf…

二叉搜索树的应用(了解补充)

前言 前面我们对二叉搜索树进行了讲解&#xff0c;本节内容我们将对该树的应用进行讲解&#xff0c;对二叉搜素树进行进一步的了解。 二叉搜索树key和key/value使用场景 key搜索场景 只有key作为关键码&#xff0c;结构中只需要存储key即可&#xff0c;关键码即为需要搜索到的值…

Python 爬虫运行状态监控:进度、错误与完成情况

Python 爬虫运行状态监控&#xff1a;进度、错误与完成情况 在进行大规模数据爬取时&#xff0c;监控爬虫的运行状态至关重要。通过实时监控&#xff0c;可以了解爬虫的工作进度、出现的错误以及任务完成情况。这样可以及时发现并解决问题&#xff0c;确保数据抓取任务顺利进行…

Marin说PCB之1000-BASE-T1的PCB设计总结--01

上周末小编我从耶路撒冷出差回来&#xff0c;从浦东机场回来的路上和司机师傅聊了一会天&#xff0c;司机师傅说小伙子喜欢看脱口秀不&#xff1f;我说挺喜欢的&#xff0c;之前还看过上海这边的周立波的海派脱口秀呢&#xff0c;我记得还有一个综艺节目叫做一周立波秀&#xf…

[大模型]视频生成-Sora简析

参考资料&#xff1a; Sora技术报告https://openai.com/index/video-generation-models-as-world-simulators/4分钟详细揭密&#xff01;Sora视频生成模型原理https://www.bilibili.com/video/BV1AW421K7Ut 一、概述 相较于Gen-2、Stable Diffusion、Pika等生成模型的前辈&am…

Prompt Engineering 提示工程

一、什么是提示工程&#xff08;Prompt Engineering&#xff09; Prompt 就是发给大模型的指令&#xff0c;比如讲个笑话、用 Python 编个贪吃蛇游戏等&#xff1b;大模型只接受一种输入&#xff0c;那就是 prompt。本质上&#xff0c;所有大模型相关的工程工作&#xff0c;都是…

python爬虫指南——初学者避坑篇

目录 Python爬虫初学者学习指南一、学习方向二、Python爬虫知识点总结三、具体知识点详解和实现步骤1. HTTP请求和HTML解析2. 正则表达式提取数据3. 动态内容爬取4. 数据存储5. 反爬虫应对措施 四、完整案例&#xff1a;爬取京东商品信息1. 导入库和设置基本信息2. 获取网页内容…

微搭低代码入门01变量

目录 1 变量的定义2 变量的赋值3 变量的类型4 算术运算符5 字符串的连接6 模板字符串7 检查变量的类型8 解构赋值8.1 数组的解构赋值8.2 对象的解构赋值 9 类型转换9.1 转换为字符串9.2 转换为数字9.3 转换为布尔值 总结 好些零基础的同学&#xff0c;在使用低代码的时候&#…

FPGA学习笔记#5 Vitis HLS For循环的优化(1)

本笔记使用的Vitis HLS版本为2022.2&#xff0c;在windows11下运行&#xff0c;仿真part为xcku15p_CIV-ffva1156-2LV-e&#xff0c;主要根据教程&#xff1a;跟Xilinx SAE 学HLS系列视频讲座-高亚军进行学习 从这一篇开始正式进入HLS对C代码的优化笔记 学习笔记&#xff1a;《…

每日OJ题_牛客_JZ38字符串的排列_DFS_C++_Java

目录 牛客_JZ38字符串的排列_DFS 题目解析 C代码 Java代码 牛客_JZ38字符串的排列_DFS 字符串的排列_牛客题霸_牛客网 描述&#xff1a; 输入一个长度为 n 字符串&#xff0c;打印出该字符串中字符的所有排列&#xff0c;你可以以任意顺序返回这个字符串数组。 例如输入…

markdown常用语法

&#x1f353; 简介&#xff1a;java系列技术分享(&#x1f449;持续更新中…&#x1f525;) &#x1f353; 初衷:一起学习、一起进步、坚持不懈 &#x1f353; 如果文章内容有误与您的想法不一致,欢迎大家在评论区指正&#x1f64f; &#x1f353; 希望这篇文章对你有所帮助,欢…

CSS教程(二)- CSS选择器

1. 作用 匹配文档中的某些元素为其应用样式。根据不同需求把不同的标签选出来。 2. 分类 分类 基础选择器 包含 标签选择器、ID选择器、类选择器、通用选择器等 复合选择器 包含 后代选择器、子代选择器、伪类选择器等 1 标签选择器 介绍 又称为元素选择器&#xff0c;根…

第二十周学习周报

目录 摘要abstractTheory behind GANGAN训练目标GAN训练技巧 总结 摘要 本周的学习内容是GAN的基本理论&#xff0c;在训练GAN的时候&#xff0c;Generator的目标是希望生成的数据与真实的数据越相似越好&#xff0c;而Discriminator的目标是尽量将生成的数据与真实的数据区分…

2024年CRM系统对比:国内外十大CRM热门选择

在数字化转型的大潮中&#xff0c;CRM系统是企业提升客户关系管理、优化销售流程的重要工具。本文将从系统功能、优势、劣势、总体评价四个方面&#xff0c;对2024年国内外十大热门CRM系统进行全方位对比&#xff0c;帮助企业找到最适合的CRM解决方案。 1.纷享销客CRM 系统功…

VideoChat:开源的数字人实时对话系统,支持自定义数字人的形象和音色

❤️ 如果你也关注大模型与 AI 的发展现状&#xff0c;且对大模型应用开发非常感兴趣&#xff0c;我会快速跟你分享最新的感兴趣的 AI 应用和热点信息&#xff0c;也会不定期分享自己的想法和开源实例&#xff0c;欢迎关注我哦&#xff01; &#x1f966; 微信公众号&#xff…

[CKS] TLS Secrets创建与挂载

目前的所有题目为2024年10月后更新的最新题库&#xff0c;考试的k8s版本为1.31.1 BackGround 您必须使用存储在TLS Secret中的SSL文件&#xff0c;来保护Web 服务器的安全访问。 Task 在clever-cactus namespace中为名为clever-cactus的现有Deployment创建名为clever-cactu…