第十四届蓝桥杯三月真题刷题训练——第 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、注意数据类型要用long3、如何找出这个最小数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];//对大区间前缀和}//注意数据类型longin.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(),最后能通过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);//注意数据范围用longlong 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;