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

时间:2022-08-02 01:23:24

目录

第 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;
    }
}

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

思路:

(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);
    }
}

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

思路:

(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 ])];
    }
}

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

思路:

(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(第十四届蓝桥杯三月真题刷题训练——第 22 天),最后能通过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 ])];

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

第 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;
    }
}

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

思路:

(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;

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