第十四届蓝桥杯三月真题刷题训练——第 22 天

目录

第 1 题:受伤的皇后_dfs

题目描述

输入描述

输出描述

输入输出样例

运行限制

代码:

思路:

第 2 题:完全平方数

问题描述

输入格式

输出格式

样例输入 1

样例输出 1

样例输入 2

样例输出 2

评测用例规模与约定

运行限制

代码:

思路:

第 3 题:123_前缀和_二分_long

题目描述

输入描述

输出描述

输入输出样例

评测用例规模与约定

运行限制

代码:

思路:

第 4 题:求阶乘_二分_long 

问题描述

输入格式

输出格式

样例输入

样例输出

评测用例规模与约定

运行限制

代码:

思路:


第 1 题:受伤的皇后_dfs

题目描述

有一个 n×n 的国际象棋棋盘(n 行 n 列的方格图),请在棋盘中摆放 n 个受伤的国际象棋皇后,要求:

  1. 任何两个皇后不在同一行。
  2. 任何两个皇后不在同一列。
  3. 如果两个皇后在同一条 45 度角的斜线上,这两个皇后之间行号的差值至少为 3 。

请问一共有多少种摆放方案。

输入描述

输入的第一行包含一个整数 n。

其中,1≤n≤10。

输出描述

输出一个整数,表示答案。

输入输出样例

示例 1

输入

4

输出

2

运行限制

  • 最大运行时间:1s
  • 最大运行内存: 128M

代码:

package 第十四届蓝桥杯三月真题刷题训练.day22;

import java.util.Scanner;

/**
 * @author yx
 * @date 2023-03-25 14:52
 */
public class 受伤的皇后_dfs {
    static int[][]map;
    static int ans=0;
    static int n;
    static int[] column;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n=scanner.nextInt();
        map=new int[n][n];
        column=new int[n];
        dfs(0);
        System.out.println(ans);
    }
    static void dfs(int i){
        if(i==n){//出口
            ans++;
        }
        //编列第i行的每一列
        for (int j = 0; j < n; j++) {
            if(check(i,j)){
                //第i行的皇后在第j列
                column[i]=j;
                //继续下一行遍历
                dfs(i+1);
            }
        }
    }
    //检查r行,l列是否可以放皇后
    static boolean check(int r,int l){
        for (int i = 0; i < r ; i++) {
            //在同一列,在斜对角(注意:因为i!=r所以不用判断在同一行)
            if(l==column[i]||(Math.abs(r-i)==Math.abs(l-column[i])&&(r-i)<3)){
                return false;
            }
        }
        return true;
    }
}

思路:

(1)核心思想是dfs深度搜索

(2)注意dfs必须要有一个出口

if(i==n){//出口
            ans++;
        }

(3)检查r行l列是否可以放

    //检查r行,l列是否可以放皇后
    static boolean check(int r,int l){
        for (int i = 0; i < r ; i++) {
            //在同一列,在斜对角(注意:因为i!=r所以不用判断在同一行)
            if(l==column[i]||(Math.abs(r-i)==Math.abs(l-column[i])&&(r-i)<3)){
                return false;
            }
        }
        return true;
    }

(4)因为我们是遍历每一行,所以行是已知的,定义一个数组存储每一行的列值

column=new int[n];

第 2 题:完全平方数

问题描述

一个整数 a 是一个完全平方数, 是指它是某一个整数的平方, 即存在一个 整数 b, 使得 a=b2。

给定一个正整数 n, 请找到最小的正整数 x, 使得它们的乘积是一个完全平 方数。

输入格式

输入一行包含一个正整数 n 。

输出格式

输出找到的最小的正整数 x 。

样例输入 1

12

样例输出 1

3

样例输入 2

15

样例输出 2

15

评测用例规模与约定

对于 30 的评测用例, 1≤n≤1000, 答案不超过 1000 。

对于 60 的评测用例, 1≤n≤10^8, 答案不超过 10^8 。

对于所有评测用例, 1≤n≤10^12, 答案不超过 10^12 。

运行限制

  • 最大运行时间:1s
  • 最大运行内存: 256M

代码:

package 第十四届蓝桥杯三月真题刷题训练.day22;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Scanner;

/**
 * @author yx
 * @date 2023-03-25 12:35
 */
public class 完全平方数 {
    static PrintWriter out =new PrintWriter(System.out);
    static BufferedReader ins=new BufferedReader(new InputStreamReader(System.in));
    static StreamTokenizer in=new StreamTokenizer(ins);
    /**
     * 输入
     * in.nextToken()
     * int a= (int)in.nval;
     *
     * 输出
     * out.print();
     * out.flush();
     *
     * 读文件:
     * BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("C:\\Users\\yx\\Desktop\\primes.txt")));
     * String s = br.readLine();s读取每一行数据
     * if (s == null)break;读取文件终止的语句
     **/
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long n=scanner.nextLong();
        /*
        1、找一个x使得x*n为一个平方数
        2、注意数据类型要用long
        3、如何找出这个最小数x呢,如果n是由a*a*b*b.....*y(y为不能开方的数)组成的话
        4、那我们是不是把x赋值为y,就可以保证n是完全平方数了,其中a、b都是小于等于sqrt(n)的
         */
        for (long i = 2; i*i <= n ; i++) {
            //如果这个n由(i*i)^k组成,就一直除到它没有i的平方为止
            while (n%(i*i)==0)n/=(i*i);
        }
        System.out.println(n);
    }
}

思路:

(1)找一个x使得x*n为一个平方数

(2)注意数据范围要用long

(3)如何找出这个最小数x呢,如果n是由a*a*b*b.....*y(y为不能开方的数)组成的话

(4)那我们是不是最后只需要把y赋值给x,就可以保证x*n是完全平方数了

注意:

  • 如果这个n由(i*i)^k组成,即可以由多个相同平方数i构成,我们需要一直除到它没有i平方为止
while (n%(i*i)==0)n/=(i*i);

第 3 题:123_前缀和_二分_long

题目描述

小蓝发现了一个有趣的数列,这个数列的前几项如下:

1,1,2,1,2,3,1,2,3,4,⋯

小蓝发现,这个数列前 1 项是整数 1,接下来 2 项是整数 1 至 2,接下来 3 项是整数 1 至 3,接下来 4 项是整数 1 至 4,依次类推。

小蓝想知道,这个数列中,连续一段的和是多少。

输入描述

输入的第一行包含一个整数 T,表示询问的个数。

接下来 T 行,每行包含一组询问,其中第 i 行包含两个整数 li​ 和 ri ,表示询问数列中第 li​ 个数到第 ri​ 个数的和。

输出描述

输出 T 行,每行包含一个整数表示对应询问的答案。

输入输出样例

示例

输入

3
1 1
1 3
5 8

输出

1
4
8

评测用例规模与约定

对于 10% 的评测用例,1≤T≤30,1≤li≤ri≤100。

对于 20% 的评测用例,1≤T≤100,1≤li≤ri≤1000。

对于 40% 的评测用例,1≤T≤1000,1≤li≤ri≤10^6。

对于 70% 的评测用例,1≤T≤10000,1≤li≤ri≤10^9。

对于 80% 的评测用例,1≤T≤1000,1≤li≤ri≤10^12。

对于 90% 的评测用例,1≤T≤10000,1≤li≤ri≤10^12。

对于所有评测用例,1≤T≤100000,1≤li≤ri≤10^12。

运行限制

  • 最大运行时间:5s
  • 最大运行内存: 256M

代码:

package 第十四届蓝桥杯三月真题刷题训练.day22;

import java.io.*;

/**
 * @author yx
 * @date 2023-03-25 13:56
 */
public class 一23_二分 {
    static PrintWriter out = new PrintWriter(System.out);
    static BufferedReader ins = new BufferedReader(new InputStreamReader(System.in));
    static StreamTokenizer in = new StreamTokenizer(ins);
    static long[] S = new long[1500000];//大区间
    static long[] a = new long[1500000];//小区间

    /**
     * 输入
     * in.nextToken()
     * int a= (int)in.nval;
     * <p>
     * 输出
     * out.print();
     * out.flush();
     * <p>
     * 读文件:
     * BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("C:\\Users\\yx\\Desktop\\primes.txt")));
     * String s = br.readLine();s读取每一行数据
     * if (s == null)break;读取文件终止的语句
     **/
    public static void main(String[] args) throws IOException {
        for (int i = 1; i < 1500000; i++) {
            a[i] = a[i - 1] + i;//对小区间前缀和
            S[i] = S[i - 1] + a[i];//对大区间前缀和
        }
        //注意数据类型long
        in.nextToken();
        int n = (int) in.nval;
        while (n != 0) {
            n--;
            String[] sp = ins.readLine().split(" ");
            long l = Long.parseLong(sp[0]);
            long r = Long.parseLong(sp[1]);
            String ans = (Sum(r) - Sum(l - 1)) + "";
            System.out.println(ans);
        }
    }

    //求整体前缀和
    static long Sum(long m) {
        if (m == 0) return 0;
        //1、用等差数列求和公式是O(n^1/2)的复杂度
//        int i = 1;
//        //找i的区间位置
//        while (true){
//            if(((long)i*(long)(i+1)/2)>=m){
//                break;
//            }
//            i++;
//        }
        //2、二分优化
        long l=1;
        long r=1500000;
        long ans=1;
        while (l <= r) {
            //二分
            long mid = (l + r) / 2;
            if (a[(int) mid]<m) {
                ans = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
//        System.out.print(ans);
//        ans--;
        return S[(int) ans ] + a[(int) (m - a[(int) ans ])];
    }
}

思路:

(1)这道题目和核心思想是前缀和

(2)直接求所有数据的前缀和的话我们不好求,一个是数据下标会爆炸(下标不可能是10^12)

(3)我用把它进行划分多个大区间:1为第一个大区间;1 2为第二个大区间;1 2 3为第三个大区间;1 2 3 4为第四个大区间......

(4)我们用S把每一个大区间的和进行存储

(5)再定义一个小区间a,a可以用来定位也可以用来迭代数据

  1. 定位:输入一个m,我们通过与a[i]的比较能快速找到第m个数位于第i个大区间
  2. 迭代数据:用于S数组初始化迭代数据;用于输出第i个大区间的第j位(j=m-a[i])前缀和

(6)因为每个大区间个数呈等差数列增长,我们通过(n)*(n+1)/2这个公式来定位m的位置,复杂度为O(\sqrt{n}),最后能通过8个点,超时2个点

        //1、用等差数列求和公式是O(n^1/2)的复杂度
//        int i = 1;
//        //找i的区间位置
//        while (true){
//            if(((long)i*(long)(i+1)/2)>=m){
//                break;
//            }
//            i++;
//        }

(7)用二分进行优化复杂度O(logN)

        //2、二分优化
        long l=1;
        long r=1500000;
        long ans=1;
        while (l <= r) {
            //二分
            long mid = (l + r) / 2;
            if (a[(int) mid]<m) {
                ans = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
//        System.out.print(ans);
//        ans--;
        return S[(int) ans ] + a[(int) (m - a[(int) ans ])];

第 4 题:求阶乘_二分_long 

问题描述

满足 N ! 的末尾恰好有 K 个 0 的最小的 N 是多少?

如果这样的 N 不存在输出 −1 。

输入格式

一个整数 K 。

输出格式

一个整数代表答案。

样例输入

2

样例输出

10

评测用例规模与约定

对于 30% 的数据, 1≤K≤10^6

对于 100% 的数据, 1≤K≤10^18

运行限制

  • 最大运行时间:3s
  • 最大运行内存: 512M

代码:

package 第十四届蓝桥杯三月真题刷题训练.day22;

import java.util.Scanner;

/**
 * @author yx
 * @date 2023-03-25 13:02
 */
public class 求阶乘_二分 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        //注意数据范围用long
        long K = scanner.nextLong();
//        long r = 1000000000000000000L;
        long r = 9000000000000000000L;
        long l = 1;
        long ans=0;
        while (l <= r) {
            long mid = (l + r) / 2;
            if (Find_5(mid)<K) {
//                System.out.println(Find_5(mid));
                ans = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        if(Find_5(ans+1)==K) {
            System.out.print(ans + 1);
        }else {
            System.out.println(-1);
        }
    }

    //末尾1个0对应一个因子5和一个因子2.因为2的个数是远远大于5的个数的所以只需要找5有多少即可
    static long Find_5(long n) {
        long ans = 0;
        //为什么要循环除5呢?
        /*
        我们举一个例子: n=100时
        (1) n/5=20;表示在1~n有20个区间大小为5的区间(5只能分解一个5)
        (2) (n/5)/5=4;表示在1~n有4个区间大小为25的区间(25可以分解两个5)
        (3)((n/5)/5)/5=0;表示1~n有0个区间大小为125的区间(125可以分解3个5)
         */
        while (n / 5 != 0) {
            n /= 5;
            ans += n;
        }
        return ans;
    }
}

思路:

(1)数据范围long

(2)末尾1个0对应一个因子5和一个因子2,又由于2的个数是远远大于5的个数的所以只需要找5有多少即可

static long Find_5(long n) 

(3)在Find_5这个函数里为什么要循环除5呢?

我们举一个例子: n=100时
(1) n/5=20;表示在1~n有20个区间大小为5的区间(5只能分解一个5)
(2) (n/5)/5=4;表示在1~n有4个区间大小为25的区间(25可以分解两个5)
(3)((n/5)/5)/5=0;表示1~n有0个区间大小为125的区间(125可以分解3个5)

(4)最后用二分来找n(二分模板)

   while (l <= r) {
            long mid = (l + r) / 2;
            if (Find_5(mid)<K) {
//                System.out.println(Find_5(mid));
                ans = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }

(5)注意这道题目中二分的r的初始值,如果用Long.MaxValue是只能过9个点的,因为Long.MaxValue的取值是2^63-1,而long的范围2^64-1,所以初始值r应该是2^64-1才可以

//        long r = 1000000000000000000L;
//        long r=Long.MAX_VALUE;
        long r = 9000000000000000000L;

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/3273.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Jenkins--邮件通知设置与构建日志邮件通知设置(踩过很多坑之后,记录一下)

1为啥要配置邮件通知配置邮件通知的目的是为了给用户发送构建结果的状态&#xff0c;以便用户知晓构建任务后的结果。2 开始配置邮件通知2.1 插件准备先检查Jenkins是否安装了Email Extension Plugin 插件&#xff0c;检查方法如下&#xff1a;进入Jenkins-->Manage Jenkins…

uni-app:登录与支付--用户信息

用户信息 实现用户头像昵称区域的基本布局 在 my-userinfo 组件中&#xff0c;定义如下的 UI 结构&#xff1a; <template><view class"my-userinfo-container"><!-- 头像昵称区域 --><view class"top-box"><image src"…

蓝桥杯刷题冲刺 | 倒计时18天

作者&#xff1a;指针不指南吗 专栏&#xff1a;蓝桥杯倒计时冲刺 &#x1f43e;马上就要蓝桥杯了&#xff0c;最后的这几天尤为重要&#xff0c;不可懈怠哦&#x1f43e; 文章目录0.知识点1.乳草的入侵今天写 搜索题 0.知识点 DFS 设计步骤 确定该题目的状态&#xff08;包括边…

串口,IIC,SPI,USB等总线硬件知识总结

串口&#xff0c;IIC&#xff0c;SPI&#xff0c;USB等总线硬件知识总结 文章目录串口&#xff0c;IIC&#xff0c;SPI&#xff0c;USB等总线硬件知识总结1 串口2.I2C3.SPI4.USB控制&#xff08;Control&#xff09;传输方式同步&#xff08;Isochronous&#xff09;传输方式中…

vue3+vite+ts 搭建脚手架01创建vite项目并且在项目中初次使用router

vue3vite 搭建脚手架01创建vite项目并且在项目中使用router 1.使用yarn安装vite项目 yarn create vite 搭建vite项目 在开发语言中选择vuets2.安装现在最新的 vue-router4 yarn add vue-router4 在packger中检查是否成功安装3.简单配置router文件 在项目中新建views和…

【C++】map、set、multimap、multiset的介绍和使用

我讨厌世俗&#xff0c;也耐得住孤独。 文章目录一、键值对二、树形结构的关联式容器1.set1.1 set的介绍1.2 set的使用1.3 multiset的使用2.map2.1 map的介绍2.2 map的使用2.3 multimap的使用三、两道OJ题1.前K个高频单词&#xff08;less<T>小于号是小的在左面升序&…

如何将字符串反转?

参考答案 使用 StringBuilder 或 StringBuffer 的 reverse 方法&#xff0c;本质都调用了它们的父类 AbstractStringBuilder 的 reverse 方法实现。&#xff08;JDK1.8&#xff09;不考虑字符串中的字符是否是 Unicode 编码&#xff0c;自己实现。递归1. public AbstractStrin…

优秀程序员的5个特征,你在第几层?

每个人程序员都对未来的职业发展有着憧憬和规划&#xff0c;要做架构师、要做技术总监、要做CTO。但现实总是复杂的&#xff0c;日复一日的工作与生活总能让人一次又一次地陷入迷茫。大部分原因就是对职业发展轨迹和自我能力提升的一般规律缺乏认识&#xff0c;做事找不到方向或…

WebSocket 测试工具

一、WebSocket 简介 WebSocket是一种在单个TCP连接上进行全双工通信的协议。 WebSocket使得客户端和服务器之间的数据交换变得更加简单&#xff0c;允许服务端主动向客户端推送数据。在WebSocket API中&#xff0c;浏览器和服务器只需要完成一次握手&#xff0c;两者之间就直…

MySQL数据库管理系统安装部署——Linux

MySQL数据库管理系统安装部署——Linux 简介 MySQL数据库管理系统&#xff08;后续简称MySQL)&#xff0c;是一款知名的数据库系统&#xff0c;其特点是:轻量、简单、功能丰富。MySQL数据库可谓是软件行业的明星产品&#xff0c;无论是后端开发、大数据、AI、运维、测试等各类…

linux入门---操作体统的概念

什么是操作系统 操作系统是一个对软硬件资源进行管理的软件。计算机由一堆硬件组成&#xff0c;这些硬件遵循着冯诺依曼体系结构 在这个硬件的基础上还有一个软件叫做操作系统 操作系统的任务是对硬件进行管理&#xff0c;既然是管理的话操作系统得访问到底层的硬件&#xf…

【贪心算法】一文让你学会“贪心”(贪心算法详解及经典案例)

文章目录前言如何理解“贪心算法”&#xff1f;贪心算法实战分析1.分糖果2.钱币找零3.区间覆盖内容小结最后说一句&#x1f431;‍&#x1f409;作者简介&#xff1a;大家好&#xff0c;我是黑洞晓威&#xff0c;一名大二学生&#xff0c;希望和大家一起进步。 &#x1f47f;本…

Spring Boot 各层作用与联系

目录 1 Entity 层 2 DAO 层 3 Service 层 4 Controller 层 Spring Boot 各层之间的联系&#xff1a; controller 层-----> service 层(接口->接口实现类) -----> dao 层的.mapper 文件 -----> 和 mapper 层里的.xml 文件对应 1 Entity 层 实体层&#xff0c;…

Java笔记_6(面向对象)

Java笔记_6一、面向对象1.1、设计对象并使用1.2、封装1.3、就近原则和this关键字1.4、构造方法1.5、标准的JavaBean类1.6、对象内存图1.7、基本数据类型和引用数据类型1.8、this的内存原理1.9、成员和局部二、面向对象&#xff08;综合练习&#xff09;2.1、文字版格斗游戏2.2、…

正式环境关闭swagger

直接上步骤&#xff0c;如图&#xff1a;1&#xff0c;启动判断写在相应的环境配置文件中&#xff0c;根据条件判断是否启动 swagger &#xff1a;添加配置项&#xff1a;swagger.is.enable配置文件中添加&#xff1a;#是否激活 swagger true or falseswagger.is.enabletrue2&a…

【Linux】-初识Linux

作者&#xff1a;学Java的冬瓜 博客主页&#xff1a;☀冬瓜的主页&#x1f319; 专栏&#xff1a;【Linux】 分享&#xff1a;逆着光行走&#xff0c;任风吹雨打。 ——《起风了》 主要内容&#xff1a;Linux的一些最基本指令&#xff0c;Linux的小程序&#xff0c;Linux关于连…

从暴力递归到动态规划(2)小乖,你也在为转移方程而烦恼吗?

前引&#xff1a;继上篇我们讲到暴力递归的过程&#xff0c;这一篇blog我们将继续对从暴力递归到动态规划的实现过程&#xff0c;与上篇类似&#xff0c;我们依然采用题目的方式对其转化过程进行论述。上篇博客&#xff1a;https://blog.csdn.net/m0_65431718/article/details/…

看完这篇 教你玩转渗透测试靶机vulnhub——My File Server: 1

Vulnhub靶机My File Server: 1渗透测试详解Vulnhub靶机介绍&#xff1a;Vulnhub靶机下载&#xff1a;Vulnhub靶机安装&#xff1a;Vulnhub靶机漏洞详解&#xff1a;①&#xff1a;信息收集&#xff1a;②&#xff1a;FTP匿名登入&#xff1a;③&#xff1a;SMB共享服务&#xf…

【微信小程序】-- 使用 Git 管理项目(五十)

&#x1f48c; 所属专栏&#xff1a;【微信小程序开发教程】 &#x1f600; 作  者&#xff1a;我是夜阑的狗&#x1f436; &#x1f680; 个人简介&#xff1a;一个正在努力学技术的CV工程师&#xff0c;专注基础和实战分享 &#xff0c;欢迎咨询&#xff01; &…

【Docker】Compose容器编排LNMP上云

文章目录什么是Docker-Compose下载安装官网官网下载安装卸载Compose核心概念一文件两要素三个步骤Compose常用命令DjangoMysqlRedisNginx部署部署架构构建django容器 - - - dockerfile编写构建Nginx容器docker-compose 编排容器Django项目配置custom_webmysql容器redis容器Djan…