排书 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的小编,也是冬天不穿秋裤,天冷也要风度的程序猿!在当今信息安全至关重要的时代,保护数据的安全性…...
KubeSphere 容器平台高可用:环境搭建与可视化操作指南
Linux_k8s篇 欢迎来到Linux的世界,看笔记好好学多敲多打,每个人都是大神! 题目:KubeSphere 容器平台高可用:环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...
React Native在HarmonyOS 5.0阅读类应用开发中的实践
一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强,React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 (1)使用React Native…...
《通信之道——从微积分到 5G》读书总结
第1章 绪 论 1.1 这是一本什么样的书 通信技术,说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号(调制) 把信息从信号中抽取出来&am…...
Unit 1 深度强化学习简介
Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库,例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体,比如 SnowballFight、Huggy the Do…...
Redis数据倾斜问题解决
Redis 数据倾斜问题解析与解决方案 什么是 Redis 数据倾斜 Redis 数据倾斜指的是在 Redis 集群中,部分节点存储的数据量或访问量远高于其他节点,导致这些节点负载过高,影响整体性能。 数据倾斜的主要表现 部分节点内存使用率远高于其他节…...
RabbitMQ入门4.1.0版本(基于java、SpringBoot操作)
RabbitMQ 一、RabbitMQ概述 RabbitMQ RabbitMQ最初由LShift和CohesiveFT于2007年开发,后来由Pivotal Software Inc.(现为VMware子公司)接管。RabbitMQ 是一个开源的消息代理和队列服务器,用 Erlang 语言编写。广泛应用于各种分布…...
省略号和可变参数模板
本文主要介绍如何展开可变参数的参数包 1.C语言的va_list展开可变参数 #include <iostream> #include <cstdarg>void printNumbers(int count, ...) {// 声明va_list类型的变量va_list args;// 使用va_start将可变参数写入变量argsva_start(args, count);for (in…...
MyBatis中关于缓存的理解
MyBatis缓存 MyBatis系统当中默认定义两级缓存:一级缓存、二级缓存 默认情况下,只有一级缓存开启(sqlSession级别的缓存)二级缓存需要手动开启配置,需要局域namespace级别的缓存 一级缓存(本地缓存&#…...
uniapp 集成腾讯云 IM 富媒体消息(地理位置/文件)
UniApp 集成腾讯云 IM 富媒体消息全攻略(地理位置/文件) 一、功能实现原理 腾讯云 IM 通过 消息扩展机制 支持富媒体类型,核心实现方式: 标准消息类型:直接使用 SDK 内置类型(文件、图片等)自…...
人工智能 - 在Dify、Coze、n8n、FastGPT和RAGFlow之间做出技术选型
在Dify、Coze、n8n、FastGPT和RAGFlow之间做出技术选型。这些平台各有侧重,适用场景差异显著。下面我将从核心功能定位、典型应用场景、真实体验痛点、选型决策关键点进行拆解,并提供具体场景下的推荐方案。 一、核心功能定位速览 平台核心定位技术栈亮…...
