主頁 > 後端開發 > 2020年 第11屆 藍橋杯 Java B組 省賽真題詳解及小結【第2場省賽 2020.10.17】

2020年 第11屆 藍橋杯 Java B組 省賽真題詳解及小結【第2場省賽 2020.10.17】

2020-11-01 17:36:16 後端開發

  • 藍橋杯 Java B組 省賽真題詳解及小結匯總【2013年(第4屆)~2020年(第11屆)】
  • 說明：大部分題解思路及程式代碼 源自 藍橋杯 官網視頻(Java B組歷年真題決議) —— 鄭未老師，
  1. 2013年 第04屆 藍橋杯 Java B組 省賽真題詳解及小結
  2. 2014年 第05屆 藍橋杯 Java B組 省賽真題詳解及小結
  3. 2015年 第06屆 藍橋杯 Java B組 省賽真題詳解及小結
  4. 2016年 第07屆 藍橋杯 Java B組 省賽真題詳解及小結
  5. 2017年 第08屆 藍橋杯 Java B組 省賽真題詳解及小結
  6. 2018年 第09屆 藍橋杯 Java B組 省賽真題詳解及小結
  7. 2019年 第10屆 藍橋杯 Java B組 省賽真題詳解及小結
  8. 2020年 第11屆 藍橋杯 第1次模擬賽真題詳解及小結【Java版】（校內模擬）
  9. 2020年 第11屆 藍橋杯 第2次模擬賽真題詳解及小結【Java版】
  10. 2020年 第11屆 藍橋杯 C/C++ B組 省賽真題詳解及小結【第1場省賽 2020.07.05】【Java版】
  11. 2020年 第11屆 藍橋杯 Java B組 省賽真題詳解及小結【第1場省賽 2020.07.05】
  12. 2020年 第11屆 藍橋杯 Java B組 省賽真題詳解及小結【第2場省賽 2020.10.17】
  13. 2020年 第11屆 藍橋杯 Java C組 省賽真題詳解及小結【第1場省賽 2020.07.05】
  • 第11屆 藍橋杯-第1、2次模擬(軟體類)真題-(2020年3月、4月)-官方講解視頻

目 錄

一、試題 A: 門牌制作——答案：641

解法一：x % 10 == 2

解法二：雙重for回圈+字符陣列

二、試題 B: 尋找 2020——答案：16520

三、試題 C: 蛇形填數——答案：761

解法一：規律推公式 (n-1)(2n-1)+n

解法二：手工計算（寫滿兩頁A4演草紙）

解法三：第i行第i列的值為a = a + (i*4)

解法四：找規律

四、試題 D: 七段碼——答案：80

五、試題 E: 排序——jonmlkihgfedcba

六、試題 F: 成績分析

七、試題 G: 單詞分析

八、試題 H: 數字三角形

九、試題 I: 子串分值和

十、試題 J: 裝飾珠

小結

試題下載：【鏈接：https://pan.baidu.com/s/11bI8HRFmb_FitUMvC5NF6Q 提取碼：zjxs】

說明：本文參考了很多大佬的題解，

一、試題 A: 門牌制作——答案：641

本題總分：5 分

【問題描述】

小藍要為一條街的住戶制作門牌號，

這條街一共有 2020 位住戶，門牌號從 1 到 2020 編號，

小藍制作門牌的方法是先制作 0 到 9 這幾個數字字符，最后根據需要將字符粘貼到門牌上，例如門牌 1017 需要依次粘貼字符 1、0、1、7，即需要 1 個 字符 0，2 個字符 1，1 個字符 7，

請問要制作所有的 1 到 2020 號門牌，總共需要多少個字符 2？

【答案提交】

這是一道結果填空的題，你只需要算出結果后提交即可，本題的結果為一個整數，在提交答案時只填寫這個整數，填寫多余的內容將無法得分，

【答案】：624

解法一：x % 10 == 2

【決議】：從1~2020開始回圈，一直計算即可，

package provincialGames_11_2020_2_JavaB;

public class _01_A_門牌制作 {

	public static void main(String[] args) {
		int ans = 0;
		for (int i = 1; i <= 2020; i++) {
			int x = i;
			while (x > 0) {
				if (x % 10 == 2)
					ans++;
				x /= 10;
			}
		}
		System.out.println(ans);
	}

}

解法二：雙重for回圈+字符陣列

【決議】：從1~2020開始回圈，將數字轉為字符數字，逐個比較字符，

package provincialGames_11_2020_2_JavaB;

public class _01_A_門牌制作2 {

	public static void main(String[] args) {
		int ans = 0;
		for (int i = 1; i <= 2020; i++) {
			char strArray[] = (i + "").toCharArray();
			for (int j = 0; j < strArray.length; j++) {
				if (strArray[j] == '2') {
					ans++;
				}
			}
		}
		System.out.println(ans);
	}

}

二、試題 B: 尋找 2020——答案：16520

本題總分：5 分

【問題描述】

小藍有一個數字矩陣，里面只包含數字 0 和 2，小藍很喜歡 2020，他想找到這個數字矩陣中有多少個 2020 ，

小藍只關注三種構成 2020 的方式：

? 同一行里面連續四個字符從左到右構成 2020，

? 同一列里面連續四個字符從上到下構成 2020，

? 在一條從左上到右下的斜線上連續四個字符，從左上到右下構成 2020，

例如，對于下面的矩陣：

220000

000000

002202

000000

000022

002020

一共有 5 個 2020，其中 1 個是在同一行里的，1 個是在同一列里的，3 個是斜線上的，

小藍的矩陣比上面的矩陣要大，由于太大了，他只好將這個矩陣放在了一個檔案里面，在試題目錄下有一個檔案 2020.txt，里面給出了小藍的矩陣，

請幫助小藍確定在他的矩陣中有多少個 2020，

【答案提交】

這是一道結果填空的題，你只需要算出結果后提交即可，本題的結果為一 個整數，在提交答案時只填寫這個整數，填寫多余的內容將無法得分，

【決議】：定義二維矩陣，遍歷每個坐標，以每個坐標為起點分別向右向下向右下三個方向遍歷，

原文鏈接

打開 txt 檔案，滑鼠放到最后一行最后一列，可以知道，是一個300行300列的矩陣，然后直接暴力三次回圈，分別是從左到右，從上到下，從左上到右下方向，比賽的時候在這里耗時有點久，因為除錯的時候，發現我復制輸入這個矩陣后，控制臺輸出的矩陣只有260多行，一直以為哪里寫錯了， 

package provincialGames_11_2020_2_JavaB;

import java.util.Scanner;

public class _02_B_尋找2020 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int[][] num = new int[301][301];
		for (int i = 1; i <= 300; i++) {
			String str = sc.next();
			for (int j = 1; j <= str.length(); j++) {
				num[i][j] = str.charAt(j - 1) - '0';
			}
		}
		int ans = 0;
		for (int i = 1; i <= 300; i++) {
			for (int j = 1; j <= 300; j++) {
				if (i + 3 <= 300 && num[i][j] == 2 && num[i + 1][j] == 0 && num[i + 2][j] == 2 && num[i + 3][j] == 0)
					ans++;
			}
		}
		for (int i = 1; i <= 300; i++) {
			for (int j = 1; j <= 300; j++) {
				if (j + 3 <= 300 && num[i][j] == 2 && num[i][j + 1] == 0 && num[i][j + 2] == 2 && num[i][j + 3] == 0)
					ans++;
			}
		}
		for (int i = 1; i <= 300; i++) {
			for (int j = 1; j <= 300; j++) {
				if (i + 3 <= 300 && j + 3 <= 300 && num[i][j] == 2 && num[i + 1][j + 1] == 0 && num[i + 2][j + 2] == 2
						&& num[i + 3][j + 3] == 0)
					ans++;
			}
		}
		System.out.println(ans);
	}

}

三、試題 C: 蛇形填數——答案：761

本題總分：10 分

【問題描述】

如下圖所示，小明用從 1 開始的正整數“蛇形”填充無限大的矩陣，

1 2 6 7 15 ...

3 5 8 14 ...

4 9 13 ...

10 12 ... (1)

11 ...

...

容易看出矩陣第二行第二列中的數是 5，請你計算矩陣中第 20 行第 20 列的數是多少？

【答案提交】

這是一道結果填空的題，你只需要算出結果后提交即可，本題的結果為一個整數，在提交答案時只填寫這個整數，填寫多余的內容將無法得分，

【答案】：761

解法一：規律推公式 (n-1)(2n-1)+n

原文鏈接

【決議】：由 規律推公式 (n-1)*(2n-1)+n ，帶入n=20得結果，

  • 第1行：(1 - 1) * (2 * 1 - 1) + 1 = 1
  • 第2行：(1-1)*(2*1 - 1) + 1 = 1
  • 第3行：(1-1)*(2*1 - 1) + 1 = 1
  • ...

解法二：手工計算（寫滿兩頁A4演草紙）

【決議】：計算程序——從第1行第1列資料開始計算，一致計算到第20行20列，差不多寫滿了2頁A4紙...

考試的時候，監考員會給每個考生發一張空白A4紙，使用A4紙進行手工計算，演草紙不夠的話，A4紙列印的準考證背面也可以使用，

這種題，一看就是找規律的題，大致一看，題中規律顯然與斐波那契數列沒有關系，慌了...

藍橋杯就好考斐波那契、全排列，但是這次省賽貌似都沒考...

不管黑貓🐱、白貓🐱，抓住耗子🐀就是好貓，o(=?ェ?=)m

解法三：第i行第i列的值為a = a + (i*4)

原文鏈接

先說下我考試的思路吧，就是把整個矩陣想左轉45°，然后就可以發現是一個有規律的三角形，可以發現矩陣中第 i 行第 j 列的數在這個三角形中是第 i* 2-1 行 j* 2-1 列最中間的數，那么第20行第20列就在三角形中的第39行39列的中間，答案也就出來了，

再說下別人的做法，直接找規律，第一行第一列的值為1，第二行第二列的值為5，第三行第三列的值為13，第四行第四列的值為25，仔細觀察就可以發現第i行第i列的值為 a = a + (i*4)，可能要多畫幾個矩陣，才能發現規律，

package provincialGames_11_2020_2_JavaB;

public class _03_C_蛇形填數 {
	public static void main(String[] args) {
		int n = 20;
		System.out.println((n - 1) * (2 * n - 1) + n);
		System.out.println("---------");
		for (int i = 1; i <= 20; i++) {
			System.out.println((i - 1) * (2 * i - 1) + i);
		}
		System.out.println("---------");
		int a = 1;
		for (int i = 0; i < 20; i++) {
			a = a + (i * 4);
			System.out.println(a);
		}
	}
}

解法四：找規律

原文鏈接

第一行第一列是1；
第二行第二列是前面兩條斜行（左上到右下或者右上到左下為一條斜行），再數兩個數，
第三行第三列是前面四條斜行，再數三個數，
依次類推，20行第20列是前面38條斜行，再數20個數，
38條斜行為：1+2+…+38，最后結果（1+2+…+38）+20 = (1+38)38/2 +20 = 3919+20 = 761

四、試題 D: 七段碼——答案：80

【問題描述】

小藍要用七段碼數碼管來表示一種特殊的文字，

上圖給出了七段碼數碼管的一個圖示，數碼管中一共有 7 段可以發光的二 極管，分別標記為 a, b, c, d, e, f, g，

小藍要選擇一部分二極管（至少要有一個）發光來表達字符，在設計字符 的表達時，要求所有發光的二極管是連成一片的，

例如：b 發光，其他二極管不發光可以用來表達一種字符，

例如：c 發光，其他二極管不發光可以用來表達一種字符，這種方案與上一行的方案可以用來表示不同的字符，盡管看上去比較相似，

例如：a, b, c, d, e 發光，f, g 不發光可以用來表達一種字符，

例如：b, f 發光，其他二極管不發光則不能用來表達一種字符，因為發光 的二極管沒有連成一片，

請問，小藍可以用七段碼數碼管表達多少種不同的字符？

【答案提交】

這是一道結果填空的題，你只需要算出結果后提交即可，本題的結果為一個整數，在提交答案時只填寫這個整數，填寫多余的內容將無法得分，

【答案】：80

【決議】：列舉127種字符組合，挨個查看是否聯通，DFS生成127個字符組合，

原文鏈接 思路： 本題的大致思路是

  1. 將數碼管的七段進行全排列（用數字代表數碼管欄位,0代表a，1代表b,以此類推）然后將這7個數字的所有可能全部排列（從7個數字中取m（1<=m<=7）進行排列）列舉出來，
  2. 得到所有的取值情況，再判斷每種情況構成的圖是否連通，若連通，sum++
  3. 進行排列時需要注意，一定要保證每個排列必須是遞增或者遞減,這樣才能不重復，例如：012,021,210等等，它們都表示數碼管中取出ABC這一種情況，

package provincialGames_11_2020_2_JavaB;

public class _04_D_七段碼 {
	
	static boolean[][] M;// M是鄰接矩陣
	static int[] a;// a代表排列組合的數字
	static int sum = 0;// 最后結果

	public static void main(String[] args) {
		/*
		 * M是鄰接矩陣，根據數碼管影像可以得到 例如：a和b,a和f都可以連通，那么代表0和1,0和5連通
		 */
		M = new boolean[7][7];
		M[0][1] = M[1][0] = M[0][5] = M[5][0] = true;
		M[1][2] = M[2][1] = M[1][6] = M[6][1] = true;
		M[2][3] = M[3][2] = M[2][6] = M[6][2] = true;
		M[4][3] = M[3][4] = true;
		M[4][5] = M[5][4] = M[4][6] = M[6][4] = true;
		M[5][6] = M[6][5] = true;
		a = new int[7];
		for (int i = 0; i < a.length; i++) {
			a[i] = i;
		}
		// 所有排列的可能，深搜
		for (int n = 1; n <= 7; n++) {
			dfs(0, n);
		}
		System.out.println(sum);
	}

	public static void dfs(int k, int n) {
		if (k == n) {
			// 如果只有一個數,那么這種情況下必然成立
			if (n == 1) {
				sum++;
				return;
			}
			// 判斷，這種情況下的圖是否連通，用的是并查集方法
			// 初始化
			int[] pre = new int[n];
			for (int i = 0; i < pre.length; i++) {
				pre[i] = i;
			}
			for (int i = 0; i < n; i++) {
				for (int j = i + 1; j < n; j++) {
					// 兩層for窮舉所有邊的情況
					// 若i和j連通,j加入i
					// i和j代表的是結點，所以并的時候就是jion(pre,
					// i,j)，但是i代表的結點好j代表的結點是否連通，則需要看a[i]]和[a[j]在鄰接矩陣M中是否為真
					if (M[a[i]][a[j]]) {
						jion(pre, i, j);
					}
				}
			}
			// 到最后，若所有結點都連通，則所有結點的跟結點應該都一樣，否則說明此情況下的圖不連通
			boolean flag = true;
			for (int i = 1; i < pre.length; i++) {
				if (find(pre, 0) != find(pre, i)) {
					flag = false;
					break;
				}
			}
			if (flag) {
				sum++;
			}
			return;
		}
		// dfs，深搜
		for (int i = k; i < a.length; i++) {
			if (k == 0 || a[i] > a[k - 1]) {
				int t = a[i];
				a[i] = a[k];
				a[k] = t;
				dfs(k + 1, n);
				t = a[i];
				a[i] = a[k];
				a[k] = t;
			}
		}
	}

	// 查找根節點
	public static int find(int[] pre, int node) {
		int son = node, temp = 0;
		// 查找根節點
		while (node != pre[node]) {
			node = pre[node];
		}
		// 路徑優化
		while (son != node) {
			temp = pre[son];
			// 直接通跟
			pre[son] = node;
			// son向上走一格
			son = pre[son];
		}
		return node;
	}

	// 兩個結點相并
	public static void jion(int[] pre, int x, int y) {
		int fx = find(pre, x);
		int fy = find(pre, y);
		// 兩個結點屬于不同圖，相并
		if (fx != fy) {
			pre[fy] = fx;
		}
	}

}

五、試題 E: 排序——jonmlkihgfedcba

本題總分：15 分

【問題描述】

小藍最近學習了一些排序演算法，其中冒泡排序讓他印象深刻，

在冒泡排序中，每次只能交換相鄰的兩個元素，

小藍發現，如果對一個字串中的字符排序，只允許交換相鄰的兩個字符，則在所有可能的排序方案中，冒泡排序的總交換次數是最少的，

例如，對于字串 lan 排序，只需要 1 次交換，對于字串 qiao 排序，總共需要 4 次交換，

小藍找到了很多字串試圖排序，他恰巧碰到一個字串，需要 100 次交換，可是他忘了吧這個字串記下來，現在找不到了，

請幫助小藍找一個只包含小寫英文字母且沒有字母重復出現的字串，對該串的字符排序，正好需要 100 次交換，如果可能找到多個，請告訴小藍最短的那個，如果最短的仍然有多個，請告訴小藍字典序最小的那個，請注意字串中可以包含相同的字符，

【答案提交】

這是一道結果填空的題，你只需要算出結果后提交即可，本題的結果為一個只包含小寫英文字母的字串，在提交答案時只填寫這個字串，填寫多余的內容將無法得分，

【答案】：jonmlkihgfedcba

【決議】：冒泡排序，要求字串最短，那就假設完全逆序，設長度為n，則移動次數為 n*(n-1)/2，要求移動次數恰好大于100，則 n=15；移動次數105，要求字典序最小，則把第六個字符移動到第一個位置，前五個字符后移一位，純邏輯推導，無代碼，

原文鏈接

思路： 首先要注意最后得到的字串全是英文小寫字母并且不重復，接下來進行分析，最后要求結果在最短的前提下字典序最小，那么我們先想辦法找到最短的結果，
??最短，那是能多短就多短，最短是長度是1，但是肯定不可能，因為他還要求字串進行了100次交換，那么長度為2可不可以呢？也不行，長度為2的字串最多進行一次交換，
??一個長度為n的字串，如果進行冒泡排序，假設他每次比較都進行了交換，那么它最多交換 (n-1)+(n-2)+…+1 = n*(n-1）/2 （進行n-1趟操作，第一趟操作交換n-1次，之后每趟交換的次數依次遞減），
??在n*(n-1）/2>=100的前提下，n的最小值是15，也就是說，最后結果的字串的長度至少15（低于15,它根本連交換100次的要求都達不到），接下來再和題目要求的字典序最小一起考慮，
??首先了解一下字典序：字典序是指從前到后比較兩個字串的大小的方法，首先比較第一個字符，如果不同則第一個字符較小的字串更小，如果相同則繼續比較第2個字符…如此繼續，來比較整個字串的大小，
??現在我們知道字串全是英文小寫字母，并且長度為15且各不相同，那么我們可以確定這15個字母就是前15個小寫英文字母abcdefghijklklmno，怎么排現在還不知道，
??用逆向思維思考，若這15個字母每次冒泡兩兩比較都進行交換，能交換 15*(15-1) = 105次，那這個字串只可能是這15個字母的逆序：onmlkjighfedecba，
??然后我們再想辦法減少逆序字串的5次比較，并且使最后得到的結果字典序最小，只需要把逆序字串的第六位提前至第一位：jonmlkighfedecba，在這種情況下，字典序就是最小的，我只需要第一位比你小，我就是字典序最小的，而且第1，2，3，4，5趟，每次j會分別和o,n,m,k,l進行比較，但是不交換，這樣就省下了5次交換，且最后一共交換105-5=100次，

六、試題 F: 成績分析

時間限制: 1.0s 記憶體限制: 512.0MB 本題總分：15 分

【問題描述】

小藍給學生們組織了一場考試，卷面總分為 100 分，每個學生的得分都是一個 0 到 100 的整數，

請計算這次考試的最高分、最低分和平均分，

【輸入格式】

輸入的第一行包含一個整數 n，表示考試人數，

接下來 n 行，每行包含一個 0 至 100 的整數，表示一個學生的得分，

【輸出格式】

輸出三行，

第一行包含一個整數，表示最高分，

第二行包含一個整數，表示最低分，

第三行包含一個實數，四舍五入保留正好兩位小數，表示平均分，

【樣例輸入】

7

80

92

56

74

88

99

10

【樣例輸出】

99

10

71.29

【評測用例規模與約定】

對于 50% 的評測用例，1 ≤ n ≤ 100，

對于所有評測用例，1 ≤ n ≤ 10000，

【決議】：String.format("%.2f", xxx)：自動四舍五入

package provincialGames_11_2020_2_JavaB;

import java.util.Scanner;

public class _06_F_成績分析 { // String.format("%.2f", xxx)：自動四舍五入

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
		double sum = 0;
		for (int i = 0; i < n; i++) {
			int t = sc.nextInt();
			min = Math.min(min, t);
			max = Math.max(max, t);
			sum += t;
		}
		System.out.println(max + "\n" + min + "\n" + String.format("%.2f", sum / n));
	}

}

七、試題 G: 單詞分析

時間限制: 1.0s 記憶體限制: 512.0MB 本題總分：20 分

【問題描述】

小藍正在學習一門神奇的語言，這門語言中的單詞都是由小寫英文字母組成，有些單詞很長，遠遠超過正常英文單詞的長度，小藍學了很長時間也記不住一些單詞，他準備不再完全記憶這些單詞，而是根據單詞中哪個字母出現得最多來分辨單詞，

現在，請你幫助小藍，給了一個單詞后，幫助他找到出現最多的字母和這個字母出現的次數，

【輸入格式】

輸入一行包含一個單詞，單詞只由小寫英文字母組成，

【輸出格式】

輸出兩行，第一行包含一個英文字母，表示單詞中出現得最多的字母是哪個，如果有多個字母出現的次數相等，輸出字典序最小的那個，

第二行包含一個整數，表示出現得最多的那個字母在單詞中出現的次數，

【樣例輸入】

lanqiao

【樣例輸出】

a

2

【樣例輸入】

longlonglongistoolong

【樣例輸出】

o

6

【評測用例規模與約定】

對于所有的評測用例，輸入的單詞長度不超過 1000，

【決議】：記錄每個字符的出現次數即可，

package provincialGames_11_2020_2_JavaB;

import java.util.Scanner;

public class _07_G_單詞分析 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		char charArray[] = sc.next().toCharArray(); // 字符陣列
		int nums[] = new int[26]; // int型陣列 記錄 每個字母的出現次數
		for (int i = 0; i < charArray.length; i++) {
			nums[charArray[i] - 'a']++;
		}
		int ans = nums[0], index = 0;
		for (int i = 0; i < 26; i++) {
			if (nums[i] > ans) {
				ans = nums[i];
				index = i;
			}
		}
		System.out.println((char) ('a' + index) + "\n" + ans);
	}

}

八、試題 H: 數字三角形

時間限制: 1.0s 記憶體限制: 512.0MB 本題總分：20 分

【問題描述】

上圖給出了一個數字三角形，從三角形的頂部到底部有很多條不同的路徑，對于每條路徑，把路徑上面的數加起來可以得到一個和，你的任務就是找到最大的和，

路徑上的每一步只能從一個數走到下一層和它最近的左邊的那個數或者右邊的那個數，此外，向左下走的次數與向右下走的次數相差不能超過 1，

【輸入格式】

輸入的第一行包含一個整數 N (1 < N ≤ 100)，表示三角形的行數，下面的 N 行給出數字三角形，數字三角形上的數都是 0 至 100 之間的整數，

【輸出格式】

輸出一個整數，表示答案，

【樣例輸入】

5

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

【樣例輸出】

27

【決議】：dp推導+奇偶判斷

package provincialGames_11_2020_2_JavaB;

import java.util.Scanner;

public class _08_H_數字三角形 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int arr[][] = new int[n + 1][n + 1];
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= i; j++) {
				arr[i][j] = sc.nextInt();
				arr[i][j] += Math.max(arr[i - 1][j - 1], arr[i - 1][j]);
			}
		}
		System.out.println(n % 2 == 1 ? arr[n][n / 2 + 1] : Math.max(arr[n][n / 2], arr[n][n / 2 + 1]));
	}
}

九、試題 I: 子串分值和

試題 I: 子串分值和 時間限制: 1.0s 記憶體限制: 512.0MB 本題總分：25 分

【問題描述】

對于一個字串 S，我們定義 S 的分值 f(S ) 為 S 中出現的不同的字符個數，例如 f(”aba”) = 2，f(”abc”) = 3, f(”aaa”) = 1，

現在給定一個字串 S [0..n ? 1]（長度為 n），請你計算對于所有 S 的非空子串 S [i.. j](0 ≤ i ≤ j < n)，f(S [i.. j]) 的和是多少，

【輸入格式】

輸入一行包含一個由小寫字母組成的字串 S，

【輸出格式】

輸出一個整數表示答案，

【樣例輸入】

ababc

【樣例輸出】

28

【樣例說明】

子串 f值

a 1

ab 2

aba 2

abab 2

ababc 3

b 1

ba 2

bab 2

babc 3

a 1

ab 2

abc 3

b 1

bc 2

c 1

【評測用例規模與約定】

對于 20% 的評測用例，1 ≤ n ≤ 10；

對于 40% 的評測用例，1 ≤ n ≤ 100；

對于 50% 的評測用例，1 ≤ n ≤ 1000；

對于 60% 的評測用例，1 ≤ n ≤ 10000；

對于所有評測用例，1 ≤ n ≤ 100000，

【決議】：寫了個兩層暴力，for回圈，時間復雜度n^2，HashSet去重，

package provincialGames_11_2020_2_JavaB;

import java.util.HashSet;
import java.util.Scanner;

public class _09_I_字串分值和 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String string = sc.next();
		char c[] = string.toCharArray();
		long ans = 0;
		for (int i = 0; i < c.length; i++) {
			HashSet<Character> set = new HashSet<Character>(); // HashSet去重
			for (int j = i; j < c.length; j++) {
				set.add(c[j]);
				ans += set.size();
			}
		}
		System.out.println(ans);
	}

}

十、試題 J: 裝飾珠

時間限制: 1.0s 記憶體限制: 512.0MB 本題總分：25 分

【問題描述】

在怪物獵人這一款游戲中，玩家可以通過給裝備鑲嵌不同的裝飾珠來獲取相應的技能，以提升自己的戰斗能力，

已知獵人身上一共有 6 件裝備，每件裝備可能有若干個裝飾孔，每個裝飾孔有各自的等級，可以鑲嵌一顆小于等于自身等級的裝飾珠 (也可以選擇不鑲嵌)，

裝飾珠有 M 種，編號 1 至 M，分別對應 M 種技能，第 i 種裝飾珠的等級為 Li，只能鑲嵌在等級大于等于 Li 的裝飾孔中，

對第 i 種技能來說，當裝備相應技能的裝飾珠數量達到 Ki 個時，會產生 Wi(Ki) 的價值，鑲嵌同類技能的數量越多，產生的價值越大，即 Wi(Ki ? 1) < Wi(Ki)，但每個技能都有上限 Pi(1 ≤ Pi ≤ 7)，當裝備的珠子數量超過 Pi 時，只會產生 Wi(Pi) 的價值，

對于給定的裝備和裝飾珠資料，求解如何鑲嵌裝飾珠，使得 6 件裝備能得到的總價值達到最大，

【輸入格式】

輸入的第 1 至 6 行，包含 6 件裝備的描述，其中第 i 的第一個整數 Ni 表示第 i 件裝備的裝飾孔數量，后面緊接著 Ni 個整數，分別表示該裝備上每個裝飾 孔的等級 L(1 ≤ L ≤ 4)，

第 7 行包含一個正整數 M，表示裝飾珠 (技能) 種類數量，

第 8 至 M + 7 行，每行描述一種裝飾珠 (技能) 的情況，每行的前兩個整數 Lj(1 ≤ Lj ≤ 4) 和 Pj(1 ≤ Pi ≤ 7) 分別表示第 j 種裝飾珠的等級和上限，接下來 Pj 個整數，其中第 k 個數表示裝備該中裝飾珠數量為 k 時的價值 Wj(k)，

【輸出格式】

輸出一行包含一個整數，表示能夠得到的最大價值，

【樣例輸入】

1 1

2 1 2

1 1

2 2 2

1 1

1 3

3

1 5 1 2 3 5 8

2 4 2 4 8 15

3 2 5 10

【樣例輸出】

20

【樣例說明】

按照如下方式鑲嵌珠子得到最大價值 18，括號內表示鑲嵌的裝飾珠的種類編號：

1: (1)

2: (1)(2)

3: (1)

4: (2) (2)

5: (1)

6: (2)

4 顆技能 1 裝飾珠，4 顆技能 2 裝飾珠 W1(4) + W2(4) = 5 + 15 = 20，

【評測用例規模與約定】

暫無

小結

河南省賽區：一等獎得獎情況示例（75分）：

  • 一、試題 A: 門牌制作——本題總分：5 分
  • 三、試題 C: 蛇形填數——本題總分：10 分
  • 六、試題 F: 成績分析——本題總分：15 分
  • 七、試題 G: 單詞分析——本題總分：20 分
  • 九、試題 I: 子串分值和——本題總分：25 分

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/198340.html

標籤：python

上一篇：兔兔 的 題解 —— 2020 CSP-J 多校賽 T4

下一篇：Java語言實作石頭剪刀布游戲

標籤雲
其他(157675) Python(38076) JavaScript(25376) Java(17977) C(15215) 區塊鏈(8255) C＃(7972) AI(7469) 爪哇(7425) MySQL(7132) html(6777) 基礎類(6313) sql(6102) 熊猫(6058) PHP(5869) 数组(5741) R(5409) Linux(5327) 反应(5209) 腳本語言(PerlPython)(5129) 非技術區(4971) Android(4554) 数据框(4311) css(4259) 节点.js(4032) C語言(3288) json(3245) 列表(3129) 扑(3119) C++語言(3117) 安卓(2998) 打字稿(2995) VBA(2789) Java相關(2746) 疑難問題(2699) 细绳(2522) 單片機工控(2479) iOS(2429) ASP.NET(2402) MongoDB(2323) 麻木的(2285) 正则表达式(2254) 字典(2211) 循环(2198) 迅速(2185) 擅长(2169) 镖(2155) 功能(1967) .NET技术(1958) Web開發(1951) python-3.x(1918) HtmlCss(1915) 弹簧靴(1913) C++(1909) xml(1889) PostgreSQL(1872) .NETCore(1853) 谷歌表格(1846) Unity3D(1843) for循环(1842)

熱門瀏覽
  • 【C++】Microsoft C++、C 和匯編程式檔案

    ......

    uj5u.com 2020-09-10 00:57:23 more
  • 例外宣告

    相比于斷言適用于排除邏輯上不可能存在的狀態，例外通常是用于邏輯上可能發生的錯誤。 例外宣告 Item 1：當函式不可能拋出例外或不能接受拋出例外時，使用noexcept 理由 如果不打算拋出例外的話，程式就會認為無法處理這種錯誤，并且應當盡早終止，如此可以有效地阻止例外的傳播與擴散。 示例 //不可 ......

    uj5u.com 2020-09-10 00:57:27 more
  • Codeforces 1400E Clear the Multiset(貪心 + 分治)

    鏈接：https://codeforces.com/problemset/problem/1400/E 來源：Codeforces 思路：給你一個陣列，現在你可以進行兩種操作，操作1：將一段沒有 0 的區間進行減一的操作，操作2：將 i 位置上的元素歸零。最終問：將這個陣列的全部元素歸零后操作的最少 ......

    uj5u.com 2020-09-10 00:57:30 more
  • UVA11610 【Reverse Prime】

    本人看到此題沒有翻譯，就附帶了一個自己的翻譯版本 思考 這一題，它的第一個要求是找出所有 $7$ 位反向質數及其質因數的個數。 我們應該需要質數篩篩選1~$10^{7}$的所有數，這里就不慢慢介紹了。但是，重讀題，我們突然發現反向質數都是 $7$ 位，而將它反過來后的數字卻是 $6$ 位數，這就說明 ......

    uj5u.com 2020-09-10 00:57:36 more
  • 統計區間素數數量

    1 #pragma GCC optimize(2) 2 #include <bits/stdc++.h> 3 using namespace std; 4 bool isprime[1000000010]; 5 vector<int> prime; 6 inline int getlist(int ......

    uj5u.com 2020-09-10 00:57:47 more
  • C/C++編程筆記：C++中的 const 變數詳解，教你正確認識const用法

    1、C中的const 1、區域const變數存放在堆疊區中，會分配記憶體（也就是說可以通過地址間接修改變數的值）。測驗代碼如下： 運行結果： 2、全域const變數存放在只讀資料段（不能通過地址修改，會發生寫入錯誤）， 默認為外部聯編，可以給其他源檔案使用（需要用extern關鍵字修飾） 運行結果： ......

    uj5u.com 2020-09-10 00:58:04 more
  • 【C++犯錯記錄】VS2019 MFC添加資源不懂如何修改資源宏ID

    1. 首先在資源視圖中，添加資源 2. 點擊新添加的資源，復制自動生成的ID 3. 在解決方案資源管理器中找到Resource.h檔案，編輯，使用整個專案搜索和替換的方式快速替換 宏宣告 4. Ctrl+Shift+F 全域搜索，點擊查找全部，然后逐個替換 5. 為什么使用搜索替換而不使用屬性視窗直 ......

    uj5u.com 2020-09-10 00:59:11 more
  • 【C++犯錯記錄】VS2019 MFC不懂的批量添加資源

    1. 打開資源頭檔案Resource.h，在其中預先定義好宏 ID（不清楚其實ID值應該設定多少，可以先新建一個相同的資源項，再在這個資源的ID值的基礎上遞增即可） 2. 在資源視圖中選中專案資源，按F7編輯資源檔案，按 ID 型別 相對路徑的形式添加 資源。（別忘了先把檔案拷貝到專案中的res檔案 ......

    uj5u.com 2020-09-10 01:00:19 more
  • C/C++編程筆記：關于C++的參考型別，專供新手入門使用

    今天要講的是C++中我最喜歡的一個用法——參考，也叫別名。 參考就是給一個變數名取一個變數名，方便我們間接地使用這個變數。我們可以給一個變數創建N個參考，這N + 1個變數共享了同一塊記憶體區域。(參考型別的變數會占用記憶體空間，占用的記憶體空間的大小和指標型別的大小是相同的。雖然參考是一個物件的別名，但 ......

    uj5u.com 2020-09-10 01:00:22 more
  • 【C/C++編程筆記】從頭開始學習C ++：初學者完整指南

    眾所周知，C ++的學習曲線陡峭，但是花時間學習這種語言將為您的職業帶來奇跡，并使您與其他開發人員區分開。您會更輕松地學習新語言，形成真正的解決問題的技能，并在編程的基礎上打下堅實的基礎。 C ++將幫助您養成良好的編程習慣（即清晰一致的編碼風格，在撰寫代碼時注釋代碼，并限制類內部的可見性），并且由 ......

    uj5u.com 2020-09-10 01:00:41 more
最新发布
  • Rust中的智能指標:Box<T> Rc<T> Arc<T> Cell<T> RefCell<T> Weak

    Rust中的智能指標是什么 智能指標（smart pointers）是一類資料結構，是擁有資料所有權和額外功能的指標。是指標的進一步發展 指標（pointer）是一個包含記憶體地址的變數的通用概念。這個地址參考，或 ” 指向”（points at）一些其 他資料 。參考以 & 符號為標志并借用了他們所 ......

    uj5u.com 2023-04-20 07:24:10 more
  • Java的值傳遞和參考傳遞

    值傳遞不會改變本身，參考傳遞（如果傳遞的值需要實體化到堆里）如果發生修改了會改變本身。 1.基本資料型別都是值傳遞 package com.example.basic; public class Test { public static void main(String[] args) { int ......

    uj5u.com 2023-04-20 07:24:04 more
  • [2]SpinalHDL教程——Scala簡單入門

    第一個 Scala 程式 shell里面輸入 $ scala scala> 1 + 1 res0: Int = 2 scala> println("Hello World!") Hello World! 檔案形式 object HelloWorld { /* 這是我的第一個 Scala 程式 * 以 ......

    uj5u.com 2023-04-20 07:23:58 more
  • 理解函式指標和回呼函式

    理解 函式指標 指向函式的指標。比如： 理解函式指標的偽代碼 void (*p)(int type, char *data); // 定義一個函式指標p void func(int type, char *data); // 宣告一個函式func p = func; // 將指標p指向函式func ......

    uj5u.com 2023-04-20 07:23:52 more
  • Django筆記二十五之資料庫函式之日期函式

    本文首發于公眾號：Hunter后端 原文鏈接：Django筆記二十五之資料庫函式之日期函式 日期函式主要介紹兩個大類，Extract() 和 Trunc() Extract() 函式作用是提取日期，比如我們可以提取一個日期欄位的年份，月份，日等資料 Trunc() 的作用則是截取，比如 2022-0 ......

    uj5u.com 2023-04-20 07:23:45 more
  • 一天吃透JVM面試八股文

    什么是JVM？ JVM，全稱Java Virtual Machine（Java虛擬機），是通過在實際的計算機上仿真模擬各種計算機功能來實作的。由一套位元組碼指令集、一組暫存器、一個堆疊、一個垃圾回收堆和一個存盤方法域等組成。JVM屏蔽了與作業系統平臺相關的資訊，使得Java程式只需要生成在Java虛擬機 ......

    uj5u.com 2023-04-20 07:23:31 more
  • 使用Java接入小程式訂閱訊息！

    更新完微信服務號的模板訊息之后，我又趕緊把微信小程式的訂閱訊息給實作了！之前我一直以為微信小程式也是要企業才能申請，沒想到小程式個人就能申請。 訊息推送平臺🔥推送下發【郵件】【短信】【微信服務號】【微信小程式】【企業微信】【釘釘】等訊息型別。 https://gitee.com/zhongfuch ......

    uj5u.com 2023-04-20 07:22:59 more
  • java -- 緩沖流、轉換流、序列化流

    緩沖流 緩沖流, 也叫高效流, 按照資料型別分類： 位元組緩沖流：BufferedInputStream，BufferedOutputStream 字符緩沖流：BufferedReader，BufferedWriter 緩沖流的基本原理，是在創建流物件時，會創建一個內置的默認大小的緩沖區陣列，通過緩沖 ......

    uj5u.com 2023-04-20 07:22:49 more
  • Java-SpringBoot-Range請求頭設定實作視頻分段傳輸

    老實說，人太懶了，現在基本都不喜歡寫筆記了，但是網上有關Range請求頭的文章都太水了 下面是抄的一段StackOverflow的代碼...自己大修改過的，寫的注釋挺全的，應該直接看得懂，就不解釋了 寫的不好...只是希望能給視頻網站開發的新手一點點幫助吧. 業務場景：視頻分段傳輸、視頻多段傳輸（理 ......

    uj5u.com 2023-04-20 07:22:42 more
  • Windows 10開發教程_編程入門自學教程_菜鳥教程-免費教程分享

    教程簡介 Windows 10開發入門教程 - 從簡單的步驟了解Windows 10開發，從基本到高級概念，包括簡介，UWP，第一個應用程式，商店，XAML控制元件，資料系結，XAML性能，自適應設計，自適應UI，自適應代碼，檔案管理，SQLite資料庫，應用程式到應用程式通信，應用程式本地化，應用程式 ......

    uj5u.com 2023-04-20 07:22:35 more

Copyright © 2010-2020 有解無憂