当前位置: 首页 > 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;本文将为大家介绍阿里云最新优惠…...

微信小程序之bind和catch

这两个呢&#xff0c;都是绑定事件用的&#xff0c;具体使用有些小区别。 官方文档&#xff1a; 事件冒泡处理不同 bind&#xff1a;绑定的事件会向上冒泡&#xff0c;即触发当前组件的事件后&#xff0c;还会继续触发父组件的相同事件。例如&#xff0c;有一个子视图绑定了b…...

MFC内存泄露

1、泄露代码示例 void X::SetApplicationBtn() {CMFCRibbonApplicationButton* pBtn GetApplicationButton();// 获取 Ribbon Bar 指针// 创建自定义按钮CCustomRibbonAppButton* pCustomButton new CCustomRibbonAppButton();pCustomButton->SetImage(IDB_BITMAP_Jdp26)…...

使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装

以下是基于 vant-ui&#xff08;适配 Vue2 版本 &#xff09;实现截图中照片上传预览、删除功能&#xff0c;并封装成可复用组件的完整代码&#xff0c;包含样式和逻辑实现&#xff0c;可直接在 Vue2 项目中使用&#xff1a; 1. 封装的图片上传组件 ImageUploader.vue <te…...

稳定币的深度剖析与展望

一、引言 在当今数字化浪潮席卷全球的时代&#xff0c;加密货币作为一种新兴的金融现象&#xff0c;正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而&#xff0c;加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下&#xff0c;稳定…...

OPENCV形态学基础之二腐蚀

一.腐蚀的原理 (图1) 数学表达式&#xff1a;dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一&#xff0c;腐蚀跟膨胀属于反向操作&#xff0c;膨胀是把图像图像变大&#xff0c;而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...

Xen Server服务器释放磁盘空间

disk.sh #!/bin/bashcd /run/sr-mount/e54f0646-ae11-0457-b64f-eba4673b824c # 全部虚拟机物理磁盘文件存储 a$(ls -l | awk {print $NF} | cut -d. -f1) # 使用中的虚拟机物理磁盘文件 b$(xe vm-disk-list --multiple | grep uuid | awk {print $NF})printf "%s\n"…...

初探Service服务发现机制

1.Service简介 Service是将运行在一组Pod上的应用程序发布为网络服务的抽象方法。 主要功能&#xff1a;服务发现和负载均衡。 Service类型的包括ClusterIP类型、NodePort类型、LoadBalancer类型、ExternalName类型 2.Endpoints简介 Endpoints是一种Kubernetes资源&#xf…...

C++:多态机制详解

目录 一. 多态的概念 1.静态多态&#xff08;编译时多态&#xff09; 二.动态多态的定义及实现 1.多态的构成条件 2.虚函数 3.虚函数的重写/覆盖 4.虚函数重写的一些其他问题 1&#xff09;.协变 2&#xff09;.析构函数的重写 5.override 和 final关键字 1&#…...

Python Einops库:深度学习中的张量操作革命

Einops&#xff08;爱因斯坦操作库&#xff09;就像给张量操作戴上了一副"语义眼镜"——让你用人类能理解的方式告诉计算机如何操作多维数组。这个基于爱因斯坦求和约定的库&#xff0c;用类似自然语言的表达式替代了晦涩的API调用&#xff0c;彻底改变了深度学习工程…...

比较数据迁移后MySQL数据库和OceanBase数据仓库中的表

设计一个MySQL数据库和OceanBase数据仓库的表数据比较的详细程序流程,两张表是相同的结构,都有整型主键id字段,需要每次从数据库分批取得2000条数据,用于比较,比较操作的同时可以再取2000条数据,等上一次比较完成之后,开始比较,直到比较完所有的数据。比较操作需要比较…...