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

双向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…...

数据艺术:精通数据可视化的关键步骤

数据可视化是将复杂数据转化为易于理解的图表和图形的过程&#xff0c;帮助我们发现趋势、关联和模式。同时数据可视化也是数字孪生的基础&#xff0c;本文小编带大家用最简单的话语为大家讲解怎么制作一个数据可视化大屏&#xff0c;接下来跟随小编的思路走起来~ 1.数据收集和…...

MySQL 是如何实现事务的四大特性的?

分析&回答 如果你不知道事务更不知道四大特性请先看看&#xff1a;说说什么是事务 原子性 语句要么都执行&#xff0c;要么都不执行&#xff0c;是事务最核心的特性&#xff0c;事务本身来说就是以原子性来定义的&#xff0c;实现主要是基于undo log undo log&#xff…...

python实现zscore归一化和minmax标准化

zscore归一化&#xff1a; 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多次引用同一数据&#xff0c;会导致两次释放同一内…...

ElementUI浅尝辄止18:Avatar 头像

用图标、图片或者字符的形式展示用户或事物信息。 常用于管理系统或web网站的用户头像&#xff0c;在用户账户模块更换头像操作也能看到关于Avatar组件的应用。 1.如何使用&#xff1f; 通过 shape 和 size 设置头像的形状和大小。 <template><el-row class"de…...

1688API技术解析,实现按图搜索1688商品(拍立淘)

一种可能的解决方案是使用图像识别和相似度匹配的算法。您可以通过将输入的图片与1688上的商品图片进行比对&#xff0c;找出最相似的商品。这涉及到图像特征提取、相似度计算以及数据库匹配等技术。您可以使用开源的图像处理库&#xff08;如OpenCV&#xff09;来进行图像处理…...

【面试经典150题】买卖股票的最佳时机

题目链接 给定一个数组 prices &#xff0c;它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 你只能选择 某一天 买入这只股票&#xff0c;并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。 返回你可以从这笔交易中获取的…...

selenium可以编写自动化测试脚本吗?

Selenium可以用于编写自动化测试脚本&#xff0c;它提供了许多工具和API&#xff0c;可以与浏览器交互&#xff0c;模拟用户操作&#xff0c;检查网页的各个方面。下面是一些步骤&#xff0c;可以帮助你编写Selenium自动化测试脚本。 1、安装Selenium库和浏览器驱动程序 首先…...

CXL.mem M2S Message 释义

&#x1f525;点击查看精选 CXL 系列文章&#x1f525; &#x1f525;点击进入【芯片设计验证】社区&#xff0c;查看更多精彩内容&#x1f525; &#x1f4e2; 声明&#xff1a; &#x1f96d; 作者主页&#xff1a;【MangoPapa的CSDN主页】。⚠️ 本文首发于CSDN&#xff0c…...

使用boost::geometry::union_ 合并边界(内、外):方案二

使用boost::geometry::union_ 合并边界&#xff08;内、外&#xff09;&#xff1a;方案二 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

摘要 主动域自适应&#xff08;ADA&#xff09;通过查询少量选定的目标域样本的标签&#xff0c;以帮助模型从源域迁移到目标域。查询数据的局部上下文信息非常重要&#xff0c;特别是在域间差异较大的情况下&#xff0c;然而现有的ADA方法尚未充分探索这一点。在本文中&#…...

stable diffusion实践操作-黑白稿线稿上色

系列文章目录 本文专门开一节【黑白稿线稿上色】写相关的内容&#xff0c;在看之前&#xff0c;可以同步关注&#xff1a; stable diffusion实践操作 文章目录 系列文章目录前言一、操作步骤1. 找到黑白线稿图 总结 前言 本章主要介绍黑白稿线稿上色&#xff0c;这是通过Cont…...

Python学习教程:集合操作的详细教程

前言 大家早好、午好、晚好吖 ❤ ~欢迎光临本文章 Python中有两种可以遍历的容器类型&#xff1a; 序列类型&#xff1a;包含字符串、列表、元祖 序列类型是线性表&#xff0c;就像数组一样&#xff0c;是在内存中开辟一块连续空间&#xff0c;连续存储的&#xff0c; 那么查找…...

球球的排列

题目传送门 引 计数DP,好像特别经典&#xff0c;有两种做法&#xff0c;我只会 O ( n 3 ) O(n^3) O(n3),有 O ( n 2 ) O(n^2) O(n2)的 解法 首先&#xff0c; 若 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同时执行一个脚本

全部学习汇总&#xff1a; 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语言中内存分配的几种方式 静态内存分配 静态内存分配是在程序编译时分配内存&#xff0c;通常用于全局变量和静态变量。这些变量的内存空间在程序的整个运行期间都是存在的。 栈内存分配 栈内存…...

组相联cache如何快速实现cache line eviction并使用PMU events验证

如何快速实现cache line eviction 一&#xff0c;什么是cache hit、miss、linefill、evict &#xff1f;1.1 如果要程序员分别制造出cache hit、miss、linefill、evict这四种场景&#xff0c;该怎么做&#xff1f; 二&#xff0c;实现cache line eviction的方法1.1 直接填充法3…...

【Stable Diffusion安装】支持python3.11 window版

前言 主要的安装步骤是参考B站播放量第一的视频&#xff0c;但是那位阿婆主应该是没有编程经验&#xff0c;只强调使用3.10&#xff0c;而python最新版本是3.11。 理论上来说&#xff0c;只是一个小版本的不同&#xff0c;应该是可以安装成功了。自己摸索了下&#xff0c;挺费…...

接口测试中缓存处理策略

在接口测试中&#xff0c;缓存处理策略是一个关键环节&#xff0c;直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性&#xff0c;避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明&#xff1a; 一、缓存处理的核…...

ES6从入门到精通:前言

ES6简介 ES6&#xff08;ECMAScript 2015&#xff09;是JavaScript语言的重大更新&#xff0c;引入了许多新特性&#xff0c;包括语法糖、新数据类型、模块化支持等&#xff0c;显著提升了开发效率和代码可维护性。 核心知识点概览 变量声明 let 和 const 取代 var&#xf…...

【OSG学习笔记】Day 18: 碰撞检测与物理交互

物理引擎&#xff08;Physics Engine&#xff09; 物理引擎 是一种通过计算机模拟物理规律&#xff08;如力学、碰撞、重力、流体动力学等&#xff09;的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互&#xff0c;广泛应用于 游戏开发、动画制作、虚…...

在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:

在 HarmonyOS 应用开发中&#xff0c;手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力&#xff0c;既支持点击、长按、拖拽等基础单一手势的精细控制&#xff0c;也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档&#xff0c…...

Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例

使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件&#xff0c;常用于在两个集合之间进行数据转移&#xff0c;如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model&#xff1a;绑定右侧列表的值&…...

dedecms 织梦自定义表单留言增加ajax验证码功能

增加ajax功能模块&#xff0c;用户不点击提交按钮&#xff0c;只要输入框失去焦点&#xff0c;就会提前提示验证码是否正确。 一&#xff0c;模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...

华为OD机试-食堂供餐-二分法

import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...

MySQL中【正则表达式】用法

MySQL 中正则表达式通过 REGEXP 或 RLIKE 操作符实现&#xff08;两者等价&#xff09;&#xff0c;用于在 WHERE 子句中进行复杂的字符串模式匹配。以下是核心用法和示例&#xff1a; 一、基础语法 SELECT column_name FROM table_name WHERE column_name REGEXP pattern; …...

Java面试专项一-准备篇

一、企业简历筛选规则 一般企业的简历筛选流程&#xff1a;首先由HR先筛选一部分简历后&#xff0c;在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如&#xff1a;Boss直聘&#xff08;招聘方平台&#xff09; 直接按照条件进行筛选 例如&#xff1a…...

精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南

精益数据分析&#xff08;97/126&#xff09;&#xff1a;邮件营销与用户参与度的关键指标优化指南 在数字化营销时代&#xff0c;邮件列表效度、用户参与度和网站性能等指标往往决定着创业公司的增长成败。今天&#xff0c;我们将深入解析邮件打开率、网站可用性、页面参与时…...