2019年第十屆藍橋杯[Java]

特別數的和

【題目描述】
小明對數位中含有 2、0、1、9 的數字很感興趣(不包括前導 0)，在 1 到 40 中這樣的數包括 1、2、9、10 至 32、39 和 40，共 28 個，他們的和是 574，
請問，在 1 到 n 中，所有這樣的數的和是多少?
【輸入】
輸入一行包含兩個整數 n，
【輸出】
輸出一行，包含一個整數，表示滿足條件的數的和
【樣例輸入】
40
【樣例輸出】
574

代碼

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int sum = 0;
		for(int i = 1; i <= n; i++) {
			String str = Integer.toString(i);
//			if(str.indexOf('2') != -1 || str.indexOf('0') != -1 || str.indexOf('1') != -1 || str.indexOf('9') != -1) {
			if(str.contains("2") || str.contains("0") || str.contains("1") || str.contains("9")) {	
				sum += i;
			}
		}
		System.out.println(sum);
		sc.close();
	}
}

等引數列

【題目描述】
數學老師給小明出了一道等引數列求和的題目，但是粗心的小明忘記了一 部分的數列，只記得其中 N 個整數，現在給出這 N 個整數，小明想知道包含這 N 個整數的最短的等引數列有 幾項?
【輸入】
輸入的第一行包含一個整數 N， 第二行包含N個整數A1,A2,···,AN，(注意A1 ～AN并不一定是按等引數列中的順序給出)
【輸出】
輸出一個整數表示答案
【樣例輸入】
5
2 6 4 10 20
【樣例輸出】
10

代碼

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[] x = new int[N];
		for (int i = 0; i < N; i++) {
			x[i] = sc.nextInt();
		}
		Arrays.sort(x);
		int d = Integer.MAX_VALUE;
		for (int i = 0; i < x.length - 1; i++) {
			if (d > x[i + 1] - x[i]) {
				d = x[i + 1] - x[i];
			}
		}
		if (d == 0) {
			System.out.println(N);
		} else {
			System.out.println((x[x.length - 1] - x[0]) / d + 1);
		}
		sc.close();
	}
}

后綴運算式

【題目描述】
給定 N 個加號、M 個減號以及 N + M + 1 個整數 A1, A2, · · · , AN+M+1，小 明想知道在所有由這 N 個加號、M 個減號以及 N + M + 1 個整數湊出的合法的 后綴運算式中，結果最大的是哪一個?
請你輸出這個最大的結果，
例如使用1 2 3 + -，則 “2 3 + 1 -” 這個后綴運算式結果是 4，是最大的，
【輸入】
第一行包含兩個整數 N 和 M，
第二行包含 N + M + 1 個整數 A1, A2, · · · , AN+M+1，
【輸出】
輸出一個數，表示答案
【樣例輸入】
1 1
1 2 3
【樣例輸出】
4

代碼

import java.util.Arrays;
import java.util.Scanner;

public class Main	{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int add = sc.nextInt();
		int reduce = sc.nextInt();
		int t = add + reduce + 1;
		int[] number = new int[t];
		for (int i = 0; i < t; i++) {
			number[i] = sc.nextInt();
		}
		long sum = 0;
		if (reduce == 0 && add == 0) {
			sum += number[0];
		}
		if (reduce == 0 && add != 0) {
			for (int i = 0; i < t; i++) {
				sum += number[i];
			}
		}
		if (add == 0 && reduce != 0) {
			Arrays.sort(number);
			if (number[0] < 0) {
				for (int i = 0; i <= reduce; i++) {
					if (number[i] > 0) {
						sum += number[i];
					} else {
						sum -= number[i];
					}
				}
			} else {
				for (int i = 1; i <= reduce; i++) {
					sum += number[i];
				}
				sum -= number[0];
			}
		}
		if (add != 0 && reduce != 0) {
			int reduceNum = 0;
			for (int i = 0; i < t; i++) {
				if (number[i] < 0) {
					reduceNum++;
				}
			}
			if (reduce >= reduceNum) {
				if (reduceNum != 0) {
					Arrays.sort(number);
					for (int i = 0; i < reduceNum; i++) {
						number[i] = -number[i];
					}
					// Arrays.sort(number);
					for (int i = t - 1; i >= 0; i--) {
						sum += number[i];
					}
				}else {
					Arrays.sort(number);
					for (int i = t - 1; i > 0; i--) {
						sum += number[i];
					}
					sum -= number[0];
				}
			} else {
				Arrays.sort(number);
				sum += number[t - 1];
				for (int i = 0; i < t - 1; i++) {
					if (number[i] > 0) {
						sum += number[i];
					} else {
						sum -= number[i];
					}
				}
			}
		}
		System.out.println(sum);
		sc.close();
	}
}

旋轉

【題目描述】
圖片旋轉是對圖片最簡單的處理方式之一，在本題中，你需要對圖片順時針旋轉 90 度，
我們用一個 n × m 的二維陣列來表示一個圖片，例如下面給出一個 3 × 4 的圖片例子:
1 3 5 7
9 8 7 6
3 5 9 7
這個圖片順時針旋轉 90 度后的圖片如下:
3 9 1
5 8 3
9 7 5
7 6 7
給定初始圖片，請計算旋轉后的圖片

【輸入】
輸入的第一行包含兩個整數 n 和 m，分別表示行數和列數，
接下來 n 行，每行 m 個整數，表示給定的圖片，圖片中的每個元素(像
素)為一個值為 0 至 255 之間的整數(包含 0 和 255)，

【輸出】
輸出 m 行 n 列，表示旋轉后的圖片，

【樣例輸入】
3 4
1 3 5 7
9 8 7 6
3 5 9 7
【樣例輸出】
3 9 1
5 8 3
9 7 5
7 6 7

代碼

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		int[][] x = new int[m][n];
		for (int j = n - 1; j >= 0; j--) {
			for(int i = 0; i < m; i++) {
				x[i][j] = sc.nextInt();
			}
		}
		for(int i = 0; i < m; i++) {
			for(int j = 0; j < n; j++) {
				System.out.print(x[i][j] + " ");
			}
			System.out.println();
		}
		sc.close();
	}
}

Fibonacci 數列與黃金分割

【題目描述】
Fibonacci 數列是非常著名的數列:
F[1] = 1,
F[2] = 1,
對于 i > 3，F[i] = F[i ? 1] + F[i ? 2]
Fibonacci 數列有一個特殊的性質，前一項與后一項的比值，F[i]/F[i + 1]， 會趨近于黃金分割，
為了驗證這一性質，給定正整數 N，請你計算 F[N]/F[N + 1]，并保留 8 位 小數，
【輸入】
一個正整數 N，(1 ≤ N ≤ 2000000000)
【輸出】
F[N]/F[N + 1]，答案保留 8 位小數，
【樣例輸入】
2
【樣例輸出】
0.50000000

代碼

import java.math.BigDecimal;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long n = sc.nextLong();
		if(n == 1) {
			System.out.println("1.00000000");
		}
		else if (n > 50) {
			System.out.println("0.61803399");
		} else {
			BigDecimal[] f = new BigDecimal[(int)n + 2];
			f[1] = BigDecimal.ONE;
			f[2] = BigDecimal.ONE;
			for (int i = 3; i <= n + 1; i++) {
				f[i] = f[i - 1].add(f[i - 2]);
			}
			System.out.println(f[(int)n].divide(f[(int)n + 1], 8, BigDecimal.ROUND_HALF_UP));
		}
		sc.close();
	}
}