双向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。 理论上来说,只是一个小版本的不同,应该是可以安装成功了。自己摸索了下,挺费…...
反向工程与模型迁移:打造未来商品详情API的可持续创新体系
在电商行业蓬勃发展的当下,商品详情API作为连接电商平台与开发者、商家及用户的关键纽带,其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息(如名称、价格、库存等)的获取与展示,已难以满足市场对个性化、智能…...
从零实现富文本编辑器#5-编辑器选区模型的状态结构表达
先前我们总结了浏览器选区模型的交互策略,并且实现了基本的选区操作,还调研了自绘选区的实现。那么相对的,我们还需要设计编辑器的选区表达,也可以称为模型选区。编辑器中应用变更时的操作范围,就是以模型选区为基准来…...
CMake基础:构建流程详解
目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...
高频面试之3Zookeeper
高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个?3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制(过半机制࿰…...
深入理解JavaScript设计模式之单例模式
目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式(Singleton Pattern&#…...
零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)
本期内容并不是很难,相信大家会学的很愉快,当然对于有后端基础的朋友来说,本期内容更加容易了解,当然没有基础的也别担心,本期内容会详细解释有关内容 本期用到的软件:yakit(因为经过之前好多期…...
关于easyexcel动态下拉选问题处理
前些日子突然碰到一个问题,说是客户的导入文件模版想支持部分导入内容的下拉选,于是我就找了easyexcel官网寻找解决方案,并没有找到合适的方案,没办法只能自己动手并分享出来,针对Java生成Excel下拉菜单时因选项过多导…...
掌握 HTTP 请求:理解 cURL GET 语法
cURL 是一个强大的命令行工具,用于发送 HTTP 请求和与 Web 服务器交互。在 Web 开发和测试中,cURL 经常用于发送 GET 请求来获取服务器资源。本文将详细介绍 cURL GET 请求的语法和使用方法。 一、cURL 基本概念 cURL 是 "Client URL" 的缩写…...
MyBatis中关于缓存的理解
MyBatis缓存 MyBatis系统当中默认定义两级缓存:一级缓存、二级缓存 默认情况下,只有一级缓存开启(sqlSession级别的缓存)二级缓存需要手动开启配置,需要局域namespace级别的缓存 一级缓存(本地缓存&#…...
保姆级【快数学会Android端“动画“】+ 实现补间动画和逐帧动画!!!
目录 补间动画 1.创建资源文件夹 2.设置文件夹类型 3.创建.xml文件 4.样式设计 5.动画设置 6.动画的实现 内容拓展 7.在原基础上继续添加.xml文件 8.xml代码编写 (1)rotate_anim (2)scale_anim (3)translate_anim 9.MainActivity.java代码汇总 10.效果展示 逐帧…...
