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

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最少要几次

题目 思路&#xff1a;因为有走的过程不能超初始位置1e5的限制&#xff0c;所以不能直接用奇数最多两次&#xff0c;4的倍数最多两次的结论。spfa&#xff0c;平方数的dis为1&#xff0c;然后推出其他数的dis #include<bits/stdc.h> using namespace std; #define int …...

【Spring Boot 3】【Flyway】数据库版本管理

【Spring Boot 3】【Flyway】数据库版本管理 背景介绍开发环境开发步骤及源码工程目录结构总结背景 软件开发是一门实践性科学,对大多数人来说,学习一种新技术不是一开始就去深究其原理,而是先从做出一个可工作的DEMO入手。但在我个人学习和工作经历中,每次学习新技术总是…...

蓝桥杯基础数据结构(java版)

引言 数据结构数据结构。所以数据结构是一个抽象的概念。其目的是为了更好的组织数据方便数据存储。下面我们来看一些简单的数据储存方式 输入和输出 这里先介绍java的输入和输出。简单引入&#xff0c;不过多详细介绍&#xff0c;等我单一写一篇的时候这里会挂上链接 简单的…...

39 C++ 模版中的参数如果 是 vector,list等集合类型如何处理呢?

在前面写的例子中&#xff0c;模版参数一般都是 int&#xff0c;或者一个类Teacher&#xff0c;假设我们现在有个需求&#xff1a;模版的参数要是vector&#xff0c;list这种结合类型应该怎么写呢&#xff1f; //当模版中的类型是 vector &#xff0c;list 等集合类型的时候的处…...

5.Pytorch模型单机多GPU训练原理与实现

文章目录 Pytorch的单机多GPU训练1)多GPU训练介绍2)pytorch中使用单机多GPU训练DistributedDataParallel(DDP)相关变量及含义a)初始化b)数据准备c)模型准备d)清理e)运行 3)使用DistributedDataParallel训练模型的一个简单实例 欢迎访问个人网络日志&#x1f339;&#x1f339;知…...

想成为一名C++开发工程师,需要具备哪些条件?

C语言是一门面向过程的、抽象化的通用程序设计语言&#xff0c;广泛应用于底层开发。C语言能以简易的方式编译、处理低级存储器。C语言是仅产生少量的机器语言以及不需要任何运行环境支持便能运行的高效率程序设计语言。尽管C语言提供了许多低级处理的功能&#xff0c;但仍然保…...

Qat++,轻量级开源C++ Web框架

目录 一.简介 二.编译Oat 1.环境 2.编译/安装 三.试用 1.创建一个 CMake 项目 2.自定义客户端请求响应 3.将请求Router到服务器 4.用浏览器验证 一.简介 Oat是一个面向C的现代Web框架 官网地址&#xff1a;https://oatpp.io github地址&#xff1a;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 编译后文字乱码的解决方案

问题: 新建的页面中编写代码&#xff0c;其中数字和图片都可以正常显示&#xff0c;只有中文编译后展示乱码 页面展示也是乱码 解决方案: 打开HuilderX编辑器的【文件】- 【以指定编码重新打开】- 【选择UTF-8】 然后重新编译就可以啦~ 希望可以帮到你啊~...

iOS中利用KeyChain永久保存用户信息的方法示例

方法示例 一、新建一个LYKeychainTool类&#xff0c;导入系统Security框架 &#xff0c;LYKeychainTool.h文件实现如下 // // LYKeychainTool.h // keyChainTest // // Created by Liyu on 2017/6/2. // Copyright © 2017年 liyu. All rights reserved. //#import <F…...

基于时域有限差分法的FDTD的计算电磁学算法(含Matlab代码)-YEE网格下的更新公式推导

基于时域有限差分法的FDTD的计算电磁学算法&#xff08;含Matlab代码&#xff09;-YEE网格下的更新公式推导 参考书籍&#xff1a;The finite-difference time-domain method for electromagnetics with MATLAB simulations&#xff08;国内翻译版本&#xff1a;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 [盘符] [挂载的工作目录&#xff08;debug.exe文件夹位置&#xff…...

怎么投稿各大媒体网站?

怎么投稿各大媒体网站&#xff1f;这是很多写作者及自媒体从业者经常面临的问题。在信息爆炸的时代&#xff0c;如何将自己的文章推送到广大读者面前&#xff0c;成为了一个不可避免的挑战。本文将为大家介绍一种简单有效的投稿方法——媒介库发稿平台发稿&#xff0c;帮助大家…...

chatgpt免费使用的网站

前言 如果您认为本文对你有帮助&#xff0c;希望可以点赞收藏&#xff01;感谢您的支持 下面我为你推荐我自己在用的gpt类工具&#xff0c;帮你在工作学习生活上解决一些大小问题 &#x1f389;智能GPT 地址&#xff1a; https://meet.adminjs.net 在他的详情中有详细的使用…...

音频编辑软件:Studio One 6 中文

Studio One 6是一款功能强大的数字音乐制作软件&#xff0c;为用户提供一站式音乐制作解决方案。它具有直观的界面和强大的音频录制、编辑、混音和制作功能&#xff0c;支持虚拟乐器、效果器和第三方插件&#xff0c;可帮助用户实现高质量的音乐创作和制作。同时&#xff0c;St…...

MySQL语句|使用UNION和UNION ALL合并两个或多个 SELECT 语句的结果集

文章目录 举个通用的例子举个实际的例子 在MySQL中&#xff0c; UNION 和 UNION ALL 是用于合并两个或多个 SELECT 语句的结果集的操作符。 UNION 会去除结果集中的重复行&#xff0c;返回唯一的行&#xff0c;而 UNION ALL 会返回所有的行&#xff0c;包括重复行。 举个通…...

UNRAID 优盘制作

使用方法和开心方法&#xff1a; 如果重启之后显示器有信号但是黑屏无法正常引导系统&#xff0c;此为九代以后主板快速开机&#xff08;快速引导&#xff09;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是一种开源的关系型数据库管理系统&#xff0c;被广泛应用…...

银行测试--------转账

转账 付款账号测试 付款账号是借记卡&#xff0c;也可以是活期存折信用卡&#xff0c;定期存折不能转出。一般在账号选择的时候进行屏蔽转出账户在销户&#xff0c;冻结&#xff0c;挂失等异常状态&#xff0c;不能进行转账付款账号金额不够 转账金额测试 0.01&#xff5e;…...

阿里云最新优惠券领取方法及优惠活动汇总

随着互联网的飞速发展&#xff0c;云服务已经成为企业和个人使用的重要基础设施。阿里云作为全球领先的云服务提供商&#xff0c;一直致力于为用户提供优质的云服务。为了回馈用户&#xff0c;阿里云会定期推出各种优惠券和优惠活动&#xff0c;本文将为大家介绍阿里云最新优惠…...

Docker 离线安装指南

参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性&#xff0c;不同版本的Docker对内核版本有不同要求。例如&#xff0c;Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本&#xff0c;Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...

无法与IP建立连接,未能下载VSCode服务器

如题&#xff0c;在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈&#xff0c;发现是VSCode版本自动更新惹的祸&#xff01;&#xff01;&#xff01; 在VSCode的帮助->关于这里发现前几天VSCode自动更新了&#xff0c;我的版本号变成了1.100.3 才导致了远程连接出…...

【Go】3、Go语言进阶与依赖管理

前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课&#xff0c;做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程&#xff0c;它的核心机制是 Goroutine 协程、Channel 通道&#xff0c;并基于CSP&#xff08;Communicating Sequential Processes&#xff0…...

从零实现STL哈希容器:unordered_map/unordered_set封装详解

本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说&#xff0c;直接开始吧&#xff01; 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...

土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等

&#x1f50d; 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术&#xff0c;可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势&#xff0c;还能有效评价重大生态工程…...

多种风格导航菜单 HTML 实现(附源码)

下面我将为您展示 6 种不同风格的导航菜单实现&#xff0c;每种都包含完整 HTML、CSS 和 JavaScript 代码。 1. 简约水平导航栏 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport&qu…...

Linux离线(zip方式)安装docker

目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1&#xff1a;修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本&#xff1a;CentOS 7 64位 内核版本&#xff1a;3.10.0 相关命令&#xff1a; uname -rcat /etc/os-rele…...

[免费]微信小程序问卷调查系统(SpringBoot后端+Vue管理端)【论文+源码+SQL脚本】

大家好&#xff0c;我是java1234_小锋老师&#xff0c;看到一个不错的微信小程序问卷调查系统(SpringBoot后端Vue管理端)【论文源码SQL脚本】&#xff0c;分享下哈。 项目视频演示 【免费】微信小程序问卷调查系统(SpringBoot后端Vue管理端) Java毕业设计_哔哩哔哩_bilibili 项…...

小木的算法日记-多叉树的递归/层序遍历

&#x1f332; 从二叉树到森林&#xff1a;一文彻底搞懂多叉树遍历的艺术 &#x1f680; 引言 你好&#xff0c;未来的算法大神&#xff01; 在数据结构的世界里&#xff0c;“树”无疑是最核心、最迷人的概念之一。我们中的大多数人都是从 二叉树 开始入门的&#xff0c;它…...

论文阅读:Matting by Generation

今天介绍一篇关于 matting 抠图的文章&#xff0c;抠图也算是计算机视觉里面非常经典的一个任务了。从早期的经典算法到如今的深度学习算法&#xff0c;已经有很多的工作和这个任务相关。这两年 diffusion 模型很火&#xff0c;大家又开始用 diffusion 模型做各种 CV 任务了&am…...