柚子快報邀請碼778899分享：算法 數(shù)據(jù)結(jié)構(gòu) 藍(lán)橋杯最后一戰(zhàn)

http://yzkb.51969.com/

目錄

分巧克力_二分

題目描述

輸入格式

輸出格式

輸入輸出樣例

說明/提示

代碼：

巧克力 - 優(yōu)先隊列

題目描述

輸入格式

輸出格式

輸入輸出樣例

說明/提示

代碼：

思路分析：

秘密行動_dp

藍(lán)橋杯算法提高-秘密行動

題目描述

輸入格式

輸出格式

樣例輸入

樣例輸出

代碼：

思路分析：

合并果子_優(yōu)先隊列

題目描述

輸入格式

輸出格式

輸入輸出樣例

說明/提示

代碼：

思路分析：

回文平方數(shù)_進(jìn)制轉(zhuǎn)換API

題目描述

輸入格式

輸出格式

輸入輸出樣例

說明/提示

代碼：

說在最后

分巧克力_二分

題目描述

兒童節(jié)那天有 KK 位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友們。

小明一共有 NN 塊巧克力，其中第 ii 塊是 Hi×WiHi?×Wi? 的方格組成的長方形。

為了公平起見，小明需要從這 NN 塊巧克力中切出 KK 塊巧克力分給小朋友們。切出的巧克力需要滿足：

形狀是正方形，邊長是整數(shù)。 大小相同。

例如一塊 6×56×5 的巧克力可以切出 66 塊 2×22×2 的巧克力或者 22 塊 3×33×3 的巧克力。

當(dāng)然小朋友們都希望得到的巧克力盡可能大，你能幫小 HiHi? 計算出最大的邊長是多少么？

輸入格式

第一行包含兩個整數(shù) NN 和 KK。(1≤N,K≤105)(1≤N,K≤105)。

以下 NN 行每行包含兩個整數(shù) HiHi? 和 WiWi?。(1≤Hi,Wi≤105)(1≤Hi?,Wi?≤105)。

輸入保證每位小朋友至少能獲得一塊 1×11×1 的巧克力。

輸出格式

輸出切出的正方形巧克力最大可能的邊長。

輸入輸出樣例

輸入 #1

2 10

6 5

5 6

輸出 #1

2

說明/提示

藍(lán)橋杯 2022 省賽 A 組 I 題。

代碼：

package 第十四屆藍(lán)橋杯三月真題刷題訓(xùn)練.自由刷題;

import java.io.*;

/**

* @author yx

* @date 2023-04-03 18:11

*/

public class 分巧克力_二分 {

static PrintWriter out = new PrintWriter(System.out);

static BufferedReader ins = new BufferedReader(new InputStreamReader(System.in));

static StreamTokenizer in = new StreamTokenizer(ins);

static int[] H;

static int[] W;

static int K;

static int N;

/**

* 輸入

* 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;讀取文件終止的語句

**/

public static void main(String[] args) throws IOException {

String[] sp = ins.readLine().split(" ");

N = Integer.parseInt(sp[0]);

K = Integer.parseInt(sp[1]);

H = new int[N];

W = new int[N];

for (int i = 0; i < N; i++) {

String[] sp1 = ins.readLine().split(" ");

H[i] = Integer.parseInt(sp1[0]);

W[i] = Integer.parseInt(sp1[1]);

}

int l = 1;

int r = 100001;

int ans = 0;

while (l <= r) {

//二分

int mid = (l + r) / 2;

if (check(mid)) {

ans = mid;

l = mid + 1;

} else {

r = mid - 1;

}

}

System.out.print(ans);

}

static boolean check(int n) {

int temp=0;

for (int i = 0; i < N; i++) {

temp+=(H[i]/n)*(W[i]/n);

}

if(temp>=K){

return true;

}else {

return false;

}

}

}

巧克力 - 優(yōu)先隊列

題目描述

小藍(lán)很喜歡吃巧克力，他每天都要吃一塊巧克力。

一天小藍(lán)到超市想買一些巧克力。超市的貨架上有很多種巧克力，每種巧克力有自己的價格、數(shù)量和剩余的保質(zhì)期天數(shù)，小藍(lán)只吃沒過保質(zhì)期的巧克力，請問小藍(lán)最少花多少錢能買到讓自己吃 xx 天的巧克力。

輸入格式

輸入的第一行包含兩個整數(shù) xx，nn，分別表示需要吃巧克力的天數(shù)和巧克力的種類數(shù)。

接下來 nn 行描述貨架上的巧克力，其中第 ii 行包含三個整數(shù) aiai?，bibi?，cici?，表示第 ii 種巧克力的單價為 aiai?，保質(zhì)期還剩 bibi? 天（從現(xiàn)在開始的 bibi? 天可以吃），數(shù)量為 cici?。

輸出格式

輸出一個整數(shù)表示小藍(lán)的最小花費(fèi)。如果不存在讓小藍(lán)吃 xx 天的購買方案，輸出 ?1?1。

輸入輸出樣例

輸入 #1

10 3

1 6 5

2 7 3

3 10 10

輸出 #1

18

說明/提示

【樣例說明】

一種最佳的方案是第 11 種買 55 塊，第 22 種買 22 塊，第 33 種買 33 塊。前 55 天吃第 11 種，第 66、77 天吃第 22 種，第 88 至 1010 天吃第 33 種。

【評測用例規(guī)模與約定】

對于 30%30% 的評測用例，n,x≤1000n,x≤1000。

對于所有評測用例，1≤n,x≤1051≤n,x≤105，1≤ai,bi,ci≤1091≤ai?,bi?,ci?≤109。

藍(lán)橋杯 2021 國賽 C 組 I 題。

代碼：

package 第十四屆藍(lán)橋杯三月真題刷題訓(xùn)練.自由刷題;

import java.io.*;

import java.util.*;

/**

* @author yx

* @date 2023-04-03 18:28

*/

public class 巧克力_優(yōu)先隊列 {

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;讀取文件終止的語句

**/

static class Node implements Comparable {

int id;

int price_a;

int day_b;

int number_c;

Node(int id, int price_a, int day_b, int number_c) {

this.id = id;

this.price_a = price_a;

this.day_b = day_b;

this.number_c = number_c;

}

//按保質(zhì)期從高到低進(jìn)行排序

@Override

public int compareTo(Node o) {

if (o.day_b > this.day_b) {

return 1;

} else {

return -1;

}

}

}

static class Node1 {

int id;

int price_a;

int day_b;

int number_c;

Node1(int id, int price_a, int day_b, int number_c) {

this.id = id;

this.price_a = price_a;

this.day_b = day_b;

this.number_c = number_c;

}

}

public static void main(String[] args) throws IOException {

String[] sp = ins.readLine().split(" ");

int x = Integer.parseInt(sp[0]);

int n = Integer.parseInt(sp[1]);

Node[] nodes = new Node[n];

int[] nums = new int[n];

long ans = 0;

for (int i = 0; i < n; i++) {

String[] sp1 = ins.readLine().split(" ");

nodes[i] = new Node(i, Integer.parseInt(sp1[0]), Integer.parseInt(sp1[1]), Integer.parseInt(sp1[2]));

}

//按保質(zhì)期從高到低進(jìn)行排序

Arrays.sort(nodes);

int j = 0;

// Prio priority_queue = new LinkedList<>();

PriorityQueuepriority_queue=new PriorityQueue<>(

new Comparator() {

@Override

public int compare(Node1 o1, Node1 o2) {

return o1.price_a-o2.price_a;

}

}

);

for (int i = x; i >= 1; i--) {

while (j < n && nodes[j].day_b >= i) {

priority_queue.offer(new Node1(nodes[j].id,nodes[j].price_a,nodes[j].day_b,nodes[j].number_c));

j++;

}

//如果出現(xiàn)空隊列表示沒有選擇了

if (priority_queue.size() == 0) {

out.println(ans);

out.println(-1);

out.flush();

return;

}

Node1 node = priority_queue.peek();

//表示當(dāng)前id的物品個數(shù)+1

nums[node.id]++;

// System.out.println("id："+node.id+"價格："+node.price_a+"購買數(shù)量："+nums[node.id]);

//加上當(dāng)前物品的價格

ans += node.price_a;

//表示當(dāng)前物品全部選完了

if (node.number_c == nums[node.id]) {

// System.out.println("物品id:"+node.id+"出隊");

//當(dāng)前種類的物品已經(jīng)全部選完了，所以當(dāng)前物品出隊

priority_queue.poll();

}

}

out.println(ans);

out.flush();

}

}

思路分析：

秘密行動_dp

題目 2250:

藍(lán)橋杯算法提高-秘密行動

時間限制: 1s 內(nèi)存限制: 128MB 提交: 255 解決: 122

題目描述

小D接到一項任務(wù)，要求他爬到一座n層大廈的頂端與神秘人物會面。這座大廈有一個神奇的特點(diǎn)，每層的高度都不一樣，同時，小D也擁有一項特殊能力，可以一次向上跳躍一層或兩層，但是這項能力無法連續(xù)使用。已知向上1高度消耗的時間為1，跳躍不消耗時間。由于事態(tài)緊急，小D想知道他最少需要多少時間到達(dá)頂層。

輸入格式

第一行包含一個整數(shù)n，代表樓的高度。 接下來n行每行一個整數(shù)ai，代表i層的樓層高度（ai <= 100）。

輸出格式

輸出1行，包含一個整數(shù)，表示所需的最短時間。

樣例輸入

5

3

5

1

8

4

樣例輸出

1

代碼：

package 第十四屆藍(lán)橋杯三月真題刷題訓(xùn)練.自由刷題;

import java.io.*;

/**

* @author yx

* @date 2023-04-04 16:56

*/

public class 秘密行動_dp {

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;讀取文件終止的語句

**/

public static void main(String[] args) throws IOException {

in.nextToken();

int n=(int) in.nval;

int[] nums=new int[n+1];

for (int i = 1; i <= n; i++) {

in.nextToken();

nums[i]=(int) in.nval;

}

//n表示需要走n層

//2表示兩種下選擇可以一步一步爬也可以直接跳躍

//其中下標(biāo)[][0]表示爬,[][1]表示跳躍

int[][] dp=new int[n+1][2];

dp[1][0]=nums[1];//直接賦初值

for (int i = 2; i <= n; i++) {

//從上一層爬上來,上一層可以是爬的也可以是跳躍的

dp[i][0]=Math.min(dp[i-1][0],dp[i-1][1])+nums[i];

//直接跳躍，但是只能從爬的開始跳躍,并且每次可以跳兩層或者一層，因為不能連續(xù)跳躍

dp[i][1]=Math.min(dp[i-1][0],dp[i-2][0]);

}

out.println(Math.min(dp[n][1],dp[n][0]));

out.flush();

}

}

思路分析：

合并果子_優(yōu)先隊列

題目描述

在一個果園里，多多已經(jīng)將所有的果子打了下來，而且按果子的不同種類分成了不同的堆。多多決定把所有的果子合成一堆。

每一次合并，多多可以把兩堆果子合并到一起，消耗的體力等于兩堆果子的重量之和?？梢钥闯觯械墓咏?jīng)過 n?1n?1 次合并之后， 就只剩下一堆了。多多在合并果子時總共消耗的體力等于每次合并所耗體力之和。

因為還要花大力氣把這些果子搬回家，所以多多在合并果子時要盡可能地節(jié)省體力。假定每個果子重量都為 11 ，并且已知果子的種類 數(shù)和每種果子的數(shù)目，你的任務(wù)是設(shè)計出合并的次序方案，使多多耗費(fèi)的體力最少，并輸出這個最小的體力耗費(fèi)值。

例如有 33 種果子，數(shù)目依次為 11 ， 22 ， 99 ?？梢韵葘?11 、 22 堆合并，新堆數(shù)目為 33 ，耗費(fèi)體力為 33 。接著，將新堆與原先的第三堆合并，又得到新的堆，數(shù)目為 1212 ，耗費(fèi)體力為 1212 。所以多多總共耗費(fèi)體力 =3+12=15=3+12=15 。可以證明 1515 為最小的體力耗費(fèi)值。

輸入格式

共兩行。 第一行是一個整數(shù) n(1≤n≤10000)n(1≤n≤10000) ，表示果子的種類數(shù)。

第二行包含 nn 個整數(shù)，用空格分隔，第 ii 個整數(shù) ai(1≤ai≤20000)ai?(1≤ai?≤20000) 是第 ii 種果子的數(shù)目。

輸出格式

一個整數(shù)，也就是最小的體力耗費(fèi)值。輸入數(shù)據(jù)保證這個值小于 231231 。

輸入輸出樣例

輸入 #1

3

1 2 9

輸出 #1

15

說明/提示

對于 30%30% 的數(shù)據(jù)，保證有 n≤1000n≤1000：

對于 50%50% 的數(shù)據(jù)，保證有 n≤5000n≤5000；

對于全部的數(shù)據(jù)，保證有 n≤10000n≤10000。

代碼：

package 第十四屆藍(lán)橋杯三月真題刷題訓(xùn)練.自由刷題;

import java.io.*;

import java.util.PriorityQueue;

/**

* @author yx

* @date 2023-04-04 17:59

*/

public class 合并果子_優(yōu)先隊列 {

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;讀取文件終止的語句

**/

public static void main(String[] args) throws IOException {

in.nextToken();

int n=(int) in.nval;

//優(yōu)先隊列會自動排序

PriorityQueuequeue=new PriorityQueue<>();

for (int i = 0; i < n; i++) {

in.nextToken();

queue.offer((int)in.nval);

}

int a=0;

int b=0;

int ans=0;

while (queue.size()!=1){

if(!queue.isEmpty()){

a=queue.poll();

}

if(!queue.isEmpty()){

b=queue.poll();

}

queue.offer(a+b);

ans+=(a+b);

}

out.println(ans);

out.flush();

}

}

思路分析：

回文平方數(shù)_進(jìn)制轉(zhuǎn)換API

題目描述

回文數(shù)是指從左向右念和從右向左念都一樣的數(shù)。如 1232112321 就是一個典型的回文數(shù)。

給定一個用十進(jìn)制表示的正整數(shù) BB，輸出所有 [1,300][1,300] 中，它的平方用 BB 進(jìn)制表示時是回文數(shù)的數(shù)。

輸入格式

共一行，一個單獨(dú)的正整數(shù) BB。

輸出格式

每行兩個 BB 進(jìn)制的符合要求的數(shù)字，第二個數(shù)是第一個數(shù)的平方，且第二個數(shù)是回文數(shù)。

注意大于 99 的數(shù)，用字母表示。如用 A 表示 1010，B 表示 1111，用第 nn 個大寫字母表示 n+9n+9。

輸入輸出樣例

輸入 #1

10

輸出 #1

1 1

2 4

3 9

11 121

22 484

26 676

101 10201

111 12321

121 14641

202 40804

212 44944

264 69696

說明/提示

【數(shù)據(jù)范圍】 對于 100%100% 的數(shù)據(jù)，2≤B≤202≤B≤20

題目翻譯來自NOCOW。

USACO Training Section 1.2

代碼：

package 第十四屆藍(lán)橋杯三月真題刷題訓(xùn)練.自由刷題;

import java.io.*;

import java.util.Locale;

/**

* @author yx

* @date 2023-04-04 16:33

*/

public class P1206回文平方數(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;讀取文件終止的語句

**/

public static void main(String[] args) throws IOException {

// 1、把十進(jìn)制A+B的結(jié)果轉(zhuǎn)換為D進(jìn)制

// Integer.toString(A+B,D)

// 2、把D進(jìn)制的字符串”s“轉(zhuǎn)成十進(jìn)制

// Integer.parseInt("s",D)

// int anInt1 = Integer.parseInt("1000100", 2);//68

in.nextToken();

int number=(int) in.nval;

for (int i = 1; i <= 300; i++) {

if(isHuiWen(Integer.toString(i*i,number))){

out.println(Integer.toString(i,number).toUpperCase()+" "+Integer.toString(i*i,number).toUpperCase(Locale.ROOT));

}

}

out.flush();

}

static boolean isHuiWen(String s){

char[] arr=s.toCharArray();

int length=arr.length;

for (int i = 0; i < length/2; i++) {

if(arr[i]!=arr[length-i-1]){

return false;

}

}

return true;

}

}

說在最后

祝大家都能取得好成績?。?！

也希望自己能取得一個滿意的成績?。。?/p>

?

柚子快報邀請碼778899分享：算法 數(shù)據(jù)結(jié)構(gòu) 藍(lán)橋杯最后一戰(zhàn)

http://yzkb.51969.com/

好文鏈接