目錄
說在前面
試題 A: 階乘求和
代碼：
題目分析：
試題 B: 幸運數(shù)字
代碼：
題目分析：
試題 D: 矩形總面積
代碼：
題目分析：
試題 G: 買二贈一
代碼：
題目分析：
試題 H: 合并石子
代碼：
題目思路：
說在最后
說在前面
比賽結(jié)束啦，可能這是本科生涯的最后一次藍橋杯啦！賽前也刷了一部分的題，不管最后能不能相約北京，還是要感謝我執(zhí)梗舉辦的三十天打卡活動，辛苦啦！
我把這段時間刷的題也也整理成了一個小專欄：《23年藍橋杯刷題30天打卡》
關(guān)于這次藍橋杯，比賽的時候沒有看D題，G和H花了好長時間，嗚嗚....，等比賽結(jié)束的時候邊走邊看題才知道是送分題，考后相當(dāng)于是補題了，好遺憾，痛失10分，也許人生就是這樣，十之八九是遺憾，但這又有何妨呢，前方康莊大道，還有很多美好的事情等著我呢?。?！
下面就把這次我看過的并且感覺能做的題目寫一下吧，如有錯誤，歡迎評論區(qū)指正?。?/strong>
試題 A: 階乘求和
【問題描述】令 S = 1! + 2! + 3! + ... + 202320232023! ，求 S 的末尾 9 位數(shù)字。提示：答案首位不為 0 。【答案提交】這是一道結(jié)果填空的題，你只需要算出結(jié)果后提交即可。本題的結(jié)果為一個整數(shù)，在提交答案時只填寫這個整數(shù)，填寫多余的內(nèi)容將無法得分。
代碼：
/**
* @author yx
* @date 2023-04-08 9:11
*/
public class t1 {
public static void main(String[] args) {
// 420940313
long ans=0;
long temp=1000000000;
long temp1=1;
for (long i = 1; i <= 202320232023L ; i++) {
temp1=((temp1%temp)*(i%temp))%temp;
ans=(ans%temp+temp1%temp)%temp;
System.out.println("temp1是："+temp1+" ans是："+ans+" i是："+i);
}
// System.out.println("答案是："+ans);
}
}
題目分析：
答案是：420940313
- 這道題目最后給的是202320232023的階乘，這玩意要是用電腦暴力解，估計要很長時間（我一開始也是無腦暴力，但是感覺要好久）
- 這題完全不需要開到202320232023，因為從39！開始，后面階乘和的末尾9位數(shù)字就不發(fā)生改變了
試題 B: 幸運數(shù)字
試題 B: 幸運數(shù)字本題總分： 5 分【問題描述】哈沙德數(shù)是指在某個固定的進位制當(dāng)中，可以被各位數(shù)字之和整除的正整數(shù)。例如 126 是十進制下的一個哈沙德數(shù)，因為 (126) 10 mod (1+2+6) = 0 ； 126也是八進制下的哈沙德數(shù)，因為 (126) 10 = (176) 8 ， (126) 10 mod (1 + 7 + 6) = 0 ；同時 126 也是 16 進制下的哈沙德數(shù)，因為 (126) 10 = (7 e ) 16 ， (126) 10 mod (7 +e ) = 0 。小藍認(rèn)為，如果一個整數(shù)在二進制、八進制、十進制、十六進制下均為哈沙德數(shù)，那么這個數(shù)字就是幸運數(shù)字，第 1 至第 10 個幸運數(shù)字的十進制表示為： 1 , 2 , 4 , 6 , 8 , 40 , 48 , 72 , 120 , 126 . . . 。現(xiàn)在他想知道第 2023 個幸運數(shù)字是多少？你只需要告訴小藍這個整數(shù)的十進制表示即可。【答案提交】這是一道結(jié)果填空的題，你只需要算出結(jié)果后提交即可。本題的結(jié)果為一個整數(shù)，在提交答案時只填寫這個整數(shù)，填寫多余的內(nèi)容將無法得分。
代碼：
import java.awt.*;
/**
* @author yx
* @date 2023-04-08 9:13
*/
public class t2 {
public static void main(String[] args) {
int ans=0;
int i=0;
while (true){
i++;
if(isCheck(i)){
ans++;
System.out.println(i+"為第"+ans+"個");
}
if(ans==2023){
break;
}
}
System.out.println("答案是："+i);
}
static boolean isCheck(int n){
String temp1=Integer.toString(n,2);
String temp2=Integer.toString(n,8);
String temp3=n+"";
String temp4=Integer.toString(n,16);
int temp_1=0;
int temp_2=0;
int temp_3=0;
int temp_4=0;
for (int i = 0; i < temp1.length(); i++) {
temp_1+=Integer.parseInt(temp1.substring(i,i+1));
}
if(n%temp_1!=0){
return false;
}
for (int i = 0; i < temp2.length() ;i++) {
temp_2+=Integer.parseInt(temp2.substring(i,i+1));
}
if(n%temp_2!=0){
return false;
}
for (int i = 0; i < temp3.length(); i++) {
temp_3+=Integer.parseInt(temp3.substring(i,i+1));
}
if(n%temp_3!=0){
return false;
}
for (int i = 0; i < temp4.length(); i++) {
if((temp4.substring(i,i+1)).toCharArray()[0]>='a'){
temp_4 += (temp4.substring(i,i+1)).toCharArray()[0]-'a'+10;
}else {
temp_4 += Integer.parseInt(temp4.substring(i, i + 1));
}
}
if(n%temp_4!=0){
return false;
}
return true;
}
}
題目分析：
答案是：215040
- 直接把數(shù)先進制轉(zhuǎn)換，然后求數(shù)位和，判讀能否整除數(shù)位和就好了
- 這題本質(zhì)考一個進制轉(zhuǎn)換，如果會用Java的API就很簡單,前兩天我在算法組會分享的時候剛好講過，還寫了題解，還上了熱榜，哈哈哈，下面鏈接的第五題
藍橋杯最后一戰(zhàn)_小羊不會飛的博客-CSDN博客分巧克力_二分題目描述輸入格式輸出格式輸入輸出樣例說明/提示代碼：巧克力 - 優(yōu)先隊列題目描述輸入格式輸出格式輸入輸出樣例說明/提示代碼：思路分析：秘密行動_dp藍橋杯算法提高-秘密行動題目描述輸入格式輸出格式樣例輸入樣例輸出代碼：思路分析：合并果子_優(yōu)先隊列題目描述輸入格式輸出格式輸入輸出樣例說明/提示代碼：思路分析：回文平方數(shù)_進制轉(zhuǎn)換API題目描述輸入格式輸出格式https://blog.csdn.net/m0_55858611/article/details/129960460?spm=1001.2014.3001.5501
試題 D: 矩形總面積
【問題描述】平面上有個兩個矩形 R 1 和 R 2 ，它們各邊都與坐標(biāo)軸平行。設(shè) ( x 1 , y 1 ) 和( x 2 , y 2 ) 依次是 R 1 的左下角和右上角坐標(biāo)， ( x 3 , y 3 ) 和 ( x 4 , y 4 ) 依次是 R 2 的左下角和右上角坐標(biāo)，請你計算 R 1 和 R 2 的總面積是多少？注意：如果 R 1 和 R 2 有重疊區(qū)域，重疊區(qū)域的面積只計算一次。【輸入格式】輸入只有一行，包含 8 個整數(shù)，依次是： x 1 ， y 1 ， x 2 ， y 2 ， x 3 ， y 3 ， x 4 和 y 4 。【輸出格式】一個整數(shù)，代表答案。【樣例輸入】2 1 7 4 5 3 8 6【樣例輸出】22【樣例說明】樣例中的兩個矩形如圖所示：
【評測用例規(guī)模與約定】對于 20 % 的數(shù)據(jù)， R 1 和 R 2 沒有重疊區(qū)域。對于 20 % 的數(shù)據(jù)，其中一個矩形完全在另一個矩形內(nèi)部。對于 50 % 的數(shù)據(jù)，所有坐標(biāo)的取值范圍是 [0 , 10 ^3 ] 。對于 100 % 的數(shù)據(jù)，所有坐標(biāo)的取值范圍是 [0 , 10^ 5 ] 。
代碼：
import java.io.*;
/**
* @author yx
* @date 2023-04-08 13:57
*/
public class D {
static PrintWriter out =new PrintWriter(System.out);
static BufferedReader ins=new BufferedReader(new InputStreamReader(System.in));
static StreamTokenizer in=new StreamTokenizer(ins);
public static void main(String[] args) throws IOException {
String[] sp=ins.readLine().split(" ");
int x1=Integer.parseInt(sp[0]);
int y1=Integer.parseInt(sp[1]);
int x2=Integer.parseInt(sp[2]);
int y2=Integer.parseInt(sp[3]);
int x3=Integer.parseInt(sp[4]);
int y3=Integer.parseInt(sp[5]);
int x4=Integer.parseInt(sp[6]);
int y4=Integer.parseInt(sp[7]);
long ans=0;
int max_X=Math.max(Math.max(x1,x2),Math.max(x3,x4));
int max_Y=Math.max(Math.max(y1,y2),Math.max(y3,y4));
int max=Math.max(max_X,max_Y);
int[][] Map=new int[max+1][max+1];
for (int i = y1; i <= y2-1 ; i++) {
for (int j = x1; j <= x2-1 ; j++) {
Map[i][j]+=1;
}
}
for (int i = y3; i <= y4-1 ; i++) {
for (int j = x3; j <= x4-1 ; j++) {
Map[i][j]+=1;
}
}
for (int i = 0; i <= max_X ; i++) {
for (int j = 0; j <= max_Y ; j++) {
// System.out.print(Map[j][i]+" ");
if(Map[j][i]>=1){
ans++;
}
}
// System.out.println();
}
System.out.println(ans);
}
}
題目分析：
- 這題就是直接暴力模擬（比賽的時候看了一眼題目就直接跳過了，哭死），賽后十分鐘解決
- 先定義一個int[][]Map，然后遍歷兩塊矩陣，把它們的覆蓋的區(qū)域全部+1，屬于矩陣區(qū)域但是不重合的地方Map值為1,重合的地方加了兩次其Map值會變成2，不屬于矩陣區(qū)間的范圍當(dāng)然為0
- 最后遍歷二維數(shù)組Map，統(tǒng)計Map值>=1的個數(shù)就是答案
?文章來源地址http://www.zghlxwxcb.cn/news/detail-410896.html
試題 G: 買二贈一
【問題描述】某商場有 N 件商品，其中第 i 件的價格是 A i ?，F(xiàn)在該商場正在進行 “ 買二贈一 ” 的優(yōu)惠活動，具體規(guī)則是：每購買 2 件商品，假設(shè)其中較便宜的價格是 P （如果兩件商品價格一樣，則 P 等于其中一件商品的價格），就可以從剩余商品中任選一件價格不超過 P2的商品，免費獲得這一件商品?？梢酝ㄟ^反復(fù)購買 2 件商品來獲得多件免費商品，但是每件商品只能被購買或免費獲得一次。小明想知道如果要拿下所有商品（包含購買和免費獲得），至少要花費多少錢？【輸入格式】第一行包含一個整數(shù) N 。第二行包含 N 個整數(shù)，代表 A 1 , A 2 , A 3 , . . . ， A N 。【輸出格式】輸出一個整數(shù)，代表答案。【樣例輸入】71 4 2 8 5 7 1【樣例輸出】25試題 G: 買二贈一13 第十四屆藍橋杯大賽軟件賽省賽 Java 大學(xué) B 組【樣例說明】小明可以先購買價格 4 和 8 的商品，免費獲得一件價格為 1 的商品；再后買價格為 5 和 7 的商品，免費獲得價格為 2 的商品；最后單獨購買剩下的一件價格為 1 的商品。總計花費 4 + 8 + 5 + 7 + 1 = 25 。不存在花費更低的方案。【評測用例規(guī)模與約定】對于 30 % 的數(shù)據(jù)， 1 ≤ N ≤ 20 。對于 100 % 的數(shù)據(jù)， 1 ≤ N ≤ 5 × 10 5 ， 1 ≤ A i ≤ 10 9 。
代碼：
import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
/**
* @author yx
* @date 2023-04-08 11:31
*/
public class G3 {
static PrintWriter out = new PrintWriter(System.out);
static BufferedReader ins = new BufferedReader(new InputStreamReader(System.in));
static StreamTokenizer in = new StreamTokenizer(ins);
public static void main(String[] args) throws IOException {
String s = ins.readLine();
int N = Integer.parseInt(s);
String[] sp = ins.readLine().split(" ");
ArrayList<Integer> list = new ArrayList<>();
long ans = 0;
for (int i = 0; i < N; i++) {
list.add(Integer.parseInt(sp[i]));
}
Collections.sort(list);
for (int i = 0; list.size()>0 ; i++) {
int a1 = 0;
int a2 = 0;
a1 = list.get(list.size() - 1);
list.remove(list.size() - 1);
if(list.size() - 1>=0) {
a2 = list.get(list.size() - 1);
list.remove(list.size() - 1);
int mid = a2 / 2;
int length=list.size();
for (int j = length-1; j >= 0; j--) {
if (list.get(j) <= mid) {
list.remove(j);
break;
}
}
}
ans += (a1 + a2);
}
out.println(ans);
out.flush();
}
}
題目分析：
用隊列的思想，不過我用的是ArrayList實現(xiàn)
- 首先用鏈表接收數(shù)據(jù)，對其進行排序，從大的開始買，才能讓P/2盡可能大，然后才能讓自己收益盡可能大
- 從最大的元素的開始遍歷，取最大的兩個元素A1、A2（A1>A2）計入總花費，然后把這兩個元素出隊，找隊列中小于等于A2/2的最大元素，它可以白嫖，然后把它出隊
- 找A2/2元素可以用二分優(yōu)化，不過我當(dāng)時神經(jīng)有點緊繃，二分報錯，所以直接從A2開始往后遍歷了，復(fù)雜度會高一點
試題 H: 合并石子
【問題描述】在桌面從左至右橫向擺放著 N 堆石子。每一堆石子都有著相同的顏色，顏色可能是顏色 0 ，顏色 1 或者顏色 2 中的其中一種。現(xiàn)在要對石子進行合并，規(guī)定每次只能選擇位置相鄰并且顏色相同的兩堆石子進行合并。合并后新堆的相對位置保持不變，新堆的石子數(shù)目為所選擇的兩堆石子數(shù)目之和，并且新堆石子的顏色也會發(fā)生循環(huán)式的變化。具體來說：兩堆顏色 0 的石子合并后的石子堆為顏色 1 ，兩堆顏色 1 的石子合并后的石子堆為顏色 2 ，兩堆顏色 2 的石子合并后的石子堆為顏色 0 。本次合并的花費為所選擇的兩堆石子的數(shù)目之和。給出 N 堆石子以及他們的初始顏色，請問最少可以將它們合并為多少堆石子？如果有多種答案，選擇其中合并總花費最小的一種，合并總花費指的是在所有的合并操作中產(chǎn)生的合并花費的總和。【輸入格式】第一行一個正整數(shù) N 表示石子堆數(shù)。第二行包含 N 個用空格分隔的正整數(shù)，表示從左至右每一堆石子的數(shù)目。第三行包含 N 個值為 0 或 1 或 2 的整數(shù)表示每堆石頭的顏色。【輸出格式】一行包含兩個整數(shù)，用空格分隔。其中第一個整數(shù)表示合并后數(shù)目最少的石頭堆數(shù)，第二個整數(shù)表示對應(yīng)的最小花費。【樣例輸入】55 10 1 8 61 1 0 2 2試題 H: 合并石子15 第十四屆藍橋杯大賽軟件賽省賽 Java 大學(xué) B 組【樣例輸出】2 44【樣例說明】
上圖顯示了兩種不同的合并方式。其中節(jié)點中標(biāo)明了每一堆的石子數(shù)目，在方括號中標(biāo)注了當(dāng)前堆石子的顏色屬性。左圖的這種合并方式最終剩下了兩堆石子，所產(chǎn)生的合并總花費為 15 + 14 + 15 = 44 ；右圖的這種合并方式最終也剩下了兩堆石子，但產(chǎn)生的合并總花費為 14 + 15 + 25 = 54 。綜上所述，我們選擇合并花費為 44 的這種方式作為答案。【評測用例規(guī)模與約定】對于 30 % 的評測用例， 1 ≤ N ≤ 10 。對于 50 % 的評測用例， 1 ≤ N ≤ 50 。對于 100 % 的評測用例， 1 ≤ N ≤ 300 , 1 ≤ 每堆石子的數(shù)目 ≤ 1000 。
代碼：
import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
/**
* @author yx
* @date 2023-04-08 12:04
*/
public class H1 {
static class Node implements Comparable<Node>{
int count;
int color;
Node(int count, int color) {
this.count = count;
this.color = color;
}
@Override
public int compareTo(Node o) {
if(this.color==o.color){
return this.count-o.count;
}else {
return 0;
}
}
}
static PrintWriter out = new PrintWriter(System.out);
static BufferedReader ins = new BufferedReader(new InputStreamReader(System.in));
static StreamTokenizer in = new StreamTokenizer(ins);
public static void main(String[] args) throws IOException {
String s = ins.readLine();
int n = Integer.parseInt(s);
String[] strings1 = ins.readLine().split(" ");
String[] strings2 = ins.readLine().split(" ");
Node[] nodes = new Node[n];
int count = 0;
int color = 0;
long ans=0;
ArrayList<Node>list=new ArrayList<>();
for (int i = 0; i < n; i++) {
count = Integer.parseInt(strings1[i]);
color = Integer.parseInt(strings2[i]);
Node node = new Node(count, color);
list.add(node);
}
Collections.sort(list);
// for (int i = 0; i < n; i++) {
// System.out.println(list.get(i).count);
// }
// System.out.println(list.size());
int length=list.size();
for (int j = 0; j < length; j++) {
for (int i = 1; i < list.size(); i++) {
if (list.get(i).color == list.get(i - 1).color) {
Node node1 = list.get(i);
Node node2 = list.get(i - 1);
Node node3 = new Node(0, 0);
if (node1.color == 0) {
node3 = new Node(node1.count + node2.count, 1);
} else if (node1.color == 1) {
node3 = new Node(node1.count + node2.count, 2);
} else {
node3 = new Node(node1.count + node2.count, 0);
}
list.get(i-1).count = node3.count;
list.get(i-1).color = node3.color;
ans += node3.count;
list.remove(i);
// i--;
}
}
}
out.println(list.size()+" "+ans);
out.flush();
}
}
題目思路：
- 分堆問題，前兩天剛做過，簡單的分堆問題可以用優(yōu)先隊列，前天寫的題解第四題合并果子但是很顯然這題是加強版分堆問題，具體體現(xiàn)如下：
- 只有同一類的堆才能合并
- 堆合并之后會進化(堆號為0合并后--->堆號變?yōu)?........)
藍橋杯最后一戰(zhàn)_小羊不會飛的博客-CSDN博客分巧克力_二分題目描述輸入格式輸出格式輸入輸出樣例說明/提示代碼：巧克力 - 優(yōu)先隊列題目描述輸入格式輸出格式輸入輸出樣例說明/提示代碼：思路分析：秘密行動_dp藍橋杯算法提高-秘密行動題目描述輸入格式輸出格式樣例輸入樣例輸出代碼：思路分析：合并果子_優(yōu)先隊列題目描述輸入格式輸出格式輸入輸出樣例說明/提示代碼：思路分析：回文平方數(shù)_進制轉(zhuǎn)換API題目描述輸入格式輸出格式https://blog.csdn.net/m0_55858611/article/details/129960460?spm=1001.2014.3001.5501
- 這題我用局部優(yōu)先隊列的思想，用ArrayList實現(xiàn)，自定義一個Node，然后重寫排序，局部堆號相同的按堆數(shù)count遞增排序（count小的先合，并保證count數(shù)大的堆重復(fù)合并次數(shù)最少）
- 從頭節(jié)點開始往下遍歷，判斷下一個堆是否能合并，如果能合并，更新當(dāng)前節(jié)點，刪除下一個節(jié)點,ans+=當(dāng)前節(jié)點的count+下一個節(jié)點的count
- 最后list的節(jié)點個數(shù)就是最小堆數(shù)
說在最后
趁著剛比完賽，思路還是比價清晰的，終于寫完了題解，相比去年我感覺自己面對算法變得更加從容了一些(雖然還是算法小菜雞)，這段時間因為要備戰(zhàn)考研，所以每天也就只能在上課的時候練算法題，考研之余寫寫算法有時會放松心情有時會增加焦慮，不管怎樣，這一個月都堅持下來了，接下來就是安心備戰(zhàn)考研啦，可能會很長一段時間不更文，各位uu盡情諒解??
最后希望正在看這篇文章的uu，藍橋都能取得好成績！?。?/p>
藍橋杯，咱們有緣江湖再見呀！
文章來源：http://www.zghlxwxcb.cn/news/detail-410896.html
?
到了這里，關(guān)于第十四屆藍橋杯大賽軟件賽省賽JavaB組解析的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
