Jerry每次能向前或向后走n*n步(始终不能超过初始位置1e5),q(q <= 1e5)次询问,求向前走d最少要几次
题目
思路:因为有走的过程不能超初始位置1e5的限制,所以不能直接用奇数最多两次,4的倍数最多两次的结论。spfa,平方数的dis为1,然后推出其他数的dis
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 2e5 + 5, inf = 1e9, N = 1e5;
int a[maxn];
int sq[maxn], dis[maxn];
int m;
// int f[320][maxn];
queue<int> q;
bool inque[maxn];
bool issq(int x){int sqt = sqrt(x);return sqt * sqt == x;
}
void solve(){int Q;cin >> Q;memset(dis, 0x3f, sizeof(dis));for(int i = 1; i * i <= 1e5; i++){sq[++m] = i * i;dis[i * i + N] = 1;q.push(i * i);dis[-i * i + N] = 1;q.push(-i * i);inque[i * i + N] = inque[-i * i + N] = 1;}while(!q.empty()){int u = q.front();q.pop();inque[u + N] = 0;for(int i = 1; i <= m; i++){int v = u + sq[i];if(v >= -N && v <= N){if(dis[u + N] + 1 < dis[v + N]){dis[v + N] = dis[u + N] + 1;q.push(v);inque[v + N] = 1;}} v = u - sq[i];if(v >= -N && v <= N && dis[u + N] + 1 < dis[v + N]){dis[v + N] = dis[u + N] + 1;q.push(v);inque[v + N] = 1;}}}while(Q--){int d;cin >> d;cout << dis[d + N] << '\n';}
// for(int i = 99900; i <= N; i++){
// cout << dis[i + N] << ' ';
// }
}
signed main(){
// memset(f, 0x3f, sizeof(f));int T = 1;
// cin >> T;while(T--){solve();}return 0;
}
相关文章:
Jerry每次能向前或向后走n*n步(始终不能超过初始位置1e5),q(q <= 1e5)次询问,求向前走d最少要几次
题目 思路:因为有走的过程不能超初始位置1e5的限制,所以不能直接用奇数最多两次,4的倍数最多两次的结论。spfa,平方数的dis为1,然后推出其他数的dis #include<bits/stdc.h> using namespace std; #define int …...
【Spring Boot 3】【Flyway】数据库版本管理
【Spring Boot 3】【Flyway】数据库版本管理 背景介绍开发环境开发步骤及源码工程目录结构总结背景 软件开发是一门实践性科学,对大多数人来说,学习一种新技术不是一开始就去深究其原理,而是先从做出一个可工作的DEMO入手。但在我个人学习和工作经历中,每次学习新技术总是…...
蓝桥杯基础数据结构(java版)
引言 数据结构数据结构。所以数据结构是一个抽象的概念。其目的是为了更好的组织数据方便数据存储。下面我们来看一些简单的数据储存方式 输入和输出 这里先介绍java的输入和输出。简单引入,不过多详细介绍,等我单一写一篇的时候这里会挂上链接 简单的…...
39 C++ 模版中的参数如果 是 vector,list等集合类型如何处理呢?
在前面写的例子中,模版参数一般都是 int,或者一个类Teacher,假设我们现在有个需求:模版的参数要是vector,list这种结合类型应该怎么写呢? //当模版中的类型是 vector ,list 等集合类型的时候的处…...
5.Pytorch模型单机多GPU训练原理与实现
文章目录 Pytorch的单机多GPU训练1)多GPU训练介绍2)pytorch中使用单机多GPU训练DistributedDataParallel(DDP)相关变量及含义a)初始化b)数据准备c)模型准备d)清理e)运行 3)使用DistributedDataParallel训练模型的一个简单实例 欢迎访问个人网络日志🌹🌹知…...
想成为一名C++开发工程师,需要具备哪些条件?
C语言是一门面向过程的、抽象化的通用程序设计语言,广泛应用于底层开发。C语言能以简易的方式编译、处理低级存储器。C语言是仅产生少量的机器语言以及不需要任何运行环境支持便能运行的高效率程序设计语言。尽管C语言提供了许多低级处理的功能,但仍然保…...
Qat++,轻量级开源C++ Web框架
目录 一.简介 二.编译Oat 1.环境 2.编译/安装 三.试用 1.创建一个 CMake 项目 2.自定义客户端请求响应 3.将请求Router到服务器 4.用浏览器验证 一.简介 Oat是一个面向C的现代Web框架 官网地址:https://oatpp.io github地址:https://github.co…...
openssl3.2 - 官方demo学习 - digest - EVP_MD_demo.c
文章目录 openssl3.2 - 官方demo学习 - digest - EVP_MD_demo.c概述笔记END openssl3.2 - 官方demo学习 - digest - EVP_MD_demo.c 概述 使用 SHA3-512 对多个buffer连续进行摘要, 最后得到一个摘要值 笔记 /*! \file EVP_MD_demo.c \note openssl3.2 - 官方demo学习 - dig…...
uniapp 编译后文字乱码的解决方案
问题: 新建的页面中编写代码,其中数字和图片都可以正常显示,只有中文编译后展示乱码 页面展示也是乱码 解决方案: 打开HuilderX编辑器的【文件】- 【以指定编码重新打开】- 【选择UTF-8】 然后重新编译就可以啦~ 希望可以帮到你啊~...
iOS中利用KeyChain永久保存用户信息的方法示例
方法示例 一、新建一个LYKeychainTool类,导入系统Security框架 ,LYKeychainTool.h文件实现如下 // // LYKeychainTool.h // keyChainTest // // Created by Liyu on 2017/6/2. // Copyright © 2017年 liyu. All rights reserved. //#import <F…...
基于时域有限差分法的FDTD的计算电磁学算法(含Matlab代码)-YEE网格下的更新公式推导
基于时域有限差分法的FDTD的计算电磁学算法(含Matlab代码)-YEE网格下的更新公式推导 参考书籍:The finite-difference time-domain method for electromagnetics with MATLAB simulations(国内翻译版本:MATLAB模拟的电…...
win10使用debug,汇编初学
DOSBox挂载Debug.exe 双击 DOSBox Options.bat 打开配置 或者执行cmd DOSBox.exe -editconf notepad.exe -editconf %SystemRoot%\system32\notepad.exe -editconf %WINDIR%\notepad.exe最后一行增加 mount [盘符] [挂载的工作目录(debug.exe文件夹位置ÿ…...
怎么投稿各大媒体网站?
怎么投稿各大媒体网站?这是很多写作者及自媒体从业者经常面临的问题。在信息爆炸的时代,如何将自己的文章推送到广大读者面前,成为了一个不可避免的挑战。本文将为大家介绍一种简单有效的投稿方法——媒介库发稿平台发稿,帮助大家…...
chatgpt免费使用的网站
前言 如果您认为本文对你有帮助,希望可以点赞收藏!感谢您的支持 下面我为你推荐我自己在用的gpt类工具,帮你在工作学习生活上解决一些大小问题 🎉智能GPT 地址: https://meet.adminjs.net 在他的详情中有详细的使用…...
音频编辑软件:Studio One 6 中文
Studio One 6是一款功能强大的数字音乐制作软件,为用户提供一站式音乐制作解决方案。它具有直观的界面和强大的音频录制、编辑、混音和制作功能,支持虚拟乐器、效果器和第三方插件,可帮助用户实现高质量的音乐创作和制作。同时,St…...
MySQL语句|使用UNION和UNION ALL合并两个或多个 SELECT 语句的结果集
文章目录 举个通用的例子举个实际的例子 在MySQL中, UNION 和 UNION ALL 是用于合并两个或多个 SELECT 语句的结果集的操作符。 UNION 会去除结果集中的重复行,返回唯一的行,而 UNION ALL 会返回所有的行,包括重复行。 举个通…...
UNRAID 优盘制作
使用方法和开心方法: 如果重启之后显示器有信号但是黑屏无法正常引导系统,此为九代以后主板快速开机(快速引导)UNRAID并不支持快速引导所以会直接卡黑屏。所以发现这种情况的时候请进BIOS关闭和开机快速引导或和快有关系的任何开…...
二、Java中SpringBoot组件集成接入【MySQL和MybatisPlus】
二、Java中SpringBoot组件集成接入【MySQL和MybatisPlus】 1.MySQL和MybatisPlus简介2.maven依赖3.配置1.在application.yaml配置中加入mysql配置2.新增Mybatis-Plus配置类 4.参考文章 1.MySQL和MybatisPlus简介 MySQL是一种开源的关系型数据库管理系统,被广泛应用…...
银行测试--------转账
转账 付款账号测试 付款账号是借记卡,也可以是活期存折信用卡,定期存折不能转出。一般在账号选择的时候进行屏蔽转出账户在销户,冻结,挂失等异常状态,不能进行转账付款账号金额不够 转账金额测试 0.01~…...
阿里云最新优惠券领取方法及优惠活动汇总
随着互联网的飞速发展,云服务已经成为企业和个人使用的重要基础设施。阿里云作为全球领先的云服务提供商,一直致力于为用户提供优质的云服务。为了回馈用户,阿里云会定期推出各种优惠券和优惠活动,本文将为大家介绍阿里云最新优惠…...
业务系统对接大模型的基础方案:架构设计与关键步骤
业务系统对接大模型:架构设计与关键步骤 在当今数字化转型的浪潮中,大语言模型(LLM)已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中,不仅可以优化用户体验,还能为业务决策提供…...
golang循环变量捕获问题
在 Go 语言中,当在循环中启动协程(goroutine)时,如果在协程闭包中直接引用循环变量,可能会遇到一个常见的陷阱 - 循环变量捕获问题。让我详细解释一下: 问题背景 看这个代码片段: fo…...
在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:
在 HarmonyOS 应用开发中,手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力,既支持点击、长按、拖拽等基础单一手势的精细控制,也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档,…...
【位运算】消失的两个数字(hard)
消失的两个数字(hard) 题⽬描述:解法(位运算):Java 算法代码:更简便代码 题⽬链接:⾯试题 17.19. 消失的两个数字 题⽬描述: 给定⼀个数组,包含从 1 到 N 所有…...
系统设计 --- MongoDB亿级数据查询优化策略
系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log,共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题,不能使用ELK只能使用…...
【HarmonyOS 5 开发速记】如何获取用户信息(头像/昵称/手机号)
1.获取 authorizationCode: 2.利用 authorizationCode 获取 accessToken:文档中心 3.获取手机:文档中心 4.获取昵称头像:文档中心 首先创建 request 若要获取手机号,scope必填 phone,permissions 必填 …...
华硕a豆14 Air香氛版,美学与科技的馨香融合
在快节奏的现代生活中,我们渴望一个能激发创想、愉悦感官的工作与生活伙伴,它不仅是冰冷的科技工具,更能触动我们内心深处的细腻情感。正是在这样的期许下,华硕a豆14 Air香氛版翩然而至,它以一种前所未有的方式&#x…...
在QWebEngineView上实现鼠标、触摸等事件捕获的解决方案
这个问题我看其他博主也写了,要么要会员、要么写的乱七八糟。这里我整理一下,把问题说清楚并且给出代码,拿去用就行,照着葫芦画瓢。 问题 在继承QWebEngineView后,重写mousePressEvent或event函数无法捕获鼠标按下事…...
JVM虚拟机:内存结构、垃圾回收、性能优化
1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...
作为测试我们应该关注redis哪些方面
1、功能测试 数据结构操作:验证字符串、列表、哈希、集合和有序的基本操作是否正确 持久化:测试aof和aof持久化机制,确保数据在开启后正确恢复。 事务:检查事务的原子性和回滚机制。 发布订阅:确保消息正确传递。 2、性…...
