目錄
A、階乘求和
?Ⅰ、題目解讀
Ⅱ、代碼?
B、幸運數(shù)字
?Ⅰ、題目解讀
?Ⅱ、代碼
C: 數(shù)組分割（時間限制: 1.0s 內(nèi)存限制: 512.0MB）
?Ⅰ、解題思路
?Ⅱ、代碼
?D、矩形總面積（時間限制: 1.0s 內(nèi)存限制: 512.0MB）
?Ⅰ、題目解讀
Ⅱ、代碼?
?E、蝸牛（時間限制: 1.0s 內(nèi)存限制: 512.0MB）
?Ⅰ、題目解讀
?Ⅱ、代碼
?F、合并區(qū)域 （時間限制: 2.0s 內(nèi)存限制: 512.0MB）
?Ⅰ、題目解讀
?Ⅱ、代碼
?G、買二贈一（時間限制: 1.0s 內(nèi)存限制: 512.0MB）
?Ⅰ、題目解讀
?Ⅱ、代碼1(復(fù)雜度過大，超時)
代碼2（正確答案）
?H、合并石子（時間限制: 1.0s 內(nèi)存限制: 512.0MB）
?Ⅰ、題目解讀
Ⅱ、代碼
?I、最大開支（時間限制: 1.0s 內(nèi)存限制: 512.0MB ）
?Ⅰ、題目解讀
?J、魔法陣（時間限制: 1.0s 內(nèi)存限制: 512.0MB ）
?總結(jié)
2023年第十四屆藍橋杯JavaB組省賽文件已上傳到csdn，可自行下載
藍橋杯題目：2023年第十四屆藍橋杯大賽軟件類省賽Java大學(xué)B組真題 - 題庫 - C語言網(wǎng) (dotcpp.com)
詳細完整題解在這篇博客：
2023年第十四屆藍橋杯省賽JavaB組個人題解(AK)_迷你濱的博客-CSDN博客
A、階乘求和
【問題描述】令 S = 1! + 2! + 3! + ... + 202320232023! ，求 S 的末尾 9 位數(shù)字。提示：答案首位不為 0 。
?Ⅰ、題目解讀
?一看到三個2023的巨大數(shù)字，我想大家應(yīng)該都人都麻了。但是我想說這是官方的騙術(shù)，因為題目說要求末尾的9位數(shù)，其實我想告訴大家當(dāng)加到40多的階乘時，這個階乘和后面的9位數(shù)就不會發(fā)生改變了。
Ⅱ、代碼?
public class Main {
public static void main(String[] args) {
long start=1;
String s="202320232023";
long end= Long.parseLong(s);
long sum=0;
long cj=1;
while (start<=end){
cj*=start;
cj%=1000000000;
sum+=cj;
sum%=1000000000;
start++;
if (start>40)
System.out.println(sum);
}
System.out.println(sum);
}
}
?看運行
20940313 420940313 420940313 420940313 420940313 420940313 420940313 ...
這是因為40的階乘之后后面?9位數(shù)都是0，所以階乘之和末尾9位數(shù)不會再發(fā)生改變！
B、幸運數(shù)字
【問題描述】哈沙德數(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 。小藍認為，如果一個整數(shù)在二進制、八進制、十進制、十六進制下均為 哈沙德數(shù)，那么這個數(shù)字就是幸運數(shù)字，第 1 至第 10 個幸運數(shù)字的十進制表示 為：1 , 2 , 4 , 6 , 8 , 40 , 48 , 72 , 120 , 126 . . . ?，F(xiàn)在他想知道第 2023 個幸運數(shù) 字是多少？你只需要告訴小藍這個整數(shù)的十進制表示即可。
?Ⅰ、題目解讀
?這題就是考察大家的進制轉(zhuǎn)換，數(shù)據(jù)量也不大。直接看代碼吧！
?Ⅱ、代碼
public class {
public static void main(String[] args) {
int j=0;
for (int i=1;i<10000000;i++){
if (BaseConversion(i)){
j++;
if (j==2023){
System.out.println(i);//215040
break;
}
}
}
}
public static boolean BaseConversion(int n){
//十進制
int sum=0;
int x=n;
while (x!=0){
sum+=(x%10);
x/=10;
}
if (n%sum!=0)
return false;
//二進制
sum=0;
x=n;
while (x!=0){
sum+=(x%2);
x/=2;
}
if (n%sum!=0)
return false;
//八進制
sum=0;
x=n;
while (x!=0){
sum+=(x%8);
x/=8;
}
if (n%sum!=0)
return false;
//十六進制
int[] arr={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
sum=0;
x=n;
while (x!=0){
sum+=(arr[x%16]);
x/=16;
}
if (n%sum!=0)
return false;
return true;
}
}
C: 數(shù)組分割（時間限制: 1.0s 內(nèi)存限制: 512.0MB）
時間限制 : 1.0s內(nèi)存限制 : 512.0MB本題總分： 10 分
【問題描述】小藍有一個長度為 N 的數(shù)組 A = [ A 0 , A 1 , . . . , A N ? 1 ] ?，F(xiàn)在小藍想要從 A 對應(yīng)的數(shù)組下標(biāo)所構(gòu)成的集合 I = { 0 , 1 , 2 , . . . , N ? 1 } 中找出一個子集 R 1 ，那么 R 1在 I 中的補集為 R 2 。記 S 1 = ∑ r ∈ R 1 A r ， S 2 = ∑ r ∈ R 2 A r，我們要求 S 1 和 S 2 均為 偶數(shù)，請問在這種情況下共有多少種不同的 R 1。當(dāng) R1 或 R 2 為空集時我們將 S 1 或 S 2 視為 0。【輸入格式】第一行一個整數(shù) T ，表示有 T 組數(shù)據(jù)。 接下來輸入 T 組數(shù)據(jù)，每組數(shù)據(jù)包含兩行：第一行一個整數(shù) N ，表示數(shù)組 A 的長度；第二行輸入 N 個整數(shù)從左至右依次為 A 0 , A 1 , . . . , A N ? 1 ，相鄰元素之 間用空格分隔。【輸出格式】對于每組數(shù)據(jù)，輸出一行，包含一個整數(shù)表示答案，答案可能會很大，你需要將答案對 1000000007 進行取模后輸出。【樣例輸入】2 2 6 6 2 1 6【樣例輸出】4
【樣例說明】對于第一組數(shù)據(jù)，答案為 4 。（注意：大括號內(nèi)的數(shù)字表示元素在數(shù)組中的下標(biāo)。）R 1 = { 0 } , R 2 = { 1 } ；此時 S 1 = A 0 = 6 為偶數(shù) , S 2 = A 1 = 6 為偶數(shù)。R 1 = { 1 } , R 2 = { 0 } ；此時 S 1 = A 1 = 6 為偶數(shù) , S 2 = A 0 = 6 為偶數(shù)。R 1 = { 0 , 1 } , R 2 = {} ；此時 S 1 = A 0 + A 1 = 12 為偶數(shù) , S 2 = 0 為偶數(shù)。R 1 = {} , R 2 = { 0 , 1 } ；此時 S 1 = 0 為偶數(shù) , S 2 = A 0 + A 1 = 12 為偶數(shù)。對于第二組數(shù)據(jù)，無論怎么選擇，都不滿足條件，所以答案為 0 。【評測用例規(guī)模與約定】對于 20 % 的評測用例， 1 ≤ N ≤ 10 。對于 40 % 的評測用例， 1 ≤ N ≤ 10 2 。對于 100 % 的評測用例， 1 ≤ T ≤ 10 , 1 ≤ N ≤ 10 3 , 0 ≤ A i ≤ 10 9 。?
?Ⅰ、解題思路
要求分割兩個子集，其中一個可以為空集，且兩個集合為偶數(shù)，所有第一步判斷集合的總和是否為偶數(shù)，如果不為偶數(shù)則直接判定為 0 個否則再進行深度收搜判斷 (暴力超時)
也可以利用奇數(shù)個數(shù)與偶數(shù)個數(shù)的排列組合實現(xiàn)， 將兩個奇數(shù)拼接為一個偶數(shù)，判斷無重復(fù)的奇數(shù)拼接情況，與偶數(shù)個數(shù)相加，遞推排列組合公式 ?(正解)
優(yōu)化排列組合，會發(fā)現(xiàn)是高精度算法 設(shè) x 為偶數(shù)個數(shù)， y 為奇數(shù)個數(shù)ans = pow(x + (y == 0 ? 0 : y - 1)) % mod 算法標(biāo)簽：遞推，找規(guī)律，貪心
注意事項:
?x + (y == 0 ? 0 : y - 1), 奇數(shù)為0情況
?Ⅱ、代碼
//排列組合遞推公式
import java.util.Scanner;
import java.math.BigInteger;
public class Main {
public static final BigInteger MOD = new BigInteger("1000000007");
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int T = scan.nextInt();
while (T-- > 0){
int n = scan.nextInt();
int[] a = new int[n];
long x = 0, y = 0; // x 記錄偶數(shù)， y 記錄奇數(shù)
for(int i = 0; i < n; i++){
a[i] = scan.nextInt() % 2;
if(a[i] == 0){
x++;
}else {
y++;
}
}
if(y % 2 == 1){ // 奇數(shù)個數(shù)為奇，沒有一個條件成立
System.out.println(0);
continue;
}
x = x + (y == 0 ? 0 : y - 1); // 兩個奇數(shù)組合為一個偶數(shù)，排除重復(fù)情況
BigInteger ans = new BigInteger("2");
BigInteger dp = new BigInteger("1");
// C(n,m) = P(n,m) / P(m,m) = n! / m! * (n - m)!
// 轉(zhuǎn)移遞推公式 dp = (dp * (x, x-1, x-2, ... , n) / (1, 2, 3, ... , n))
for(long i = 1, j = x; i < x; i++, j--){ // 排列組合無順序 C
BigInteger u = new BigInteger(String.valueOf(j));
BigInteger v = new BigInteger(String.valueOf(i));
dp = dp.multiply(u).divide(v);
ans = ans.add(dp);
}
System.out.println(ans.mod(MOD));
}
}
}??優(yōu)化高精度
import java.util.Scanner;
import java.math.BigInteger;
public class Main {
public static final BigInteger MOD = new BigInteger("1000000007");
public static final BigInteger TWO = new BigInteger("2");
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int T = scan.nextInt();
while (T-- > 0) {
int n = scan.nextInt();
int x = 0, y = 0; // x 記錄偶數(shù)， y 記錄奇數(shù)
for (int i = 0; i < n; i++) {
int a = scan.nextInt() % 2;
if (a == 0) {
x++;
} else {
y++;
}
}
if (y % 2 == 1) {
System.out.println(0);
}else{
System.out.println(TWO.pow(x + (y == 0 ? 0 : y - 1)).mod(MOD));
}
}
}
}?D、矩形總面積（時間限制: 1.0s 內(nèi)存限制: 512.0MB）
【問題描述】平面上有個兩個矩形 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 , 103 ?] 。對于 100 % 的數(shù)據(jù)，所有坐標(biāo)的取值范圍是 [0 , 10? ?]
?Ⅰ、題目解讀
這題有兩種解法，自己數(shù)組去求，但是可能數(shù)據(jù)量過大會爆棧。第二種就是公式直接求解，這時求兩個矩形相交的面積改怎么求？
矩形相交要使條件成立，即min(x2,x4)-max(x1,x3)>=0 且min(y2,y4)-max(y1,y3)>=0
如果條件成立，則相交矩形面積為：(min(x2,x4)-max(x1,x3))* (min(y2,y4)-max(y1,y3))
Ⅱ、代碼?
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int x1 = sc.nextInt();
int y1 = sc.nextInt();
int x2 = sc.nextInt();
int y2 = sc.nextInt();
int x3 = sc.nextInt();
int y3 = sc.nextInt();
int x4 = sc.nextInt();
int y4 = sc.nextInt();
long area1 = (long) (x2 - x1) * (y2 - y1); // 計算第一個矩形的面積
long area2 = (long) (x4 - x3) * (y4 - y3); // 計算第二個矩形的面積
long overlapArea=0;
long l = Math.min(x2, x4) - Math.max(x1, x3);
long w= Math.min(y2,y4)-Math.max(y1,y3);
if (l >=0&&w >=0){
overlapArea= l * w;
}
long Area = area1 + area2 - overlapArea; // 總面積
System.out.println(Area); // 輸出總面積
}
}
?E、蝸牛（時間限制: 1.0s 內(nèi)存限制: 512.0MB）
【問題描述】這天，一只蝸牛來到了二維坐標(biāo)系的原點。 在 x 軸上長有 n 根竹竿。它們平行于 y 軸，底部縱坐標(biāo)為 0 ，橫坐標(biāo)分別 為 x 1 , x 2 , ..., x n 。竹竿的高度均為無限高，寬度可忽略。蝸牛想要從原點走到第 n 個竹竿的底部也就是坐標(biāo) ( x n , 0) 。它只能在 x 軸上或者竹竿上爬行，在 x 軸上爬行速度為 1 單位每秒；由于受到引力影響，蝸牛在竹竿上向上和向下爬行 的速度分別為 0 . 7 單位每秒和 1 . 3 單位每秒。 為了快速到達目的地，它施展了魔法，在第 i 和 i + 1 根竹竿之間建立了傳 送門（0 < i < n ），如果蝸牛位于第 i 根竹竿的高度為 a i 的位置 ( x i , a i ) ，就可以 瞬間到達第 i + 1 根竹竿的高度為 b i +1 的位置 ( x i +1 , b i +1 )， 請計算蝸牛最少需要多少秒才能到達目的地。【輸入格式】輸入共 1 + n 行，第一行為一個正整數(shù) n ；第二行為 n 個正整數(shù) x 1 , x 2 , . . . , x n ；后面 n ? 1 行，每行兩個正整數(shù) a i , b i +1 。【輸出格式】輸出共一行，一個浮點數(shù)表示答案（ 四舍五入保留兩位小數(shù) ）。【樣例輸入】3 1 10 11 1 1 2 1【樣例輸出】
4.20【樣例說明】蝸牛路線：(0 , 0) → (1 , 0) → (1 , 1) → (10 , 1) → (10 , 0) → (11 , 0) ，花費時間為 1 +1/? 0.7 + 0 + 1/1 .3 + 1 ≈ 4 . 20【評測用例規(guī)模與約定】對于 20 % 的數(shù)據(jù)，保證 n ≤ 15 ；對于 100 % 的數(shù)據(jù)，保證 n ≤ 10? ，a i , b i ≤ 10? ，x i ≤ 10? 。
?Ⅰ、題目解讀
dp[i][j] 表示蝸牛走到第 i 根桿子的最短用時，j 表示狀態(tài)。
j = 0 : 走到桿子底部
j = 1 ：走到桿子的傳送門處
P.S.由于只與前一個桿子狀態(tài)有關(guān)，其實用兩個變量就行，用二維數(shù)組便于理解
時間復(fù)雜度: O(n)
?Ⅱ、代碼
import java.io.*;
import java.util.*;
public class Main{
static int maxn = 200005,n,m;
static long INF = (long)2e18,ans = 0,mod = (int)1e9+7;
static Scanner sc = new Scanner (System.in);
static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
static StreamTokenizer st =new StreamTokenizer(bf);
static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
public static void main(String[]args) throws IOException{
int T = 1;
//T = Integer.parseInt(S());
while(T-->0) solve();
pw.flush();
}
static final int I() throws IOException {
st.nextToken();
return (int)st.nval;
}
static void solve() throws IOException{
n = I();
long x[] = new long [n+1];
for(int i=1;i<=n;i++) x[i] = I();
int []a = new int [n+1];
int []b = new int [n+1];
for(int i=1;i<n;i++) {
a[i] = I();b[i] = I();
}
double dp[][] = new double[n+1][2];
dp[1][0] = x[1]; //底端最小用時
dp[1][1] = x[1] + a[1] / 0.7; //傳送門用時
for(int i=2; i<=n ; i++) {
dp[i][0] = Math.min(dp[i-1][0]+x[i]-x[i-1], dp[i-1][1] + b[i-1]/1.3);
dp[i][1] = Math.min(dp[i][0] + a[i] / 0.7, dp[i-1][1] + ((b[i-1]>a[i])?(b[i-1]-a[i])/1.3: (a[i]-b[i-1])/0.7));
}
pw.printf("%.2f",dp[n][0]);
}
}?F、合并區(qū)域 （時間限制: 2.0s 內(nèi)存限制: 512.0MB）
【問題描述】小藍在玩一款種地游戲?，F(xiàn)在他被分配給了兩塊大小均為 N × N 的正方形 區(qū)域。這兩塊區(qū)域都按照 N × N 的規(guī)格進行了均等劃分，劃分成了若干塊面積 相同的小區(qū)域，其中每塊小區(qū)域要么是巖石，要么就是土壤，在垂直或者水平 方向上相鄰的土壤可以組成一塊土地?，F(xiàn)在小藍想要對這兩塊區(qū)域沿著邊緣進 行合并，他想知道合并以后可以得到的最大的一塊土地的面積是多少（土地的 面積就是土地中土壤小區(qū)域的塊數(shù)）？ 在進行合并時，小區(qū)域之間必須對齊。可以在兩塊方形區(qū)域的任何一條邊 上進行合并，可以對兩塊方形區(qū)域進行 90 度、 180 度、 270 度、 360 度的旋轉(zhuǎn)， 但不可以進行上下或左右翻轉(zhuǎn)，并且兩塊方形區(qū)域不可以發(fā)生重疊。【輸入格式】第一行一個整數(shù) N 表示區(qū)域大小。 接下來 N 行表示第一塊區(qū)域，每行 N 個值為 0 或 1 的整數(shù)，相鄰的整數(shù) 之間用空格進行分隔。值為 0 表示這塊小區(qū)域是巖石，值為 1 表示這塊小區(qū)域 是土壤。 再接下來 N 行表示第二塊區(qū)域，每行 N 個值為 0 或 1 的整數(shù)，相鄰的整 數(shù)之間用空格進行分隔。值為 0 表示這塊小區(qū)域是巖石，值為 1 表示這塊小區(qū) 域是土壤。【輸出格式】一個整數(shù)表示將兩塊區(qū)域合并之后可以產(chǎn)生的最大的土地面積。【樣例輸入】4 0 1 1 0 1 0 1 1 1 0 1 0 1 1 1 0 0 0 1 0 0 1 1 0 1 0 0 0 1 1 1 1【樣例輸出】15【樣例說明】
第一張圖展示了樣例中的兩塊區(qū)域的布局。第二張圖展示了其中一種最佳的合并方式，此時最大的土地面積為 15 。【評測用例規(guī)模與約定】對于 30 % 的數(shù)據(jù)， 1 ≤ N ≤ 5 。對于 60 % 的數(shù)據(jù)， 1 ≤ N ≤ 15 。對于 100 % 的數(shù)據(jù)， 1 ≤ N ≤ 50 。
?Ⅰ、題目解讀
題目會給你兩塊土地，你可以進行兩塊土地的“縫合”，求最大的連續(xù)的土地。最大土地有三種情況①、左右連接成一塊最大的土地
②、單獨一邊中間是最大的土地
?
③、因為另一塊土地的連接而導(dǎo)致原本不連接的土地也連接成新的土地（這種情況是我沒想到的）
我只想到了前面兩種情況，如果要算上第三種情況的話就應(yīng)該直接使用暴力求解（畢竟數(shù)據(jù)量并不是很大），不斷拼接，求最大連續(xù)的土地。我的代碼也只是符合前面兩種情況，有正確代碼還請大佬給出。萬分感謝。
?Ⅱ、代碼
import java.awt.*;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
public class Main {
static class Point{
int x,y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int[][] arr1=new int[n+2][n+2];//第一個矩陣
int[][] arr2=new int[n+2][n+2];//第二個矩陣
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++){
arr1[i][j]=sc.nextInt();
}
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++){
arr2[i][j]=sc.nextInt();
}
int max=0;
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++){
if (arr1[i][j]==1){
length(arr1,i,j);
List<Point> list=new ArrayList<>(set);
for (Point p:list)
arr1[p.x][p.y]=sum;
max=Math.max(max,sum);//防止矩陣里面是最大的
sum=0;
set.clear();
}
}
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++){
if (arr2[i][j]==1){
length(arr2,i,j);
List<Point> list=new ArrayList<>(set);
for (Point p:list)
arr2[p.x][p.y]=sum;
max=Math.max(max,sum);//防止矩陣里面是最大的
sum=0;
set.clear();
}
}
int l=0;
int r=0;
//求四邊的最大值然后拼接
//兩行
for (int i=1;i<=n;i+=(n-1))
for (int j=1;j<=n;j++){
l=Math.max(l,arr1[i][j]);
r=Math.max(r,arr2[i][j]);
}
//兩列
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j+=(n-1)){
l=Math.max(l,arr1[i][j]);
r=Math.max(r,arr2[i][j]);
}
max=Math.max(max,l+r);
System.out.println(max);
}
static int sum=0;
static HashSet<Point> set=new HashSet<>();
public static void length(int[][] arr, int i, int j){
sum++;
arr[i][j]=0;
Point p=new Point(i,j);
set.add(p);
if (arr[i-1][j]==1)
length(arr,i-1,j);
if (arr[i+1][j]==1)
length(arr,i+1,j);
if (arr[i][j-1]==1)
length(arr,i,j-1);
if (arr[i][j+1]==1)
length(arr,i,j+1);
}
}
?G、買二贈一（時間限制: 1.0s 內(nèi)存限制: 512.0MB）
【問題描述】某商場有 N 件商品，其中第 i 件的價格是 A i ?，F(xiàn)在該商場正在進行 “ 買二 贈一” 的優(yōu)惠活動，具體規(guī)則是： 每購買 2 件商品，假設(shè)其中較便宜的價格是 P （如果兩件商品價格一樣，則 P 等于其中一件商品的價格），就可以從剩余商品中任選一件價格不超過 P /2 的商品，免費獲得這一件商品?？梢酝ㄟ^反復(fù)購買 2 件商品來獲得多件免費商 品，但是每件商品只能被購買或免費獲得一次。 小明想知道如果要拿下所有商品（包含購買和免費獲得），至少要花費多少錢？【輸入格式】第一行包含一個整數(shù) N 。第二行包含 N 個整數(shù)，代表 A 1 , A 2 , A 3 , . . . ， A N【輸出格式】輸出一個整數(shù)，代表答案。【樣例輸入】7 1 4 2 8 5 7 1【樣例輸出】
25【樣例說明】
小明可以先購買價格 4 和 8 的商品，免費獲得一件價格為 1 的商品；再后買價格為 5 和 7 的商品，免費獲得價格為 2 的商品；最后單獨購買剩下的一件價格為 1 的商品?？傆嫽ㄙM 4 + 8 + 5 + 7 + 1 = 25 。不存在花費更低的方案。【評測用例規(guī)模與約定】對于 30 % 的數(shù)據(jù)， 1 ≤ N ≤ 20 。對于 100 % 的數(shù)據(jù)， 1 ≤ N ≤ 5 × 10? ，1 ≤ A i ≤ 10? 。
?Ⅰ、題目解讀
要花費最少，就要購買的商品價格高點，這樣可以白嫖到更貴的商品，而不是便宜的商品。如題目所給樣例：7+8（2）+4+5（1）+1=25。我認為可以使用數(shù)組儲存再sort排序，然后使用二分查找到符合小于p/2的最大值，再將已經(jīng)買完的商品變?yōu)?（或者其他方法標(biāo)記為已購買的狀態(tài)），然后不斷重復(fù)上面步驟。（博主使用word打開題目，題目有問題，p/2顯示的是p2，看錯題目了，純純大冤種??????）。
?Ⅱ、代碼1(復(fù)雜度過大，超時)
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
long[] arr=new long[n];
for (int i=0;i<n;i++){
arr[i]=sc.nextInt();
}
//進行排序商品
Arrays.sort(arr);
long sum=0;
//arr數(shù)組中全為0才可以退出循環(huán)，因為全部東西都需要購買
while (arr[arr.length-1]!=0){
//盡量買大的商品，這樣可以盡量白嫖到更貴的商品
long k=arr[arr.length-2]/2;
sum+=(arr[arr.length-2]+arr[arr.length-1]);
//開始二分查找
int l=0,r=arr.length-1;
int mid=(l+r)/2;
while (l<=r){
if (arr[mid]>k){
r=mid-1;
}else if (arr[mid]<k){
l=mid+1;
}else {
break;
}
mid=(l+r)/2;
}
//將商品設(shè)置為已購買的狀態(tài)
arr[mid]=0;
arr[arr.length-2]=0;
arr[arr.length-1]=0;
Arrays.sort(arr);
}
System.out.println(sum);
}
}
?或者創(chuàng)建 用來判斷 是否已購買的boolean數(shù)組 來進行判斷
代碼2（正確答案）
import java.util.*;
import java.io.*;
public class Main {
static int n,m,mod=(int)1e9+7,maxn=500010;
static long ans=0,INF=(long)1e18;
static Scanner sc = new Scanner (System.in);
static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
static StreamTokenizer st = new StreamTokenizer(bf);
static PrintWriter pw = new PrintWriter(System.out);
public static void main(String[]args) throws IOException{
int T = 1;
//T = I();
while(T-->0) solve();
pw.flush();
}
static int I() throws IOException{
st.nextToken();
return (int)st.nval;
}
static int a[] = new int [maxn];
static boolean f[] = new boolean [maxn];
static int find(int x) {
int l=1,r=n;
int res =0;
while(l<=r) {
int mid = (l+r)/2;
if(f[mid]) { //先前贈送過，跳到左邊
r=mid-1;continue;
}
if(a[mid] <= x) {
res = Math.max(res, mid);
l = mid+1;
}
else r = mid-1;
}
return res;
}
static void solve() throws IOException{
n = I();
for(int i=1 ;i<=n;i++) a[i] =I();
Arrays.sort(a,1,n+1);
int t = 0;
for(int i=n;i>=1;i--) {
if(f[i]) continue;//贈送過，跳過
ans += a[i];
t++;
if(t == 2) {
t=0;
int id = find(a[i]/2);
if(id>0) f[id]=true;
}
}
pw.println(ans);
}
}?H、合并石子（時間限制: 1.0s 內(nèi)存限制: 512.0MB）
【問題描述】在桌面從左至右橫向擺放著 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)的最小花費。【樣例輸入】5 5 10 1 8 6 1 1 0 2 2【樣例輸出】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 。
?Ⅰ、題目解讀
這題和G買二贈一有點類似，都是合并然后選擇某種方法標(biāo)記為已合并的狀態(tài)。我舉個例子（1，5）和（1，10）合并為（2，15），另一個變成已使用的狀態(tài)（3，0），之后進行二維數(shù)組排序，先排石子的顏色（0，1，2）,在排石子的數(shù)量（升序排），因為這樣才能保證花費最?。ㄩ_始合并也要進行一道排序）。不斷重復(fù)上面步驟計算花費，直到?jīng)]有一樣的石子可以合并了（3為已使用狀態(tài)不可以合并）。但是這上面有一個漏洞，我們可以看下面一組數(shù)據(jù)就懂了：（0，10），（0，11），（1，1），（1，2），（2，3）；如果按照上面的思路就是先合并（0，10）和（0，11），但是我們用肉眼就可以看出來應(yīng)該先合并（1，1），（1，2）->(2,3)和（3，0），然后兩個（2，3）變成（0，6）和（3，0），再去合并顏色為0的石子，因此合并的時候要去尋找一下不同石子可以合并的最小費用，優(yōu)先合并花費少的。
Ⅱ、代碼
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int[][] arr=new int[n][2];
for (int i=0;i<n;i++){
arr[i][1]=sc.nextInt();
}
for (int i=0;i<n;i++){
arr[i][0]=sc.nextInt();
}
//先進行石子排序，在進行不同石子的數(shù)量排序
Arrays.sort(arr,(o1, o2) -> {
if (o1[0]==o2[0])
return o1[1]-o2[1];
return o1[0]-o2[0];
});
boolean merge=false;//判斷是否有過合并，如果沒有過合并即退出循環(huán)
int sum=0;//所需花費
//n=1，無需合并，直接輸出
if (n==1){
System.out.println(1+" "+0);
return;
}
while (true){
int k=0;//用來記錄合并石子的下標(biāo)
int SumMin=9999;//用來記錄當(dāng)前最小的合并花費
boolean a=true;//第一次找到0
boolean b=true;//第一次找到1
for (int i=1;i<n&&arr[i][0]!=3;i++){
if (arr[i-1][0]==0&&arr[i][0]==0&&a){
k=i;
a=false;
SumMin=Math.min(SumMin,arr[i][1]+arr[i-1][1]);
merge=true;
}
if (arr[i-1][0]==1&&arr[i][0]==1&&b){
if (SumMin>arr[i][1]+arr[i-1][1]){
k=i;
SumMin=(arr[i][1]+arr[i-1][1]);
}
b=false;
merge=true;
}
if (arr[i-1][0]==2&&arr[i][0]==2){
if (SumMin>arr[i][1]+arr[i-1][1]){
k=i;
SumMin=(arr[i][1]+arr[i-1][1]);
}
merge=true;
break;
}
}
if (!merge)
break;
sum+=SumMin;
//合并石子之后，變換成新的顏色0，1，2
if (arr[k][0]==0){
arr[k-1][0]=1;
}else if (arr[k][0]==1){
arr[k-1][0]=2;
}else {
arr[k-1][0]=0;
}
arr[k-1][1]=SumMin;
//將已合并的石子設(shè)置為使用狀態(tài)
arr[k][0]=3;
arr[k][1]=0;
merge=false;
//進行進行排序
Arrays.sort(arr,(o1, o2) -> {
if (o1[0]==o2[0])
return o1[1]-o2[1];
return o1[0]-o2[0];
});
}
int l=0;//查找當(dāng)前還有幾堆石子
for (int i=0;i<n&&arr[i][0]!=3;i++){
l++;
}
System.out.println(l+" "+sum);
}
}
?I、最大開支（時間限制: 1.0s 內(nèi)存限制: 512.0MB ）
【問題描述】小藍所在學(xué)校周邊新開業(yè)了一家游樂園，小藍作為班長，打算組織大家去 游樂園玩。已知一共有 N 個人參加這次活動，游樂園有 M 個娛樂項目，每個 項目都需要買門票后才可進去游玩。門票的價格并不是固定的，團購的人越多 單價越便宜，當(dāng)團購的人數(shù)大于某個閾值時，這些團購的人便可以免費進入項 目進行游玩。這 M 個娛樂項目是獨立的，所以只有選擇了同一個項目的人才可 以參與這個項目的團購。第 i 個項目的門票價格 H i 與團購的人數(shù) X 的關(guān)系可 以看作是一個函數(shù)：Hi(X) = max (Ki × X + Bi , 0) ，max 表示取二者之中的最大值。當(dāng) H i = 0 時說明團購人數(shù)達到了此項目的免單閾值。 這 N 個人可以根據(jù)自己的喜好選擇 M 個娛樂項目中的一種，或者有些人 對這些娛樂項目都沒有興趣，也可以選擇不去任何一個項目。每個人最多只會 選擇一個娛樂項目，如果多個人選擇了同一個娛樂項目，那么他們都將享受對 應(yīng)的團購價格。小藍想知道他至少需要準(zhǔn)備多少錢，使得無論大家如何選擇， 他都有能力支付得起所有 N 個人購買娛樂項目的門票錢。【輸入格式】第一行兩個整數(shù) N 、 M ，分別表示參加活動的人數(shù)和娛樂項目的個數(shù)。 接下來 M 行，每行兩個整數(shù)，其中第 i 行為 K i 、 B i ，表示第 i 個游樂地點 的門票函數(shù)中的參數(shù)。【輸出格式】一個整數(shù)，表示小藍至少需要準(zhǔn)備多少錢，使得大家無論如何選擇項目， 自己都支付得起。【樣例輸入】4 2 -4 10 -2 7【樣例輸出】
12【樣例說明】
樣例中有 4 個人， 2 個娛樂項目，我們用一個二元組 ( a , b ) 表示 a 個人選 擇了第一個娛樂項目，b 個人選擇了第二個娛樂項目，那么就有 4 ? a ? b 個 人沒有選擇任何項目，方案 ( a , b ) 對應(yīng)的門票花費為 max ( ? 4 × a + 10 , 0) × a + max ( ? 2 × b + 7 , 0) × b ，所有的可能如下所示：
?其中當(dāng) a = 1, b = 2 時花費最大，為 12。此時 1 個人去第一個項目，所以第一個項目的單價為 10 ? 4 = 6，在這個項目上的花費為 6 × 1 = 6；2 個人去 第二個項目，所以第二個項目得單價為 7 ? 2 × 2 = 3，在這個項目上的花費為 2 × 3 = 6；還有 1 個人沒去任何項目，不用統(tǒng)計；總花費為 12，這是花費最大的一種方案，所以答案為 12。
【評測用例規(guī)模與約定】對于 30 % 的評測用例， 1 ≤ N , M ≤ 10 。對于 50 % 的評測用例， 1 ≤ N , M ≤ 1000 。對于 100 % 的評測用例， 1 ≤ N , M , B i ≤ 10? ，?10?? ?≤ K i < 0 。
?Ⅰ、題目解讀
?這題的解題思路就是：計算每個項目多一個人參加時造成的費用變化量，貪心的參加費用變化最多的項目。
?J、魔法陣（時間限制: 1.0s 內(nèi)存限制: 512.0MB ）
?【輸入格式】
第一行輸入三個整數(shù)， N , K , M ，用空格分隔。接下來 M 行，每行包含三個整數(shù) u , v , w ，表示結(jié)點 u 與結(jié)點 v 之間存在一條傷害屬性為 w 的無向邊。【輸出格式】輸出一行，包含一個整數(shù)，表示小藍從結(jié)點 0 到結(jié)點 N ? 1 受到的最小傷 害。【樣例輸入 1】
4 2 3 0 1 2 1 2 1 2 3 4【樣例輸出 1】
2【樣例輸入 2】2 5 1 0 1 1【樣例輸出 2】
0【樣例說明】樣例 1 ，存在路徑： 0 → 1 → 2 → 3 ， K = 2 ，如果在 0 → 1 → 2 上使用魔 法，那么答案就是 0 + 0 + 4 = 4 ；如果在 1 → 2 → 3 上使用魔法，那么答案就 是 2 + 0 + 0 = 2 。再也找不到比 2 還小的答案了，所以答案就是 2 。 樣例 2 ，存在路徑： 0 → 1 → 0 → 1 → 0 → 1 ， K = 5 ，這條路徑總計恰好 走了 5 條邊，所以正好可以用魔法消除所有傷害，答案是 0 。【評測用例規(guī)模與約定】對于 30 % 的評測用例， 1 ≤ N ≤ 20 。對于 50 % 的評測用例， 1 ≤ N ≤ 100 。對于 100 % 的評測用例， 1 ≤ N ≤ 1000 , 1 ≤ M ≤ N × ( N?1) /2 ，1 ≤ K ≤ 10 , 0 ≤ u , v ≤ N ? 1 ， 1 ≤ w ≤ 1000 。
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
?總結(jié)
博主第一次參加藍橋杯，還是發(fā)現(xiàn)自身的很多不足，比如上面幾題的貪心動態(tài)規(guī)劃，寫的時候沒有一點想法，完全跳過放棄寫下一題。還有各種情況想得不是很到位，還碰上了題目顯示錯誤的事，這是我沒想到的，主辦方也沒有說一定使用哪個軟件打開題目的啊????。道阻且長，我還需繼續(xù)加油，同時也感謝各位的支持。
有官方題解我也會第一時間更新，還請兄弟們點贊收藏一番。文章來源：http://www.zghlxwxcb.cn/news/detail-408914.html
上面題解代碼僅僅代表個人觀點，有問題歡迎各位佬評論指點，或直接給出解答。萬分感謝！文章來源地址http://www.zghlxwxcb.cn/news/detail-408914.html
到了這里，關(guān)于2023第十四屆藍橋杯JavaB組的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
