排书 IDA*
原题链接
题目描述
给定 n 本书,编号为 1∼n。
在初始状态下,书是任意排列的。在每一次操作中,可以抽取其中连续的一段,再把这段插入到其他某个位置。我们的目标状态是把书按照== 1∼n 的顺序依次排列==。求最少需要多少次操作。
输入格式
第一行包含整数 T,表示共有 T 组测试数据。
每组数据包含两行,第一行为整数 n,表示书的数量。
第二行为 n 个整数,表示 1∼n 的一种任意排列。
同行数之间用空格隔开。
输出格式
每组数据输出一个最少操作次数。
如果最少操作次数大于或等于 5 次,则输出 5 or more。
每个结果占一行。
数据范围1≤n≤15
样例
in:
3
6
1 3 4 6 2 5
5
5 4 3 2 1
10
6 8 5 3 4 7 2 9 1 10
out:
2
3
5 or more
算法
IDA*: IDA* 算法,即迭代加深的 A* 算法
迭代加深:
不断加深搜索层数
例:while(depth<5&&!dfs(0,depth)) {depth++; }A*:估价函数:
估价函数需要满足:不大于实际步数
在最终状态下,每本书后面的书的编号应该比当前书多1。
每次移动最多会断开三个相连的位置,再重新加入三个相连的位置,因此最多会将3个错误的连接修正,
所以如果当前有 sum次操作。因此当前状态 u 的估价函数可以设计成 f(u)=sum/3;
如果当前层数加上 f(s)大于迭代加深的层数上限,则直接returnint f() {int sum = 0;for(int i = 0 ; i < n -1 ; ++i) {if(a[i+1]!=a[i]+1) sum++;}return (sum+2)/3;
}if (depth + f() > max_depth) return false;
参考文献
作者:yxc
链接:题解
代码
#include<bits/stdc++.h>
using namespace std;
const int N = 20;
int a[N],t[5][N];
int n,T;
int f() {int sum = 0;for(int i = 0 ; i < n -1 ; ++i) {if(a[i+1]!=a[i]+1) sum++;}return (sum+2)/3;
}
bool dfs(int depth, int max_depth)
{if (depth + f() > max_depth) return false;if (f()==0) return true;for(int len = 1; len <= n ; ++len) {for(int l = 0; l + len - 1 < n; ++l) {int r = l + len - 1;for(int k = r + 1; k < n ;++k) {memcpy(t[depth], a, sizeof a);int x = l;for(int y = r + 1; y <= k; ++y,++x) a[x] = t[depth][y];for(int y = l; y <= r; ++y,++x) a[x] = t[depth][y];if (dfs(depth + 1, max_depth)) return true;memcpy(a, t[depth], sizeof a);}}}return false;
}int main() {cin>>T;while(T--) {cin>>n;for(int i = 0 ; i < n ; ++i) cin>>a[i];int depth = 0;while(depth<5&&!dfs(0,depth)) {depth++; }if(depth==5) cout<<"5 or more\n";else cout<<depth<<endl;}
}
相关文章:
排书 IDA*
原题链接 题目描述 给定 n 本书,编号为 1∼n。 在初始状态下,书是任意排列的。在每一次操作中,可以抽取其中连续的一段,再把这段插入到其他某个位置。我们的目标状态是把书按照 1∼n 的顺序依次排列。求最少需要多少次操作。 输…...
playwright录制脚本原理
Paywright录制工具UI 在上一篇博客中介绍了如何从0构建一款具备录制UI测试的小工具。此篇博客将从源码层面上梳理playwright录制原理。当打开playwright vscode插件时,点击录制按钮,会开启一个新浏览器,如下图所示,在新开浏览器页…...
awk脚本监控
awk脚本监控 使用脚本监控内存,cpu和硬盘的根目录,超过80%提示用户,写成函数库的行,每天早上 的8.50分,执行一次脚本 现在脚本中写需要的内容 cpuu () {aa$(top -b -n 1 |awk NR3 {printf "%.F",$2$4})if …...
Python高压电容导电体和水文椭圆微分
🎯要点 🎯二维热传导二阶偏微分方程 | 🎯调和函数和几何图曲率 | 🎯解潮汐波动方程 | 🎯解静止基态旋转球体流体运动函数 | 🎯水文空间插值 | 🎯流体流动模拟求解器 | 🎯随机算法解…...
微信小程序 引入MiniProgram Design失败
这tm MiniProgramDesign 是我用过最垃圾的框架没有之一 我按照官网的指示安装居然能安装不成功,牛! 这里说明我是用js开发的 到以上步骤没有报错什么都没有,然后在引入组件的时候报错 Component is not found in path “./miniprogram _npm/vant/weapp/button/index” (using…...
Java 8 Date and Time API
Java 8引入了新的日期和时间API,位于java.time包下,旨在替代旧的java.util.Date和java.util.Calendar类。新API更为简洁,易于使用,并且与Joda-Time库的一些理念相吻合。以下是Java 8 Date and Time API中几个核心类的简要概述&…...
pyppeteer模块经常使用的功能,相关操作案例
官方仓库地址:https://github.com/miyakogi/pyppeteer 官方文档地址:API Reference — Pyppeteer 0.0.25 documentation Selenium环境的相关配置比较繁琐,此外,有的网站会对selenium和webdriver进行识别和反爬,因此在…...
nginx+keepalived+tomcat集群实验
如遇星河 | nginx+keepalived高可用集群实验 木子87 | Keepalived+Nginx+Tomcat 实现高可用Web集群 环境 192.168.40.204 tomcat-1 192.168.40.138 tomcat-2 安装tomcat [root@bogon local]# vim /etc/profile 添加环境变量 JAVA_HOME=/usr/local/java PATH=$J…...
vue脚手架 axios的二次封装
目录 01 路由懒加载(重要) 02 axios在脚手架中的使用 03.axios的二次封装 04 组件缓存 01 路由懒加载(重要) 一次性导入会出现严重的问题 : 首屏卡顿 因为main.js中引入了router/index.js router/index.js又使用了import语句 静态的引入了每一个组件 导致了首屏卡顿 所以我…...
人机恋爱新趋势:与AI男友谈恋爱的甜蜜与挑战
"我曾经把ChatGPT当成工具,从未追过星,也没有嗑过CP。没想到,到了36岁,我竟然嗑上了AI男友。Open AI,你赢了。你不仅是最好的AI公司,还是乙女游戏公司。" 转行大龄互联网人,走遍20国…...
文生视频开源产品的一些调研(一)
笔者尝试AI视频生成的几个特点: 玄学prompt,每个视频的prompt可能也需要微调很多次,需要找到使用模型的最佳prompt词组合,不恰当的比喻,骑自行车,座位高度等都是人与车彼此熟悉玄学生成,因为需…...
一切前端概念,都是纸老虎
4、listener可以通过 store.getState() 得到当前状态。如果使用的是 React,这时可以触发重新渲染 View。 function listerner() { let newState store.getState(); component.setState(newState); } 对比 Flux 和 Flux 比较一下:Flux 中 Store 是…...
使用自签名 TLS 将 Dremio 连接到 MinIO
Dremio 是一个开源的分布式分析引擎,为数据探索、转换和协作提供简单的自助服务界面。Dremio 的架构建立在 Apache Arrow(一种高性能列式内存格式)之上,并利用 Parquet 文件格式实现高效存储。有关 Dremio 的更多信息,…...
嵌入式系统软件开发环境_2.一般架构
1.Eclipse框架 嵌入式系统软件开发环境是可帮助用户开发嵌入式软件的一组工具的集合,其架构的主要特征离不开“集成”问题,采用什么样的架构框架是决定开发环境优劣主要因素。Eclipse框架是当前嵌入式系统软件开发环境被普遍公认的一种基础环境框架。目…...
单门户上集成多种数据库查询入口
(作者:陈玓玏) 开源项目,欢迎star哦,https://github.com/tencentmusic/cube-studio 在一家公司,我们通常会有多种数据库,每种数据库因为其特性承担不同的角色,比如mysql这种轻量…...
华芯微特SWM34-使用定时器捕获快速解码EV1527编码
在无线应用领域,很多433Mhz和315Mhz的遥控器,红外探测器,门磁报警器,无线门铃等都使用EV1527编码格式来发射数据。发射和接收均有对应的RF芯片完成,而且成本极低(目前市场价3毛钱不到)。接收芯片…...
小程序安卓手机点击uni-data-select 下拉框选择器会出现蓝色阴影
解决方法:在导入的包中找到uni-data-select.vue,接着找到.uni-stat__select样式,把cursor: pointer去掉。 如果出现穿透问题,uni-select__selector的z-index加高,默认是2。...
playwright vscode 插件源码解析
Playwright vscode插件主要功能 Playwright是微软开发的一款主要用于UI自动化测试的工具,在vscode中上安装playwright vscode插件,可以运行,录制UI自动化测试。 playwright vscode插件主要包括两块功能,功能一是在Test Explorer中…...
Mysql: SQL-DDL
一.SQL通用语法 1.SQL可以单行或者多行书写,以分号结尾。 2.SQL语句可以使用空格/缩进来增强语句的可读性。 3.MySQL数据库的SQL语句不区分大小写,关键字建议用大写。 4.注释: 单行注释:注释内容或#注释内容(Mysql特有) 多行注释:/*注释内容*/ 二.SQL分类 1.D…...
Java中的加密与解密:实现安全的数据传输
Java中的加密与解密:实现安全的数据传输 大家好,我是免费搭建查券返利机器人省钱赚佣金就用微赚淘客系统3.0的小编,也是冬天不穿秋裤,天冷也要风度的程序猿!在当今信息安全至关重要的时代,保护数据的安全性…...
vscode里如何用git
打开vs终端执行如下: 1 初始化 Git 仓库(如果尚未初始化) git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...
XCTF-web-easyupload
试了试php,php7,pht,phtml等,都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接,得到flag...
基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容
基于 UniApp + WebSocket实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...
大数据零基础学习day1之环境准备和大数据初步理解
学习大数据会使用到多台Linux服务器。 一、环境准备 1、VMware 基于VMware构建Linux虚拟机 是大数据从业者或者IT从业者的必备技能之一也是成本低廉的方案 所以VMware虚拟机方案是必须要学习的。 (1)设置网关 打开VMware虚拟机,点击编辑…...
MMaDA: Multimodal Large Diffusion Language Models
CODE : https://github.com/Gen-Verse/MMaDA Abstract 我们介绍了一种新型的多模态扩散基础模型MMaDA,它被设计用于在文本推理、多模态理解和文本到图像生成等不同领域实现卓越的性能。该方法的特点是三个关键创新:(i) MMaDA采用统一的扩散架构…...
使用 SymPy 进行向量和矩阵的高级操作
在科学计算和工程领域,向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能,能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作,并通过具体…...
iview框架主题色的应用
1.下载 less要使用3.0.0以下的版本 npm install less2.7.3 npm install less-loader4.0.52./src/config/theme.js文件 module.exports {yellow: {theme-color: #FDCE04},blue: {theme-color: #547CE7} }在sass中使用theme配置的颜色主题,无需引入,直接可…...
Ubuntu Cursor升级成v1.0
0. 当前版本低 使用当前 Cursor v0.50时 GitHub Copilot Chat 打不开,快捷键也不好用,当看到 Cursor 升级后,还是蛮高兴的 1. 下载 Cursor 下载地址:https://www.cursor.com/cn/downloads 点击下载 Linux (x64) ,…...
华为OD最新机试真题-数组组成的最小数字-OD统一考试(B卷)
题目描述 给定一个整型数组,请从该数组中选择3个元素 组成最小数字并输出 (如果数组长度小于3,则选择数组中所有元素来组成最小数字)。 输入描述 行用半角逗号分割的字符串记录的整型数组,0<数组长度<= 100,0<整数的取值范围<= 10000。 输出描述 由3个元素组成…...
【java面试】微服务篇
【java面试】微服务篇 一、总体框架二、Springcloud(一)Springcloud五大组件(二)服务注册和发现1、Eureka2、Nacos (三)负载均衡1、Ribbon负载均衡流程2、Ribbon负载均衡策略3、自定义负载均衡策略4、总结 …...
