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

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

2020-11-02 01:06:03 其他

  • 藍橋杯 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/qita/198801.html

標籤：其他

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

下一篇：各位大佬們，最近換作業，想大家給點意見

標籤雲
其他(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)

熱門瀏覽
  • 網閘典型架構簡述

    網閘架構一般分為兩種：三主機的三系統架構網閘和雙主機的2+1架構網閘。 三主機架構分別為內端機、外端機和仲裁機。三機無論從軟體和硬體上均各自獨立。首先從硬體上來看，三機都用各自獨立的主板、記憶體及存盤設備。從軟體上來看，三機有各自獨立的作業系統。這樣能達到完全的三機獨立。對于“2+1”系統，“2”分為 ......

    uj5u.com 2020-09-10 02:00:44 more
  • 如何從xshell上傳檔案到centos linux虛擬機里

    如何從xshell上傳檔案到centos linux虛擬機里及：虛擬機CentOs下執行 yum -y install lrzsz命令，出現錯誤：鏡像無法找到軟體包 前言 一、安裝lrzsz步驟 二、上傳檔案 三、遇到的問題及解決方案 總結 前言 提示：其實很簡單，往虛擬機上安裝一個上傳檔案的工具 ......

    uj5u.com 2020-09-10 02:00:47 more
  • 一、SQLMAP入門

    一、SQLMAP入門 1、判斷是否存在注入 sqlmap.py -u 網址/id=1 id=1不可缺少。當注入點后面的引數大于兩個時。需要加雙引號， sqlmap.py -u "網址/id=1&uid=1" 2、判斷文本中的請求是否存在注入 從文本中加載http請求，SQLMAP可以從一個文本檔案中 ......

    uj5u.com 2020-09-10 02:00:50 more
  • Metasploit 簡單使用教程

    metasploit 簡單使用教程 浩先生， 2020-08-28 16:18:25 分類專欄： kail 網路安全 linux 文章標簽： linux資訊安全 編輯 著作權 metasploit 使用教程 前言 一、Metasploit是什么？ 二、準備作業 三、具體步驟 前言 Msfconsole ......

    uj5u.com 2020-09-10 02:00:53 more
  • 游戲逆向之驅動層與用戶層通訊

    驅動層代碼： #pragma once #include <ntifs.h> #define add_code CTL_CODE(FILE_DEVICE_UNKNOWN,0x800,METHOD_BUFFERED,FILE_ANY_ACCESS) /* 更多游戲逆向視頻www.yxfzedu.com ......

    uj5u.com 2020-09-10 02:00:56 more
  • 北斗電力時鐘（北斗授時服務器）讓網路資料更精準

    北斗電力時鐘（北斗授時服務器）讓網路資料更精準 北斗電力時鐘（北斗授時服務器）讓網路資料更精準 京準電子科技官微——ahjzsz 近幾年，資訊技術的得了快速發展，互聯網在逐漸普及，其在人們生活和生產中都得到了廣泛應用，并且取得了不錯的應用效果。計算機網路資訊在電力系統中的應用，一方面使電力系統的運行 ......

    uj5u.com 2020-09-10 02:01:03 more
  • 【CTF】CTFHub 技能樹 彩蛋 writeup

    ?碎碎念 CTFHub：https://www.ctfhub.com/ 筆者入門CTF時時剛開始刷的是bugku的舊平臺，后來才有了CTFHub。 感覺不論是網頁UI設計，還是題目質量，賽事跟蹤，工具軟體都做得很不錯。 而且因為獨到的金幣制度的確讓人有一種想去刷題賺金幣的感覺。 個人還是非常喜歡這個 ......

    uj5u.com 2020-09-10 02:04:05 more
  • 02windows基礎操作

    我學到了一下幾點 Windows系統目錄結構與滲透的作用 常見Windows的服務詳解 Windows埠詳解 常用的Windows注冊表詳解 hacker DOS命令詳解（net user / type /md /rd/ dir /cd /net use copy、批處理 等） 利用dos命令制作 ......

    uj5u.com 2020-09-10 02:04:18 more
  • 03.Linux基礎操作

    我學到了以下幾點 01Linux系統介紹02系統安裝，密碼啊破解03Linux常用命令04LAMP 01LINUX windows： win03 8 12 16 19 配置不繁瑣 Linux：redhat,centos(紅帽社區版)，Ubuntu server,suse unix:金融機構，證券，銀 ......

    uj5u.com 2020-09-10 02:04:30 more
  • 05HTML

    01HTML介紹 02頭部標簽講解03基礎標簽講解04表單標簽講解 HTML前段語言 js1.了解代碼2.根據代碼 懂得挖掘漏洞 （POST注入/XSS漏洞上傳）3.黑帽seo 白帽seo 客戶網站被黑帽植入劫持代碼如何處理4.熟悉html表單 <html><head><title>TDK標題，描述 ......

    uj5u.com 2020-09-10 02:04:36 more
最新发布
  • 2023年最新微信小程式抓包教程

    01 開門見山 隔一個月發一篇文章，不過分。 首先回顧一下《微信系結手機號資料庫被脫庫事件》，我也是第一時間得知了這個訊息，然后跟蹤了整件事情的經過。下面是這起事件的相關截圖以及近日流出的一萬條資料樣本： 個人認為這件事也沒什么，還不如關注一下之前45億快遞資料查詢渠道疑似在近日復活的訊息。 訊息是 ......

    uj5u.com 2023-04-20 08:48:24 more
  • web3 產品介紹：metamask 錢包 使用最多的瀏覽器插件錢包

    Metamask錢包是一種基于區塊鏈技術的數字貨幣錢包，它允許用戶在安全、便捷的環境下管理自己的加密資產。Metamask錢包是以太坊生態系統中最流行的錢包之一，它具有易于使用、安全性高和功能強大等優點。 本文將詳細介紹Metamask錢包的功能和使用方法。 一、 Metamask錢包的功能 數字資 ......

    uj5u.com 2023-04-20 08:47:46 more
  • vulnhub_Earth

    前言 靶機地址->>>vulnhub_Earth 攻擊機ip：192.168.20.121 靶機ip：192.168.20.122 參考文章 https://www.cnblogs.com/Jing-X/archive/2022/04/03/16097695.html https://www.cnb ......

    uj5u.com 2023-04-20 07:46:20 more
  • 從4k到42k，軟體測驗工程師的漲薪史，給我看哭了

    清明節一過，盲猜大家已經無心上班，在數著日子準備過五一，但一想到銀行卡里的余額……瞬間心情就不美麗了。最近，2023年高校畢業生就業調查顯示，本科畢業月平均起薪為5825元。調查一出，便有很多同學表示自己又被平均了。看著這一資料，不免讓人想到前不久中國青年報的一項調查：近六成大學生認為畢業10年內會 ......

    uj5u.com 2023-04-20 07:44:00 more
  • 最新版本 Stable Diffusion 開源 AI 繪畫工具之中文自動提詞篇

    🎈 標簽生成器 由于輸入正向提示詞 prompt 和反向提示詞 negative prompt 都是使用英文，所以對學習母語的我們非常不友好 使用網址：https://tinygeeker.github.io/p/ai-prompt-generator 這個網址是為了讓大家在使用 AI 繪畫的時候 ......

    uj5u.com 2023-04-20 07:43:36 more
  • 漫談前端自動化測驗演進之路及測驗工具分析

    隨著前端技術的不斷發展和應用程式的日益復雜，前端自動化測驗也在不斷演進。隨著 Web 應用程式變得越來越復雜，自動化測驗的需求也越來越高。如今，自動化測驗已經成為 Web 應用程式開發程序中不可或缺的一部分，它們可以幫助開發人員更快地發現和修復錯誤，提高應用程式的性能和可靠性。 ......

    uj5u.com 2023-04-20 07:43:16 more
  • CANN開發實踐：4個DVPP記憶體問題的典型案例解讀

    摘要：由于DVPP媒體資料處理功能對存放輸入、輸出資料的記憶體有更高的要求（例如，記憶體首地址128位元組對齊），因此需呼叫專用的記憶體申請介面，那么本期就分享幾個關于DVPP記憶體問題的典型案例，并給出原因分析及解決方法。 本文分享自華為云社區《FAQ_DVPP記憶體問題案例》，作者：昇騰CANN。 DVPP ......

    uj5u.com 2023-04-20 07:43:03 more
  • msf學習

    msf學習 以kali自帶的msf為例 一、msf核心模塊與功能 msf模塊都放在/usr/share/metasploit-framework/modules目錄下 1、auxiliary 輔助模塊，輔助滲透（埠掃描、登錄密碼爆破、漏洞驗證等） 2、encoders 編碼器模塊，主要包含各種編碼 ......

    uj5u.com 2023-04-20 07:42:59 more
  • Halcon軟體安裝與界面簡介

    1. 下載Halcon17版本到到本地 2. 雙擊安裝包后 3. 步驟如下 1.2 Halcon軟體安裝 界面分為四大塊 1. Halcon的五個助手 1) 影像采集助手：與相機連接，設定相機引數，采集影像 2) 標定助手：九點標定或是其它的標定，生成標定檔案及內參外參，可以將像素單位轉換為長度單位 ......

    uj5u.com 2023-04-20 07:42:17 more
  • 在MacOS下使用Unity3D開發游戲

    第一次發博客，先發一下我的游戲開發環境吧。 去年2月份買了一臺MacBookPro2021 M1pro(以下簡稱mbp)，這一年來一直在用mbp開發游戲。我大致分享一下我的開發工具以及使用體驗。 1、Unity 官網鏈接： https://unity.cn/releases 我一般使用的Apple ......

    uj5u.com 2023-04-20 07:40:19 more

Copyright © 2010-2020 有解無憂