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

ABC413 : E Reverse 2^i

大致题意 :

将一组数列用类似ST的方式分开,相邻两个大小相同的块可以反转,问最小字典序

思路 :

为了让字典序最小,我们肯定要先把1挪到最前,然后是2,3...   观察一下样例:

                                我们要先将1放在第一位,所以就将红块与绿块反转

再将黄块与蓝块反转

终于,1来到了第一位

根据上方的图可以看出,1如果要往不同的块走,就需要“绑架”它这个块中的数字一起走

而答案的输出,其实可以看作是先走左块还是右块

那为了让字典序最小,肯定就要先走包含的最小数更小的那一个啦,代码实现比较简单,主要就是ST表找最小值+dfs遍历

代码 :

#include<bits/stdc++.h>
using namespace std;
int n,a[1100000],b[110000],st[1100000][31];
int ask(int l,int r)
{int k=log2(r-l+1); return max(st[l][k],st[r-(1<<k)+1][k]);
}
void dfs(int l,int r)
{if(l==r){printf("%lld ",a[l]);return;}int mid=(l+r)>>1;if(ask(l,mid)<ask(mid+1,r)){dfs(l,mid);dfs(mid+1,r);}else{dfs(mid+1,r);dfs(l,mid);}
}
void solve()
{scanf("%d",&n);for(int i=0;i<=20;i++) for(int j=0;j<=b[n];j++) st[j][i]=1e16;for(int i=1;i<=b[n];i++) scanf("%d",&a[i]),st[i][0]=a[i];for(int j=1;j<=21;j++){for(int i=1;i+(1<<j)-1<=b[n];i++){st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);}   }dfs(1,b[n]);printf("\n");
}
int main()
{int t;scanf("%d",&t);b[0]=1;for(int i=1;i<=20;i++) b[i]=b[i-1]*2;while(t--){solve();}return 0;
}

http://www.xdnf.cn/news/1081927.html

相关文章:

  • Vue前端项目接收webSocket信息
  • Linux网络配置与故障排除完全指南
  • 介绍electron
  • 【ES6】Latex总结笔记生成器(网页版)
  • TailWind CSS Intellisense 插件在VSCode 上不生效
  • LESS/SCSS 高效主题换肤方案
  • 基于 LangChain 实现通义千问 + Tavily 搜索 Agent 的简单实践
  • 在VMware虚拟机中安装Windows 98时,Explorer提示“该程序执行了非法操作,即将关闭”的解决办法
  • 虚拟机与容器技术详解:VM、LXC、LXD与Docker
  • php协程
  • MySQL 数据库传统方式部署主从架构的实现很详细
  • React Native 亲切的组件们(函数式组件/class组件)和陌生的样式
  • 若 VSCode 添加到文件夹内右键菜单中显示(通过reg文件方式)
  • 盘式制动器的设计+说明书和CAD)【6张】+绛重
  • Redis性能优化
  • 权电阻网络DAC实现电压输出型数模转换Multisim电路仿真——硬件工程师笔记
  • 前端捕获异常的全面场景及方法
  • Linux操作系统之文件(三):缓冲区
  • 每天一个前端小知识 Day 21 - 浏览器兼容性与 Polyfill 策略
  • 【每天一个知识点】动态知识库
  • JxBrowser 8.9.0 版本发布啦!
  • chrome插件合集
  • vue/微信小程序/h5 实现react的boundary
  • 智能电动汽车系列 --- 车载软件开发思想与已有OEM现状碰撞
  • vue-39(为复杂 Vue 组件编写单元测试)
  • 设计模式(十)
  • 区块链技术核心组件及应用架构的全面解析
  • Dash 安装使用教程
  • 程序计数器(PC)是什么?
  • Linux入门篇学习——Linux 帮助手册