目錄

第 1 題：受傷的皇后_dfs

題目描述

輸入描述

輸出描述

輸入輸出樣例

運(yùn)行限制

代碼：

思路：

第 2 題：完全平方數(shù)

問(wèn)題描述

輸入格式

輸出格式

樣例輸入 1

樣例輸出 1

樣例輸入 2

樣例輸出 2

評(píng)測(cè)用例規(guī)模與約定

運(yùn)行限制

代碼：

思路：

第 3 題：123_前綴和_二分_long

題目描述

輸入描述

輸出描述

輸入輸出樣例

評(píng)測(cè)用例規(guī)模與約定

運(yùn)行限制

代碼：

思路：

第 4 題：求階乘_二分_long?

問(wèn)題描述

輸入格式

輸出格式

樣例輸入

樣例輸出

評(píng)測(cè)用例規(guī)模與約定

運(yùn)行限制

代碼：

思路：

---

第 1 題：受傷的皇后_dfs

題目描述

有一個(gè) n×n 的國(guó)際象棋棋盤（n 行 n 列的方格圖），請(qǐng)?jiān)谄灞P中擺放 n 個(gè)受傷的國(guó)際象棋皇后，要求：

1. 任何兩個(gè)皇后不在同一行。
2. 任何兩個(gè)皇后不在同一列。
3. 如果兩個(gè)皇后在同一條 45 度角的斜線上，這兩個(gè)皇后之間行號(hào)的差值至少為 3 。

請(qǐng)問(wèn)一共有多少種擺放方案。

輸入描述

輸入的第一行包含一個(gè)整數(shù) n。

其中，1≤n≤10。

輸出描述

輸出一個(gè)整數(shù)，表示答案。

輸入輸出樣例

示例 1

輸入

4

輸出

2

運(yùn)行限制

• 最大運(yùn)行時(shí)間：1s
• 最大運(yùn)行內(nèi)存: 128M

代碼：

package 第十四屆藍(lán)橋杯三月真題刷題訓(xùn)練.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;//繼續(xù)下一行遍歷dfs(i+1);}}}//檢查r行，l列是否可以放皇后static boolean check(int r,int l){for (int i = 0; i < r ; i++) {//在同一列，在斜對(duì)角（注意：因?yàn)閕!=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必須要有一個(gè)出口

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

(3)檢查r行l(wèi)列是否可以放

    //檢查r行，l列是否可以放皇后static boolean check(int r,int l){for (int i = 0; i < r ; i++) {//在同一列，在斜對(duì)角（注意：因?yàn)閕!=r所以不用判斷在同一行）if(l==column[i]||(Math.abs(r-i)==Math.abs(l-column[i])&&(r-i)<3)){return false;}}return true;}

（4）因?yàn)槲覀兪潜闅v每一行，所以行是已知的，定義一個(gè)數(shù)組存儲(chǔ)每一行的列值

column=new int[n];

第 2 題：完全平方數(shù)

問(wèn)題描述

一個(gè)整數(shù) a 是一個(gè)完全平方數(shù), 是指它是某一個(gè)整數(shù)的平方, 即存在一個(gè) 整數(shù) b, 使得 a=b2。

給定一個(gè)正整數(shù) n, 請(qǐng)找到最小的正整數(shù) x, 使得它們的乘積是一個(gè)完全平 方數(shù)。

輸入格式

輸入一行包含一個(gè)正整數(shù) n 。

輸出格式

輸出找到的最小的正整數(shù) x 。

樣例輸入 1

12

樣例輸出 1

3

樣例輸入 2

15

樣例輸出 2

15

評(píng)測(cè)用例規(guī)模與約定

對(duì)于 30 的評(píng)測(cè)用例, 1≤n≤1000, 答案不超過(guò) 1000 。

對(duì)于 60 的評(píng)測(cè)用例, 1≤n≤10^8, 答案不超過(guò) 10^8 。

對(duì)于所有評(píng)測(cè)用例, 1≤n≤10^12, 答案不超過(guò) 10^12 。

運(yùn)行限制

• 最大運(yùn)行時(shí)間：1s
• 最大運(yùn)行內(nèi)存: 256M

代碼：

package 第十四屆藍(lán)橋杯三月真題刷題訓(xùn)練.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 完全平方數(shù) {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讀取每一行數(shù)據(jù)* if (s == null)break;讀取文件終止的語(yǔ)句**/public static void main(String[] args) {Scanner scanner = new Scanner(System.in);long n=scanner.nextLong();/*1、找一個(gè)x使得x*n為一個(gè)平方數(shù)2、注意數(shù)據(jù)類型要用long3、如何找出這個(gè)最小數(shù)x呢,如果n是由a*a*b*b.....*y(y為不能開(kāi)方的數(shù))組成的話4、那我們是不是把x賦值為y，就可以保證n是完全平方數(shù)了,其中a、b都是小于等于sqrt(n)的*/for (long i = 2; i*i <= n ; i++) {//如果這個(gè)n由(i*i)^k組成，就一直除到它沒(méi)有i的平方為止while (n%(i*i)==0)n/=(i*i);}System.out.println(n);}
}

思路：

(1)找一個(gè)x使得x*n為一個(gè)平方數(shù)

(2)注意數(shù)據(jù)范圍要用long

(3)如何找出這個(gè)最小數(shù)x呢,如果n是由a*a*b*b.....*y(y為不能開(kāi)方的數(shù))組成的話

(4)那我們是不是最后只需要把y賦值給x，就可以保證x*n是完全平方數(shù)了

注意：

• 如果這個(gè)n由(i*i)^k組成，即可以由多個(gè)相同平方數(shù)i構(gòu)成，我們需要一直除到它沒(méi)有i平方為止

while (n%(i*i)==0)n/=(i*i);

第 3 題：123_前綴和_二分_long

題目描述

小藍(lán)發(fā)現(xiàn)了一個(gè)有趣的數(shù)列，這個(gè)數(shù)列的前幾項(xiàng)如下：

1,1,2,1,2,3,1,2,3,4,?

小藍(lán)發(fā)現(xiàn)，這個(gè)數(shù)列前 1 項(xiàng)是整數(shù) 1，接下來(lái) 2 項(xiàng)是整數(shù) 1 至 2，接下來(lái) 3 項(xiàng)是整數(shù) 1 至 3，接下來(lái) 4 項(xiàng)是整數(shù) 1 至 4，依次類推。

小藍(lán)想知道，這個(gè)數(shù)列中，連續(xù)一段的和是多少。

輸入描述

輸入的第一行包含一個(gè)整數(shù) T，表示詢問(wèn)的個(gè)數(shù)。

接下來(lái) T 行，每行包含一組詢問(wèn)，其中第 i 行包含兩個(gè)整數(shù) li? 和 ri ，表示詢問(wèn)數(shù)列中第 li? 個(gè)數(shù)到第 ri? 個(gè)數(shù)的和。

輸出描述

輸出 T 行，每行包含一個(gè)整數(shù)表示對(duì)應(yīng)詢問(wèn)的答案。

輸入輸出樣例

示例

輸入

3
1 1
1 3
5 8

輸出

1
4
8

評(píng)測(cè)用例規(guī)模與約定

對(duì)于 10% 的評(píng)測(cè)用例，1≤T≤30,1≤li≤ri≤100。

對(duì)于 20% 的評(píng)測(cè)用例，1≤T≤100,1≤li≤ri≤1000。

對(duì)于 40% 的評(píng)測(cè)用例，1≤T≤1000,1≤li≤ri≤10^6。

對(duì)于 70% 的評(píng)測(cè)用例，1≤T≤10000,1≤li≤ri≤10^9。

對(duì)于 80% 的評(píng)測(cè)用例，1≤T≤1000,1≤li≤ri≤10^12。

對(duì)于 90% 的評(píng)測(cè)用例，1≤T≤10000,1≤li≤ri≤10^12。

對(duì)于所有評(píng)測(cè)用例，1≤T≤100000,1≤li≤ri≤10^12。

運(yùn)行限制

• 最大運(yùn)行時(shí)間：5s
• 最大運(yùn)行內(nèi)存: 256M

代碼：

package 第十四屆藍(lán)橋杯三月真題刷題訓(xùn)練.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];//大區(qū)間static long[] a = new long[1500000];//小區(qū)間/*** 輸入* 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讀取每一行數(shù)據(jù)* if (s == null)break;讀取文件終止的語(yǔ)句**/public static void main(String[] args) throws IOException {for (int i = 1; i < 1500000; i++) {a[i] = a[i - 1] + i;//對(duì)小區(qū)間前綴和S[i] = S[i - 1] + a[i];//對(duì)大區(qū)間前綴和}//注意數(shù)據(jù)類型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、用等差數(shù)列求和公式是O(n^1/2)的復(fù)雜度
//        int i = 1;
//        //找i的區(qū)間位置
//        while (true){
//            if(((long)i*(long)(i+1)/2)>=m){
//                break;
//            }
//            i++;
//        }//2、二分優(yōu)化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)直接求所有數(shù)據(jù)的前綴和的話我們不好求，一個(gè)是數(shù)據(jù)下標(biāo)會(huì)爆炸(下標(biāo)不可能是10^12)

(3)我用把它進(jìn)行劃分多個(gè)大區(qū)間：1為第一個(gè)大區(qū)間；1 2為第二個(gè)大區(qū)間；1 2 3為第三個(gè)大區(qū)間；1 2 3 4為第四個(gè)大區(qū)間......

(4)我們用S把每一個(gè)大區(qū)間的和進(jìn)行存儲(chǔ)

(5)再定義一個(gè)小區(qū)間a，a可以用來(lái)定位也可以用來(lái)迭代數(shù)據(jù)

1. 定位：輸入一個(gè)m，我們通過(guò)與a[i]的比較能快速找到第m個(gè)數(shù)位于第i個(gè)大區(qū)間
2. 迭代數(shù)據(jù):用于S數(shù)組初始化迭代數(shù)據(jù);用于輸出第i個(gè)大區(qū)間的第j位(j=m-a[i])前綴和

(6)因?yàn)槊總€(gè)大區(qū)間個(gè)數(shù)呈等差數(shù)列增長(zhǎng),我們通過(guò)(n)*(n+1)/2這個(gè)公式來(lái)定位m的位置,復(fù)雜度為O(),最后能通過(guò)8個(gè)點(diǎn),超時(shí)2個(gè)點(diǎn)

        //1、用等差數(shù)列求和公式是O(n^1/2)的復(fù)雜度
//        int i = 1;
//        //找i的區(qū)間位置
//        while (true){
//            if(((long)i*(long)(i+1)/2)>=m){
//                break;
//            }
//            i++;
//        }

(7)用二分進(jìn)行優(yōu)化復(fù)雜度O(logN)

        //2、二分優(yōu)化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?

問(wèn)題描述

滿足 N ! 的末尾恰好有 K 個(gè) 0 的最小的 N 是多少?

如果這樣的 N 不存在輸出 ?1 。

輸入格式

一個(gè)整數(shù) K 。

輸出格式

一個(gè)整數(shù)代表答案。

樣例輸入

2

樣例輸出

10

評(píng)測(cè)用例規(guī)模與約定

對(duì)于 30% 的數(shù)據(jù), 1≤K≤10^6

對(duì)于 100% 的數(shù)據(jù), 1≤K≤10^18

運(yùn)行限制

• 最大運(yùn)行時(shí)間：3s
• 最大運(yùn)行內(nèi)存: 512M

代碼：

package 第十四屆藍(lán)橋杯三月真題刷題訓(xùn)練.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);//注意數(shù)據(jù)范圍用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個(gè)0對(duì)應(yīng)一個(gè)因子5和一個(gè)因子2.因?yàn)?的個(gè)數(shù)是遠(yuǎn)遠(yuǎn)大于5的個(gè)數(shù)的所以只需要找5有多少即可static long Find_5(long n) {long ans = 0;//為什么要循環(huán)除5呢？/*我們舉一個(gè)例子: n=100時(shí)(1) n/5=20;表示在1~n有20個(gè)區(qū)間大小為5的區(qū)間(5只能分解一個(gè)5)(2) (n/5)/5=4;表示在1~n有4個(gè)區(qū)間大小為25的區(qū)間(25可以分解兩個(gè)5)(3)((n/5)/5)/5=0;表示1~n有0個(gè)區(qū)間大小為125的區(qū)間(125可以分解3個(gè)5)*/while (n / 5 != 0) {n /= 5;ans += n;}return ans;}
}

思路：

(1)數(shù)據(jù)范圍long

(2)末尾1個(gè)0對(duì)應(yīng)一個(gè)因子5和一個(gè)因子2,又由于2的個(gè)數(shù)是遠(yuǎn)遠(yuǎn)大于5的個(gè)數(shù)的所以只需要找5有多少即可

static long Find_5(long n) 

(3)在Find_5這個(gè)函數(shù)里為什么要循環(huán)除5呢？

我們舉一個(gè)例子: n=100時(shí)
(1) n/5=20;表示在1~n有20個(gè)區(qū)間大小為5的區(qū)間(5只能分解一個(gè)5)
(2) (n/5)/5=4;表示在1~n有4個(gè)區(qū)間大小為25的區(qū)間(25可以分解兩個(gè)5)
(3)((n/5)/5)/5=0;表示1~n有0個(gè)區(qū)間大小為125的區(qū)間(125可以分解3個(gè)5)

(4)最后用二分來(lái)找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是只能過(guò)9個(gè)點(diǎn)的，因?yàn)長(zhǎng)ong.MaxValue的取值是2^63-1，而long的范圍2^64-1，所以初始值r應(yīng)該是2^64-1才可以

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

?