检察院门户网站建设自查自纠报告,响应是网站怎么做,加强公司内部网站建设,wordpress 批量修改分类目录
第 1 题#xff1a;受伤的皇后_dfs
题目描述
输入描述
输出描述
输入输出样例
运行限制
代码#xff1a;
思路#xff1a;
第 2 题#xff1a;完全平方数
问题描述
输入格式
输出格式
样例输入 1
样例输出 1
样例输入 2
样例输出 2
评测用例规模与约…目录
第 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 ans0;static int n;static int[] column;public static void main(String[] args) {Scanner scanner new Scanner(System.in);nscanner.nextInt();mapnew int[n][n];columnnew int[n];dfs(0);System.out.println(ans);}static void dfs(int i){if(in){//出口ans;}//编列第i行的每一列for (int j 0; j n; j) {if(check(i,j)){//第i行的皇后在第j列column[i]j;//继续下一行遍历dfs(i1);}}}//检查r行l列是否可以放皇后static boolean check(int r,int l){for (int i 0; i r ; i) {//在同一列在斜对角注意因为i!r所以不用判断在同一行if(lcolumn[i]||(Math.abs(r-i)Math.abs(l-column[i])(r-i)3)){return false;}}return true;}
}思路 (1)核心思想是dfs深度搜索 (2)注意dfs必须要有一个出口 if(in){//出口ans;} (3)检查r行l列是否可以放 //检查r行l列是否可以放皇后static boolean check(int r,int l){for (int i 0; i r ; i) {//在同一列在斜对角注意因为i!r所以不用判断在同一行if(lcolumn[i]||(Math.abs(r-i)Math.abs(l-column[i])(r-i)3)){return false;}}return true;} 4因为我们是遍历每一行所以行是已知的定义一个数组存储每一行的列值 columnnew int[n]; 第 2 题完全平方数 问题描述 一个整数 a 是一个完全平方数, 是指它是某一个整数的平方, 即存在一个 整数 b, 使得 ab2。 给定一个正整数 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 insnew BufferedReader(new InputStreamReader(System.in));static StreamTokenizer innew 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 nscanner.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)(i1)/2)m){
// break;
// }
// i;
// }//2、二分优化long l1;long r1500000;long ans1;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)再定义一个小区间aa可以用来定位也可以用来迭代数据 定位输入一个m我们通过与a[i]的比较能快速找到第m个数位于第i个大区间迭代数据:用于S数组初始化迭代数据;用于输出第i个大区间的第j位(jm-a[i])前缀和(6)因为每个大区间个数呈等差数列增长,我们通过(n)*(n1)/2这个公式来定位m的位置,复杂度为O(),最后能通过8个点,超时2个点 //1、用等差数列求和公式是O(n^1/2)的复杂度
// int i 1;
// //找i的区间位置
// while (true){
// if(((long)i*(long)(i1)/2)m){
// break;
// }
// i;
// } (7)用二分进行优化复杂度O(logN) //2、二分优化long l1;long r1500000;long ans1;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 ans0;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(ans1)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呢/*我们举一个例子: n100时(1) n/520;表示在1~n有20个区间大小为5的区间(5只能分解一个5)(2) (n/5)/54;表示在1~n有4个区间大小为25的区间(25可以分解两个5)(3)((n/5)/5)/50;表示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呢 我们举一个例子: n100时
(1) n/520;表示在1~n有20个区间大小为5的区间(5只能分解一个5)
(2) (n/5)/54;表示在1~n有4个区间大小为25的区间(25可以分解两个5)
(3)((n/5)/5)/50;表示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 rLong.MAX_VALUE;long r 9000000000000000000L;
