目录
第 1 题：受伤的皇后_dfs
题目描述
输入描述
输出描述
输入输出样例
运行限制
代码：
思路：
第 2 题：完全平方数
问题描述
输入格式
输出格式
样例输入 1
样例输出 1
样例输入 2
样例输出 2
评测用例规模与约定
运行限制
代码：
思路：
第 3 题：123_前缀和_二分_long
题目描述
输入描述
输出描述
输入输出样例
评测用例规模与约定
运行限制
代码：
思路：
第 4 题：求阶乘_二分_long
问题描述
输入格式
输出格式
样例输入
样例输出
评测用例规模与约定
运行限制
代码：
思路：
第 1 题：受伤的皇后_dfs
题目描述
有一个 n×n 的国际象棋棋盘（n 行 n 列的方格图），请在棋盘中摆放 n 个受伤的国际象棋皇后，要求：
- 任何两个皇后不在同一行。
- 任何两个皇后不在同一列。
- 如果两个皇后在同一条 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是完全平方数了
注意：
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可以用来定位也可以用来迭代数据
- 定位：输入一个m，我们通过与a[i]的比较能快速找到第m个数位于第i个大区间
- 迭代数据:用于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;
