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~…...
阿里云最新优惠券领取方法及优惠活动汇总
随着互联网的飞速发展,云服务已经成为企业和个人使用的重要基础设施。阿里云作为全球领先的云服务提供商,一直致力于为用户提供优质的云服务。为了回馈用户,阿里云会定期推出各种优惠券和优惠活动,本文将为大家介绍阿里云最新优惠…...
简易版抽奖活动的设计技术方案
1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...
rknn优化教程(二)
文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK,开始写第二篇的内容了。这篇博客主要能写一下: 如何给一些三方库按照xmake方式进行封装,供调用如何按…...
Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例
使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件,常用于在两个集合之间进行数据转移,如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model:绑定右侧列表的值&…...
Java如何权衡是使用无序的数组还是有序的数组
在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...
LeetCode - 394. 字符串解码
题目 394. 字符串解码 - 力扣(LeetCode) 思路 使用两个栈:一个存储重复次数,一个存储字符串 遍历输入字符串: 数字处理:遇到数字时,累积计算重复次数左括号处理:保存当前状态&a…...
pikachu靶场通关笔记22-1 SQL注入05-1-insert注入(报错法)
目录 一、SQL注入 二、insert注入 三、报错型注入 四、updatexml函数 五、源码审计 六、insert渗透实战 1、渗透准备 2、获取数据库名database 3、获取表名table 4、获取列名column 5、获取字段 本系列为通过《pikachu靶场通关笔记》的SQL注入关卡(共10关࿰…...
dify打造数据可视化图表
一、概述 在日常工作和学习中,我们经常需要和数据打交道。无论是分析报告、项目展示,还是简单的数据洞察,一个清晰直观的图表,往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server,由蚂蚁集团 AntV 团队…...
Springboot社区养老保险系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,社区养老保险系统小程序被用户普遍使用,为方…...
【分享】推荐一些办公小工具
1、PDF 在线转换 https://smallpdf.com/cn/pdf-tools 推荐理由:大部分的转换软件需要收费,要么功能不齐全,而开会员又用不了几次浪费钱,借用别人的又不安全。 这个网站它不需要登录或下载安装。而且提供的免费功能就能满足日常…...
Golang——6、指针和结构体
指针和结构体 1、指针1.1、指针地址和指针类型1.2、指针取值1.3、new和make 2、结构体2.1、type关键字的使用2.2、结构体的定义和初始化2.3、结构体方法和接收者2.4、给任意类型添加方法2.5、结构体的匿名字段2.6、嵌套结构体2.7、嵌套匿名结构体2.8、结构体的继承 3、结构体与…...
