双向BFS
1034 Number Game
分数 35
作者 陈越
单位 浙江大学
A number game is to start from a given number A, and to reach the destination number B by a sequence of operations.
For the current number X, there are 3 types of operations:
X=X+1
X=X−1
X=X×N
Your job is to find the minimum number of steps required to reach B from A.
Input Specification:
Each input file contains several test cases. The first line gives a positive integer K (≤10) which is the total number of cases. For each case, three integers are given: A, B and N, where −10
5
≤A,B≤10
5
and 1<N<10. All the numbers in a line are separated by a space.
Output Specification:
For each test case, print in a line the minimum number of steps required to reach B from
创建两个队列和两个哈希表
queue<string> que1;
queue<string> que2;
unordered_map da<string,int> da1;
unordered_map db <string,int> db2;
(25)分 双向bfs
还能怎么优化呢? 请赐教
#include <bits/stdc++.h>
using namespace std;
const int K = 20;
int k;int extend(queue<int>& que,int N,map<int,int>& set_1,map<int,int>& set_2,bool temp,int d){int len = que.size();int ans = 0xffffffff;while(len--){int top = que.front();que.pop();if(set_1.find(top+1) == set_1.end()){set_1[top+1] = d;que.push(top+1);if(set_2.find(top+1) != set_2.end()){ans = max(d + set_2[top+1],ans);}}if(set_1.find(top-1) == set_1.end()){set_1[top-1] = d;que.push(top-1);if(set_2.find(top-1) != set_2.end()){ans = max(d+set_2[top-1],ans);}}if(temp == true){if(set_1.find(top*N) == set_1.end()){set_1[top*N] = d;que.push(top*N);if(set_2.find(top*N) != set_2.end()){ans = min(set_2[top*N] + d,ans);}}}else{if(N != 0 && top % N == 0){if(set_1.find(top/N) == set_1.end()){set_1[top/N] = d;que.push(top/N);if(set_2.find(top/N) != set_2.end()){ans = min(set_2[top/N]+d,ans);}}}}}return ans;
}
int bfs(int s,int e,int n){queue<int> que1;queue<int> que2;map<int,int> set1;map<int,int> set2;que1.push(s);set1[s] = 0;que2.push(e);set2[e] = 0;if(s == e){return 0;}int d1 = 0;int d2 = 0;while(que1.size() && que2.size()){if(que1.size() < que2.size()){d1++;int t = extend(que1,n,set1,set2,true,d1);if(t != 0xffffffff){//cout<<d1<<" "<<d2<<endl;return t;}}else{d2++;int t = extend(que2,n,set2,set1,false,d2);if(t != 0xffffffff){// cout<<d1<<" "<<d2<<endl;return t;}}}return -1;
}
int main(){cin>>k;while(k--){int s,e,n;cin>>s>>e>>n;int a = bfs(s,e,n);cout<<a<<endl;}
}
相关文章:
双向BFS
1034 Number Game 分数 35 作者 陈越 单位 浙江大学 A number game is to start from a given number A, and to reach the destination number B by a sequence of operations. For the current number X, there are 3 types of operations: XX1 XX−1 XXN Your job is to f…...
数据艺术:精通数据可视化的关键步骤
数据可视化是将复杂数据转化为易于理解的图表和图形的过程,帮助我们发现趋势、关联和模式。同时数据可视化也是数字孪生的基础,本文小编带大家用最简单的话语为大家讲解怎么制作一个数据可视化大屏,接下来跟随小编的思路走起来~ 1.数据收集和…...
MySQL 是如何实现事务的四大特性的?
分析&回答 如果你不知道事务更不知道四大特性请先看看:说说什么是事务 原子性 语句要么都执行,要么都不执行,是事务最核心的特性,事务本身来说就是以原子性来定义的,实现主要是基于undo log undo logÿ…...
python实现zscore归一化和minmax标准化
zscore归一化: minmax from sklearn import preprocessing from sklearn.preprocessing import StandardScaler import numpy as np# 数据 x np.array([[1.,-1.,2.],[2.,0.,0.],[0.,1.,-1.]]) print(----------------minmaxscaler标准化-------------) # 调用minma…...
架构师成长之路Redis第三篇|Redis key过期清除策略
Eviction policies maxmemory 100mb 当我们设置的内存达到指定的内存量时,清除策略的配置方式决定了默认行为。Redis可以为可能导致使用更多内存的命令返回错误,也可以在每次添加新数据时清除一些旧数据以返回到指定的限制。 当达到最大内存限制时,Redis所遵循的确切行为是…...
C++智能指针之weak_ptr(保姆级教学)
目录 C智能指针之weak_ptr 概述 作用 本文涉及的所有程序 使用说明 weak_ptr的常规操作 lock(); use_count(); expired(); reset(); shared_ptr & weak_ptr 尺寸 智能指针结构框架 常见使用问题 shared_ptr多次引用同一数据,会导致两次释放同一内…...
ElementUI浅尝辄止18:Avatar 头像
用图标、图片或者字符的形式展示用户或事物信息。 常用于管理系统或web网站的用户头像,在用户账户模块更换头像操作也能看到关于Avatar组件的应用。 1.如何使用? 通过 shape 和 size 设置头像的形状和大小。 <template><el-row class"de…...
1688API技术解析,实现按图搜索1688商品(拍立淘)
一种可能的解决方案是使用图像识别和相似度匹配的算法。您可以通过将输入的图片与1688上的商品图片进行比对,找出最相似的商品。这涉及到图像特征提取、相似度计算以及数据库匹配等技术。您可以使用开源的图像处理库(如OpenCV)来进行图像处理…...
【面试经典150题】买卖股票的最佳时机
题目链接 给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。 返回你可以从这笔交易中获取的…...
selenium可以编写自动化测试脚本吗?
Selenium可以用于编写自动化测试脚本,它提供了许多工具和API,可以与浏览器交互,模拟用户操作,检查网页的各个方面。下面是一些步骤,可以帮助你编写Selenium自动化测试脚本。 1、安装Selenium库和浏览器驱动程序 首先…...
CXL.mem M2S Message 释义
🔥点击查看精选 CXL 系列文章🔥 🔥点击进入【芯片设计验证】社区,查看更多精彩内容🔥 📢 声明: 🥭 作者主页:【MangoPapa的CSDN主页】。⚠️ 本文首发于CSDN,…...
使用boost::geometry::union_ 合并边界(内、外):方案二
使用boost::geometry::union_ 合并边界(内、外):方案二 typedef boost::geometry::model::d2::point_xy<double> boost_point; typedef boost::geometry::model::polygon<boost_point> boost_Polygon;struct Point {float x;floa…...
ICCV 2023 | 小鹏汽车纽约石溪:局部上下文感知主动域自适应LADA
摘要 主动域自适应(ADA)通过查询少量选定的目标域样本的标签,以帮助模型从源域迁移到目标域。查询数据的局部上下文信息非常重要,特别是在域间差异较大的情况下,然而现有的ADA方法尚未充分探索这一点。在本文中&#…...
stable diffusion实践操作-黑白稿线稿上色
系列文章目录 本文专门开一节【黑白稿线稿上色】写相关的内容,在看之前,可以同步关注: stable diffusion实践操作 文章目录 系列文章目录前言一、操作步骤1. 找到黑白线稿图 总结 前言 本章主要介绍黑白稿线稿上色,这是通过Cont…...
Python学习教程:集合操作的详细教程
前言 大家早好、午好、晚好吖 ❤ ~欢迎光临本文章 Python中有两种可以遍历的容器类型: 序列类型:包含字符串、列表、元祖 序列类型是线性表,就像数组一样,是在内存中开辟一块连续空间,连续存储的, 那么查找…...
球球的排列
题目传送门 引 计数DP,好像特别经典,有两种做法,我只会 O ( n 3 ) O(n^3) O(n3),有 O ( n 2 ) O(n^2) O(n2)的 解法 首先, 若 x y p 2 且 x z q 2 , 则 y z ( p q x ) 2 若xyp^2且xzq^2,则yz(\frac{pq}{x} )^2 若xyp2且xzq2,则yz(xpq…...
1783_CMD启动MATLAB同时执行一个脚本
全部学习汇总: GitHub - GreyZhang/g_matlab: MATLAB once used to be my daily tool. After many years when I go back and read my old learning notes I felt maybe I still need it in the future. So, start this repo to keep some of my old learning notes…...
C语言中内存分配的几种方式
目录 C语言中内存分配的几种方式静态内存分配栈内存分配堆内存分配内存映射文件 C语言中内存分配的几种方式 静态内存分配 静态内存分配是在程序编译时分配内存,通常用于全局变量和静态变量。这些变量的内存空间在程序的整个运行期间都是存在的。 栈内存分配 栈内存…...
组相联cache如何快速实现cache line eviction并使用PMU events验证
如何快速实现cache line eviction 一,什么是cache hit、miss、linefill、evict ?1.1 如果要程序员分别制造出cache hit、miss、linefill、evict这四种场景,该怎么做? 二,实现cache line eviction的方法1.1 直接填充法3…...
【Stable Diffusion安装】支持python3.11 window版
前言 主要的安装步骤是参考B站播放量第一的视频,但是那位阿婆主应该是没有编程经验,只强调使用3.10,而python最新版本是3.11。 理论上来说,只是一个小版本的不同,应该是可以安装成功了。自己摸索了下,挺费…...
内存分配函数malloc kmalloc vmalloc
内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...
大语言模型如何处理长文本?常用文本分割技术详解
为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...
10-Oracle 23 ai Vector Search 概述和参数
一、Oracle AI Vector Search 概述 企业和个人都在尝试各种AI,使用客户端或是内部自己搭建集成大模型的终端,加速与大型语言模型(LLM)的结合,同时使用检索增强生成(Retrieval Augmented Generation &#…...
网站指纹识别
网站指纹识别 网站的最基本组成:服务器(操作系统)、中间件(web容器)、脚本语言、数据厍 为什么要了解这些?举个例子:发现了一个文件读取漏洞,我们需要读/etc/passwd,如…...
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配置的颜色主题,无需引入,直接可…...
(一)单例模式
一、前言 单例模式属于六大创建型模式,即在软件设计过程中,主要关注创建对象的结果,并不关心创建对象的过程及细节。创建型设计模式将类对象的实例化过程进行抽象化接口设计,从而隐藏了类对象的实例是如何被创建的,封装了软件系统使用的具体对象类型。 六大创建型模式包括…...
Python实现简单音频数据压缩与解压算法
Python实现简单音频数据压缩与解压算法 引言 在音频数据处理中,压缩算法是降低存储成本和传输效率的关键技术。Python作为一门灵活且功能强大的编程语言,提供了丰富的库和工具来实现音频数据的压缩与解压。本文将通过一个简单的音频数据压缩与解压算法…...
用递归算法解锁「子集」问题 —— LeetCode 78题解析
文章目录 一、题目介绍二、递归思路详解:从决策树开始理解三、解法一:二叉决策树 DFS四、解法二:组合式回溯写法(推荐)五、解法对比 递归算法是编程中一种非常强大且常见的思想,它能够优雅地解决很多复杂的…...
2025年- H71-Lc179--39.组合总和(回溯,组合)--Java版
1.题目描述 2.思路 当前的元素可以重复使用。 (1)确定回溯算法函数的参数和返回值(一般是void类型) (2)因为是用递归实现的,所以我们要确定终止条件 (3)单层搜索逻辑 二…...
【java面试】微服务篇
【java面试】微服务篇 一、总体框架二、Springcloud(一)Springcloud五大组件(二)服务注册和发现1、Eureka2、Nacos (三)负载均衡1、Ribbon负载均衡流程2、Ribbon负载均衡策略3、自定义负载均衡策略4、总结 …...
