第十三屆藍橋杯模擬賽第二期JAVA組個人題解

題目1

小藍的IP地址為 192.168.*.21，其中 * 是一個數字，請問這個數字最大可能是多少 ?

答案：255

題解：這個部分是計算機網路的內容，IP地址為8位二進制為一個位，每一個位都是2⁸-1=255,所以每IP地址最大為255.255.255.255（雖然真實中不可能存在這種IP地址，但是我們根據題意來）

題目2

如果一個整數 g 能同時整除整數 A 和 B，則稱 g 是 A 和 B 的公約數，例如：43 是 86 和 2021 的公約數，
請問在 1（含） 到 2021（含） 中，有多少個數與 2021 存在大于 1 的公約數，請注意 2021 和 2021 有大于 1 的公約數，因此在計算的時候要算一個，
答案：89

題解：我們直接寫一個gcd函式，判斷如果和2021公約數大于1就加1，最后直接輸出總數就行，

import java.util.*;
public class Main{
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		int cnt = 0;
		for(int i=1;i<=2021;i++) {
			if(gcd(i,2021)>1)
				cnt ++;
		}
		System.out.println(cnt);
	}
	static int gcd(int a,int b) {
		return b>0?gcd(b,a%b):a;
	}
}

題目3

2021 是一個非常特殊的數，它可以表示成兩個非負整數的平方差，2021 = 45 * 45 - 2 * 2，
2025 也是同樣特殊的數，它可以表示成 2025 = 45 * 45 - 0 * 0，
請問，在 1 到 2021 中有多少個這樣的數？
請注意，有的數有多種表示方法，例如 9 = 3 * 3 - 0 * 0 = 5 * 5 - 4 * 4，在算答案時只算一次，
答案：1516

題解：在做這道題的時候，回憶數學的平方差公式a²-b²=(a-b)(a+b)，那我們如果想讓a²-b²為正數，那么b必須小于a的，所以b是內層回圈，那外層回圈怎么控制呢，發現(a-b)(a+b)當a確定的時候，b=a-1的時候，是最小正數也就是（a-a+1）(a+a-1)=2a-1，我們讓2a-1去等于2021，得到a=1011，b=a-1=1010的最小正數是2021.所以有如下代碼：

import java.util.*;
public class Main{
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		int cnt = 0;
		int [] arr = new int[2022];
		for(int i=1;i<=1011;i++) {
			for(int j=0;j<i;j++) {
				int sum = i*i-j*j;
				if(sum<=2021)
					arr[sum] = 1;
			}
		}
		for(int i=1;i<=2021;i++)
			if(arr[i]==1)
				cnt++;
		System.out.println(cnt);
	}
}

題目4

小藍要用01串來表達一段文字，這段文字包含 a, b, c, d, e, f 共 6 個字母，每個字母出現的次數依次為：a 出現 10 次，b 出現 20 次，c 出現 3 次，d 出現 4 次，e 出現 18 次，f 出現 50 次，
　小藍準備分別對每個字母使用確定的01串來表示，不同字母的01串長度可以不相同，
　在表示文字時，將每個字母對應的01串直接連接起來組成最終的01串，為了能夠正常還原出文字，小藍的編碼必須是前綴碼，即任何一個字符對應的01串都不能是另一個字符對應的01串的前綴，
　例如，以下是一個有效的編碼：
　a: 000
　b: 111
　c: 01
　d: 001
　e: 110
　f: 100
　其中 c 的長度為 2，其它字母的編碼長度為 3，這種方式表示這段文字需要的總長度為：103+203+32+43+183+503=312，
　上面的編碼顯然不是最優的，將上面的 f 的編碼改為 10，仍然滿足條件，但是總長度為 262，要短 50，
　要想編碼后的總長度盡量小，應當讓出現次數多的字符對應的編碼短，出現次數少的字符對應的編碼長，
　請問，在最優情況下，編碼后的總長度最少是多少？
答案：219

題解：在做這道題的時候，我并不這道這是哈夫曼編碼，這邊建議去看一下哈夫曼編碼，挺好玩的一個東西，去B站搜哈夫曼編碼就有了，

構造完就是下面一顆樹

題目5

下面的矩陣中包含 ABCDEF 六種字符，請問出現最多的字符出現了幾次？
　FFEEFEAAECFFBDBFBCDA
　DACDEEDCCFFAFADEFBBA
　FDCDDCDBFEFCEDDBFDBE
　EFCAAEECEECDCDECADDC
　DFAEACECFEADCBFECADF
　DFBAAADCFAFFCEADFDDA
　EAFAFFDEFECEDEEEDFBD
　BFDDFFBCFACECEDCAFAF
　EFAFCDBDCCBCCEADADAE
　BAFBACACBFCBABFDAFBE
　FCFDCFBCEDCEAFBCDBDD
　BDEFCAAAACCFFCBBAAEE
　CFEFCFDEEDCACDACECFF
　BAAAFACDBFFAEFFCCCDB
　FADDDBEBCBEEDDECFAFF
　CDEAFBCBBCBAEDFDBEBB
　BBABBFDECBCEFAABCBCF
　FBDBACCFFABEAEBEACBB
　DCBCCFADDCACFDEDECCC
　BFAFCBFECAACAFBCFBAF
答案：78

題解：直接遍歷一遍就可以找出最大的了，使用sc.hasnext()控制回圈是為了方便輸入，在復制粘貼完后，輸入ctrl+z就可以結束輸入了，

import java.util.*;
public class Main{
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		String temp;
		int [] str = new int[6];
		while(sc.hasNext()) {
			temp = sc.next();
			for(int i=0;i<temp.length();i++) {
				char c = temp.charAt(i);
				str[c-'A']++;
			}
		}
		int max = 0;
		for(int i=1;i<6;i++)
			if(str[max]<str[i])
				max = i;
		System.out.println(str[max]);
	}
}

題目6

問題描述
小藍要到店里買鉛筆，
鉛筆必須一整盒一整盒買，一整盒 12 支，價格 p 元，
小藍至少要買 t 支鉛筆，請問他最少花多少錢？
輸入格式
輸入一行包含兩個整數 p、t，用一個空格分隔，
輸出格式
輸出一行包含一個整數，表示答案，
樣例輸入
5 30
樣例輸出
15
樣例說明
小藍至少要買3盒才能保證買到30支鉛筆，總共花費 15 元，
評測用例規模與約定
對于所有評測用例，1 <= p <= 100，1 <= t <= 10000，

題解：上取整乘錢就行，

import java.util.*;
public class Main{
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		int p,t;
		p = sc.nextInt();
		t = sc.nextInt();
		int r = t % 12;
		int number = t / 12;
		if(r>0) number ++;
		System.out.println(number*p);
	}
}

題目7

問題描述
給定一個三角形的三條邊的長度 a, b, c，請問這個三角形是不是一個直角三角形，
輸入格式
輸入一行包含三個整數 a, b, c，表示三角形三邊的長度，相鄰整數之間用一個空格分隔，
輸出格式
如果是直角三角形，輸出“YES”（全大寫），否則輸出“NO”（全大寫），
樣例輸入
3 4 5
樣例輸出
YES
樣例輸入
4 5 4
樣例輸出
NO
評測用例規模與約定
對于所有評測用例，1 <= a, b, c <= 1000，

題解：判斷三次即可

import java.util.*;
public class Main{
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		int a,b,c;
		a = sc.nextInt();
		b = sc.nextInt();
		c = sc.nextInt();
		if(a*a+b*b==c*c || a*a+c*c==b*b || b*b+c*c==a*a)
			System.out.println("YES");
		else
			System.out.println("NO");
	}
}

題目8

問題描述
n 個小朋友正在做一個游戲，每個人要分享一個自己的小秘密，
每個小朋友都有一個 1 到 n 的編號，編號不重復，
為了讓這個游戲更有趣，老師給每個小朋友發了一張卡片，上面有一個 1 到 n 的數字，每個數字正好出現一次，
每個小朋友都將自己的秘密寫在紙上，然后根據老師發的卡片上的數字將秘密傳遞給對應編號的小朋友，如果老師發給自己的數字正好是自己的編號，這個秘密就留在自己手里，
小朋友們拿到其他人的秘密后會記下這個秘密，老師會再指揮所有小朋友將手中的秘密繼續傳遞，仍然根據老師發的卡片上的數字將秘密傳遞給對應編號的小朋友，
這樣不斷重復 n 次，
現在，每個小朋友都記下了很多個秘密，
老師現在想找一些小朋友，能說出所有秘密，請問老師最少要找幾個小朋友？
輸入格式
? 輸入的第一行包含一個整數 n，
第二行包含 n 個整數 a[1], a[2], …, a[n]，相鄰的整數間用空格分隔，分別表示編號 1 到 n 的小朋友收到的數字，
輸出格式
輸出一行包含一個整數，表示答案，
樣例輸入
6
2 1 3 5 6 4
樣例輸出
3
樣例說明
最終小朋友 1, 2 互相知道了對方的秘密，小朋友 3 只知道自己的秘密，小朋友 4, 5, 6 互相知道了對方的秘密，
至少要找 3 個小朋友才能說出所有秘密，
評測用例規模與約定
對于 30% 的評測用例，2 <= n <= 30，
對于 60% 的評測用例，2 <= n <= 1000，
對于所有評測用例，2 <= n <= 100000，

題解：這道題覺的很熟，后面發現這是一道并查集的題，因為每個人的手上都有自己或別人的秘密，就像鏈表一樣，肯定會有一條條鏈，因為鏈中回圈n次，那鏈中的人一定會知道那條鏈中每個人的秘密，所以我們最后查一下有多少條鏈就知道問至少問多少個小盆友，就可以知道所有小盆友的秘密了，點擊查看并查集（并查集決議）

import java.util.*;
public class Main{
	static Scanner sc = new Scanner(System.in);
	static int n;
	static int [] a;
	static int cnt = 0;
	static int find(int k) {
		if(a[k]==k) return k;
		return a[k] = find(a[k]);
	}
	public static void main(String[] args) {
		n = sc.nextInt();
		int [] friends = new int[n+1];
		a = new int[n+1];
		for(int i=1;i<=n;i++)
			a[i] = i;
		for(int i=1;i<=n;i++)
			friends[i] = sc.nextInt();
		for(int i=1;i<=n;i++) {
			if(find(i) != find(friends[i]))
				a[find(i)] = find(friends[i]);
		}
		for(int i=1;i<=n;i++) {
			if(a[i] == i)
				cnt ++;
		}
		System.out.println(cnt);
	}
}

題目9

問題描述
一個 1 到 n 的排列被稱為半遞增序列，是指排列中的奇數位置上的值單調遞增，偶數位置上的值也單調遞增，
例如：(1, 2, 4, 3, 5, 7, 6, 8, 9) 是一個半遞增序列，因為它的奇數位置上的值是 1, 4, 5, 6, 9，單調遞增，偶數位置上的值是 2, 3, 7, 8，也是單調遞增，
請問，1 到 n 的排列中有多少個半遞增序列？
輸入格式
輸入一行包含一個正整數 n，
輸出格式
輸出一行包含一個整數，表示答案，答案可能很大，請輸出答案除以 1000000007 的余數，
樣例輸入
5
樣例輸出
10
樣例說明
有以下半遞增序列：
　(1, 2, 3, 4, 5)
　(1, 2, 3, 5, 4)
　(1, 2, 4, 3, 5)
　(1, 3, 2, 4, 5)
　(1, 3, 2, 5, 4)
　(1, 4, 2, 5, 3)
　(2, 1, 3, 4, 5)
(2, 1, 3, 5, 4)
(2, 1, 4, 3, 5)
(3, 1, 4, 2, 5)
評測用例規模與約定
對于 50% 的評測用例，2 <= n <= 20，
對于所有評測用例，2 <= n <= 1000，

題解：這是一個求組合數問題的經典題，當然我們實在想不到辦法的時候，可以dfs遍歷所有情況，選出符合的數，但是復雜度太大，一般復雜是O（n！）只能測10個數左右，我們這里講解一下正確的解題思路，我們假如取最大的數1000，那證明有500個奇數，500個偶數，我們從1000個數中選出500個奇數進行排序，一定且只有一種情況是遞增序列，剩余的偶數也一定只有一種排序是遞增的，這就成為了C_n^m組合問題了，但是C₁₀₀₀⁵⁰⁰的數太大了，已經遠遠超出int，而且還要取模，對于除法的取模也是很復雜的，我們這里采用楊輝三角解決這個組合問題，第n行的m個數可表示為C(n-1，m-1)，即為從n-1個不同元素中取m-1個元素的組合數，

import java.util.*;
public class Main{
	static Scanner sc = new Scanner(System.in);
	static int mod = (int)1e9+7;
	public static void main(String[] args) {
		int n = sc.nextInt();
		int k = n / 2;
		int [] a = new int[1001];
		a[0] = 1;
		for(int i=1;i<=n;i++) {
			a[0] = 1;
			a[i] = 1;
			for(int j=i-1;j>0;j--) {
				a[j] = (a[j] + a[j-1])%mod;
			}
		}
		System.out.println(a[k]);
	}
}

題目10

問題描述
小藍住在 LQ 城，今天他要去小喬家玩，
LQ 城可以看成是一個 n 行 m 列的一個方格圖，
小藍家住在第 1 行第 1 列，小喬家住在第 n 行第 m 列，
小藍可以在方格圖內走，他不愿意走到方格圖外，
城市中有的地方是風景優美的公園，有的地方是熙熙攘攘的街道，小藍很喜歡公園，不喜歡街道，他把方格圖中的每一格都標注了一個屬性，或者是喜歡的公園，標為1，或者是不喜歡的街道標為2，小藍和小喬住的地方都標為了1，
小藍每次只能從一個方格走到同一行或同一列的相鄰方格，他想找到一條路徑，使得不連續走兩次標為 2 的街道，請問在此前提下他最少要經過幾次街道？
輸入格式
輸入的第一行包含兩個整數 n, m，用一個空格分隔，
接下來 n 行，每行一個長度為 m 第數字串，表示城市的標注，
輸出格式
輸出一行包含一個整數，表示答案，如果沒有滿足條件的方案，輸出 -1，
樣例輸入
3 4
1121
1211
2211
樣例輸出
2
樣例輸入
3 4
1122
1221
2211
樣例輸出
-1
樣例輸入
5 6
112121
122221
221212
211122
111121
樣例輸出
5
評測用例規模與約定
對于 50% 的評測用例，2 <= n, m <= 20，
對于所有評測用例，2 <= n, m <= 300，

題解：這道題一開始以為是DP（動態規劃）問題，然后一直在推導公式，后來問同學，因為在圖中可以上下左右都可以走，所以不算動態規劃問題（可以想），同學提出了另外一種方案，就是將相鄰的1全部歸為一個點，如果一點和另一個點之間有只有一個2，則證明有邊相連，如果所在點和另一個點相隔2個2以上，則證明無邊（但需要證明這兩個點中的所有1都沒邊才能說這倆個點沒邊），構造好圖后，就是求圖中端點的最短距離了，也就是prim演算法或者dijkstra演算法，但是prim演算法的時間復雜度是O（n³）,dijkstra的時間復雜度是O（n²），但是都無法通過所有案例，因為n，m的最大值是300，最大方格90000，最壞情況，12121212，即圖中有一半的點也就是45000，倆個的時間復雜度都會爆，但是Dijkstra有優化演算法，可以降低時間復雜度，故可以解決，
（代碼還在思考中，后續更新）