2019年第十一届蓝桥杯校内选拔赛JavaB组题解

发表于 分类于 阅读次数：
本文字数： 17k 阅读时长 ≈ 16 分钟

一共十个题，都比较好做

题目1

问题描述
　　在计算机存储中，15.125GB是多少MB？

答案：15488
思路：1GB=1024MB
解题代码：

  • java:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    package wiki.zimo.exam2019;
    /**
    * 
    * @author zimo
    *
    */
    public class Demo01 {
    	public static void main(String[] args) {
    		System.out.println(15.125 * 1024);
    	}
    }

  • c++:

    1
    2
    3
    4
    5
    6
    7
    8
    #include <iostream>

    using namespace std;

    int main() {
    	cout << 15.125 * 1024 << endl;
    	return 0;
    }

题目2

问题描述
　　不超过19000的正整数中，与19000互质的数的个数是多少？

答案：7200
思路：两个数互质，那么它们的最大公约数是1
解题代码：

  • java:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    package wiki.zimo.exam2019;
    /**
    * 
    * @author zimo
    *
    */
    public class Demo02 {
    	public static void main(String[] args) {
    		int ans = 0;
    		for (int i = 1;i <= 19000;i++) {
    			if (gcd(i,19000) == 1) {
    				ans++;
    			}
    		}
    		System.out.println(ans);
    	}

    	private static int gcd(int a, int b) {
    		if (b == 0) {
    			return a;
    		} else {
    			return gcd(b,a % b);
    		}
    	}
    }

  • c++:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    #include <iostream>

    using namespace std;

    int gcd(int a, int b) {
    	if (b == 0) {
    		return a;
    	} else {
    		return gcd(b, a % b);
    	}
    }

    int main() {
    	int ans = 0;
    	for (int i = 1; i <= 19000; i++) {
    		if (gcd(i, 19000) == 1) {
    			ans++;
    		}
    	}
    	cout << ans << endl;
    	return 0;
    }

题目3

问题描述
　　一个包含有2019个结点的二叉树，最少有多少层？
　　注意当一棵二叉树只有一个结点时为一层。

答案：11
思路：满二叉树层数最少，而满二叉树第一层节点数是1，第二层节点数是2，第三层节点数是4，，，以此类推，第n层节点数是2的n-1次方，于是这题目就变成了1+2+4+…+2n-1>2019
解题代码：

  • java:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    package wiki.zimo.exam2019;
    /**
    * 
    * @author zimo
    *
    */
    public class Demo03 {
    	public static void main(String[] args) {
    		int a = 0;
    		int d = 1;;
    		for (int i = 0;i < Integer.MAX_VALUE;i++) {
    			a += Math.pow(2, i);
    			System.out.println(d + "," + a);
    			if (a >= 2019) {
    				break;
    			}
    			d++;
    		}
    		System.out.println(d);
    	}
    }

  • c++:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    #include <iostream>
    #include <cmath>

    using namespace std;

    int main() {
    	int a = 0;
    	int d = 1;;
    	for (int i = 0; i < INT_MAX; i++) {
    		a += pow(2, i);
    //        cout << d << "," << a << endl;
    		if (a >= 2019) {
    			break;
    		}
    		d++;
    	}
    	cout << d << endl;
    	return 0;
    }

题目4

问题描述
　　由1对括号，可以组成一种合法括号序列：()。
　　由2对括号，可以组成两种合法括号序列：()()、(())。
　　由4对括号组成的合法括号序列一共有多少种？

答案：14
思路：对四对括号，先用回溯法全排列，然后set暴力去重，最后用stack验证是否合法
代码：

  • java:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    package wiki.zimo.exam2019;

    import java.util.HashSet;
    import java.util.Stack;

    /**
    * 
    * @author zimo
    *
    */
    public class Demo04 {
    	static HashSet<String> set = new HashSet<String>();
    	public static void main(String[] args) {
    		String s = "(((())))";
    		// 回溯法全排列，set暴力去重，stack验证是否合法
    		dfs(s.toCharArray(),0);
    		
    		int ans = 0;
    		for (String str : set) {
    			if (judge(str)) {
    				ans++;
    				System.out.println(str);
    			}
    		}
    		
    		System.out.println(ans);
    	}
    	
    	private static boolean judge(String str) {
    		Stack<Character> stack = new Stack<>();
    		for (int i = 0;i < str.length();i++) {
    			char c = str.charAt(i);
    			if (c == '(') {
    				stack.push(c);
    			}
    			
    			if (c == ')') {
    				if (stack.isEmpty()) {
    					return false;
    				}
    				stack.pop();
    			}
    		}
    		return stack.isEmpty();
    	}

    	private static void dfs(char[] a, int b) {
    		if (b >= a.length) {
    			String s = new String(a);
    			set.add(s);
    		}
    		
    		for (int i = b;i < a.length;i++) {
    			{char t = a[i];a[i] = a[b];a[b] = t;}
    			dfs(a, b + 1);
    			{char t = a[i];a[i] = a[b];a[b] = t;}
    		}
    	}
    }

  • c++:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    #include <iostream>
    #include <set>

    using namespace std;

    set<string> se;

    void dfs(string a, int b, int n) {
    	if (b >= n) {
    		se.insert(a);
    	}

    	for (int i = b; i < n; i++) {
    		{
    			char t = a[i];
    			a[i] = a[b];
    			a[b] = t;
    		}
    		dfs(a, b + 1, n);
    		{
    			char t = a[i];
    			a[i] = a[b];
    			a[b] = t;
    		}
    	}
    }

    bool judge(string str, int n) {
    	int left = 0;
    	for (int i = 0; i < str.length(); i++) {
    		char c = str[i];
    		if (c == '(') {
    			left++;
    		}

    		if (c == ')') {
    			if (left == 0) {
    				return false;
    			}
    			left--;
    		}
    	}
    	return left == 0;
    }

    int main() {
    	string s = "(((())))";

    	dfs(s, 0, s.length());
    	int ans = 0;

    	set<string>::iterator it;
    	for (it = se.begin(); it != se.end(); it++) {
    		if (judge(*it, s.length())) {
    			cout << *it << endl;
    			ans++;
    		}
    	}

    	cout << ans << endl;
    	return 0;
    }

题目5

问题描述
　　在数列 a[1], a[2], …, a[n] 中，如果对于下标 i, j, k 满足 0<i<j<k<n+1 且 a[i]<a[j]<a[k]，则称 a[i], a[j], a[k] 为一组递增三元组，a[j]为递增三元组的中心。
　　给定一个数列，请问数列中有多少个元素可能是递增三元组的中心。
输入格式
　　输入的第一行包含一个整数 n。
　　第二行包含 n 个整数 a[1], a[2], …, a[n]，相邻的整数间用空格分隔，表示给定的数列。
输出格式
　　输出一行包含一个整数，表示答案。
样例输入
5
1 2 5 3 5
样例输出
2
样例说明
　　a[2] 和 a[4] 可能是三元组的中心。

思路：暴力计数
解题代码：

  • java:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    package wiki.zimo.exam2019;

    import java.util.Scanner;
    /**
    * 
    * @author zimo
    *
    */
    public class Demo05 {
    	public static void main(String[] args) {
    		Scanner input = new Scanner(System.in);
    		int n = input.nextInt();
    		int a[] = new int[n];
    		
    		for (int i = 0;i < n;i++) {
    			a[i] = input.nextInt();
    		}
    		
    		int ans = 0;
    		for (int i = 0;i < n;i++) {
    			l:for (int j = i + 1;j < n ;j++) {
    				for (int k = j + 1;k < n;k++) {
    					if (a[i] < a[j] && a[j] < a[k]) {
    						ans++;
    						break l;
    					}
    				}
    			}
    		}
    		System.out.println(ans);
    	}
    }

  • c++:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    #include <iostream>

    using namespace std;

    int main() {
    	int n = 0;
    	cin >> n;
    	int a[n];

    	for (int i = 0; i < n; i++) {
    		cin >> a[i];
    	}

    	int ans = 0;
    	for (int i = 0; i < n; i++) {
    		for (int j = i + 1; j < n; j++) {
    			bool flag = false;
    			for (int k = j + 1; k < n; k++) {
    				if (a[i] < a[j] && a[j] < a[k]) {
    					ans++;
    					flag = true;
    					break;
    				}
    			}
    			if (flag){
    				break;
    			}
    		}
    	}

    	cout << ans << endl;

    	return 0;
    }

题目6

问题描述
　　在数列 a_1, a_2, …, a_n中，如果 a_i 和 a_j 满足 i < j 且 a_i > a_j，则称为一个逆序数对。
　　给定一个数列，请问数列中总共有多少个逆序数对。
输入格式
　　输入的第一行包含一个整数 n。
　　第二行包含 n 个整数 a_1, a_2, …, a_n，相邻的整数间用空格分隔，表示给定的数列。
输出格式
　　输出一行包含一个整数，表示答案。
样例输入
6
3 1 5 2 3 5
样例输出
4

思路：暴力计数
解题代码：

  • java:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    package wiki.zimo.exam2019;

    import java.util.Scanner;
    /**
    * 
    * @author zimo
    *
    */
    public class Demo06 {
    	public static void main(String[] args) {
    		Scanner input = new Scanner(System.in);
    		int n = input.nextInt();
    		int a[] = new int[n];
    		
    		for (int i = 0;i < n;i++) {
    			a[i] = input.nextInt();
    		}
    		
    		int ans = 0;
    		for (int i = 0;i < n;i++) {
    			for (int j = i + 1;j < n;j++) {
    				if (a[i] > a[j]) {
    					ans++;
    				}
    			}
    		}
    		
    		System.out.println(ans);
    	}
    }

  • c++:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    #include <iostream>

    using namespace std;

    int main() {
    	int n = 0;
    	cin >> n;
    	int a[n];

    	for (int i = 0; i < n; i++) {
    		cin >> a[i];
    	}

    	int ans = 0;
    	for (int i = 0; i < n; i++) {
    		for (int j = i + 1; j < n; j++) {
    			if (a[i] > a[j]) {
    				ans++;
    			}
    		}
    	}

    	cout << ans << endl;

    	return 0;
    }

题目7

问题描述
　　在数列 a_1, a_2, …, a_n中，定义两个元素 a_i 和 a_j 的距离为 |i-j|+|a_i-a_j|，即元素下标的距离加上元素值的差的绝对值，其中 |x| 表示 x 的绝对值。
　　给定一个数列，请问找出元素之间最大的元素距离。
输入格式
　　输入的第一行包含一个整数 n。
　　第二行包含 n 个整数 a_1, a_2, …, a_n，相邻的整数间用空格分隔，表示给定的数列。
输出格式
　　输出一行包含一个整数，表示答案。
样例输入
5
9 4 2 4 7
样例输出
9
样例说明
　　a_1 和 a_3 的距离为 |1-3|+|9-2|=9。

思路：暴力
解题代码：

  • java:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    package wiki.zimo.exam2019;

    import java.util.Scanner;
    /**
    * 
    * @author zimo
    *
    */
    public class Demo07 {
    	public static void main(String[] args) {
    		Scanner input = new Scanner(System.in);
    		int n = input.nextInt();
    		int a[] = new int[n];
    		
    		for (int i = 0;i < n;i++) {
    			a[i] = input.nextInt();
    		}
    		
    		int ans = 0;
    		for (int i = 0;i < n;i++) {
    			for (int j = i + 1;j < n;j++) {
    				int dis = Math.abs(i - j) + Math.abs(a[i] - a[j]);
    				ans = Math.max(dis, ans);
    			}
    		}
    		
    		System.out.println(ans);
    	}
    }

  • c++:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    #include <iostream>
    #include <cmath>

    using namespace std;

    int main() {
    	int n = 0;
    	cin >> n;
    	int a[n];

    	for (int i = 0; i < n; i++) {
    		cin >> a[i];
    	}

    	int ans = 0;
    	for (int i = 0; i < n; i++) {
    		for (int j = i + 1; j < n; j++) {
    			int dis = abs(i - j) + abs(a[i] - a[j]);
    			ans = max(dis, ans);
    		}
    	}

    	cout << ans << endl;

    	return 0;
    }

题目8

问题描述
　　小明有一块空地，他将这块空地划分为 n 行 m 列的小块，每行和每列的长度都为 1。
　　小明选了其中的一些小块空地，种上了草，其他小块仍然保持是空地。
　　这些草长得很快，每个月，草都会向外长出一些，如果一个小块种了草，则它将向自己的上、下、左、右四小块空地扩展，这四小块空地都将变为有草的小块。
　　请告诉小明，k 个月后空地上哪些地方有草。
输入格式
　　输入的第一行包含两个整数 n, m。
　　接下来 n 行，每行包含 m 个字母，表示初始的空地状态，字母之间没有空格。如果为小数点，表示为空地，如果字母为 g，表示种了草。
　　接下来包含一个整数 k。
输出格式
　　输出 n 行，每行包含 m 个字母，表示 k 个月后空地的状态。如果为小数点，表示为空地，如果字母为 g，表示长了草。
样例输入
4 5
.g…
…..
..g..
…..
2
样例输出
gggg.
gggg.
ggggg
.ggg.

思路：按时刻更新空地即可
解题代码：

  • java:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    package wiki.zimo.exam2019;

    import java.util.ArrayList;
    import java.util.List;
    import java.util.Scanner;
    /**
    * 
    * @author zimo
    *
    */
    public class Demo08 {
    	public static void main(String[] args) {
    		Scanner input = new Scanner(System.in);
    		int n = input.nextInt();
    		int m = input.nextInt();
    		// 干掉回车符
    		input.nextLine();
    		
    		char map[][] = new char[n][m];
    		for (int i = 0;i < n;i++) {
    			map[i] = input.nextLine().toCharArray();
    		}
    		
    		int k = input.nextInt();
    		
    		for (int i = 0;i < k;i++) {
    			List<Integer> xs = new ArrayList<Integer>();
    			List<Integer> ys = new ArrayList<Integer>();
    			for (int x = 0;x < n;x++) {
    				for (int y = 0;y < m;y++) {
    					if (map[x][y] == 'g') {
    						xs.add(x);
    						ys.add(y);
    					}
    				}
    			}
    			
    			for (int j = 0;j < xs.size();j++) {
    				dfs(map, xs.get(j), ys.get(j));
    			}
    			xs.clear();
    			ys.clear();
    		}
    		
    		print(map, n, m);
    	}
    	
    	private static void print(char map[][],int n,int m) {
    		for (int i = 0;i < n;i++) {
    			for (int j = 0;j < m;j++) {
    				System.out.print(map[i][j]);
    			}
    			System.out.println();
    		}
    		System.out.println();
    	}

    	private static void dfs(char[][] map,int x,int y) {
    		if (x - 1 >= 0 && map[x - 1][y] == '.') {
    			map[x - 1][y] = 'g';
    		}
    		
    		if (x + 1 < map.length && map[x + 1][y] == '.') {
    			map[x + 1][y] = 'g';
    		}
    		
    		if (y - 1 >= 0 && map[x][y - 1] == '.') {
    			map[x][y - 1] = 'g';
    		}
    		
    		if (y + 1 < map[x].length && map[x][y + 1] == '.') {
    			map[x][y + 1] = 'g';
    		}
    	}
    }

  • c++:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    #include <iostream>
    #include <vector>

    using namespace std;

    #define N 100
    #define M 100

    int n = 0, m = 0;

    void dfs(char map[N][M], int x, int y) {
    	if (x - 1 >= 0 && map[x - 1][y] == '.') {
    		map[x - 1][y] = 'g';
    	}

    	if (x + 1 < n && map[x + 1][y] == '.') {
    		map[x + 1][y] = 'g';
    	}

    	if (y - 1 >= 0 && map[x][y - 1] == '.') {
    		map[x][y - 1] = 'g';
    	}

    	if (y + 1 < m && map[x][y + 1] == '.') {
    		map[x][y + 1] = 'g';
    	}
    }

    void print(char map[N][M]) {
    	for (int i = 0; i < n; i++) {
    		for (int j = 0; j < m; j++) {
    			cout << map[i][j];
    		}
    		cout << endl;
    	}
    	cout << endl;
    }

    int main() {
    	int k = 0;
    	cin >> n >> m;

    	char map[N][M];
    	for (int i = 0; i < n; i++) {
    		for (int j = 0; j < m; j++) {
    			cin >> map[i][j];
    		}
    	}

    	cin >> k;

    	for (int i = 0; i < k; i++) {
    		vector<int> xs;
    		vector<int> ys;
    		for (int x = 0; x < n; x++) {
    			for (int y = 0; y < m; y++) {
    				if (map[x][y] == 'g') {
    					xs.push_back(x);
    					ys.push_back(y);
    				}
    			}
    		}

    		for (int j = 0; j < xs.size(); j++) {
    			dfs(map, xs[j], ys[j]);
    		}
    		xs.clear();
    		ys.clear();
    	}

    	print(map);
    	return 0;
    }

题目9

问题描述
　　小明想知道，满足以下条件的正整数序列的数量：
　　1. 第一项为 n；
　　2. 第二项不超过 n；
　　3. 从第三项开始，每一项小于前两项的差的绝对值。
　　请计算，对于给定的 n，有多少种满足条件的序列。
输入格式
　　输入一行包含一个整数 n。
输出格式
　　输出一个整数，表示答案。答案可能很大，请输出答案除以10000的余数。
样例输入
4
样例输出
7
样例说明
　　以下是满足条件的序列：
　　4 1
　　4 1 1
　　4 1 2
　　4 2
　　4 2 1
　　4 3
　　4 4

思路：改版的斐波那契数列，经典的递归回溯问题，动态规划问题（博主能力有限，动态规划解法没做出来，回溯法可以得部分分）
解题代码：

  • java:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    package wiki.zimo.exam2019;
    import java.util.*;

    /**
    * 
    * @author zimo
    *
    */
    public class Demo09 {
    	static int ans = 0;
    	public static void main(String[] args) {
    		Scanner input = new Scanner(System.in);
    		int n = input.nextInt();

    		if (n <= 1) {
    			System.out.println(1);
    			return;
    		}

    		int a[] = new int[n];

    		a[0] = n; // 第一项是n
    		for (int i = 1;i <= n;i++) {
    			a[1] = i;// 第二项有n种
    			dfs(a,2);// 从第三项开始每一项都跟前两项有关
    		}

    		System.out.println(ans % 10000);
    	}

    	private static void dfs(int a[],int n) {
    //        System.out.println(Arrays.toString(a));
    		print(a);
    		ans++;
    		int abs = Math.abs(a[n - 1] - a[n - 2]);
    		for (int i = 1;i < abs;i++) {
    			a[n] = i;
    			dfs(a,n + 1);
    			for (int j = n;j < a.length;j++) {// 后面置0，上一次递归可能改过第n项以后的值
    				a[j] = 0;
    			}
    		}
    	}
    	
    	private static void print(int a[]) {
    		for (int i = 0;i < a.length;i++) {
    			if (a[i] != 0) {
    				System.out.print(a[i] + " ");
    			}
    		}
    		System.out.println();
    	}
    }

  • c++:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    #include <iostream>
    #include <cstring>

    using namespace std;

    int ans = 0;

    void print(int a[], int len) {
    	for (int i = 0; i < len; i++) {
    		if (a[i] != 0) {
    			cout << a[i] << " ";
    		}
    	}
    	cout << endl;
    }

    void dfs(int a[], int n, int len) {
    //        System.out.println(Arrays.toString(a));
    	print(a, len);
    	ans++;
    	int nabs = abs(a[n - 1] - a[n - 2]);
    	for (int i = 1; i < nabs; i++) {
    		a[n] = i;
    		dfs(a, n + 1, len);
    		for (int j = n; j < len; j++) {// 后面置0，上一次递归可能改过第n项以后的值
    			a[j] = 0;
    		}
    	}
    }

    int main() {
    	int n = 0;
    	cin >> n;
    	if (n <= 1) {
    		cout << 1 << endl;
    		return 0;
    	}

    	int a[n];
    	memset(a, 0, sizeof(int) * n);// 数组初始化0

    	a[0] = n; // 第一项是n
    	for (int i = 1; i <= n; i++) {
    		a[1] = i;// 第二项有n种
    		dfs(a, 2, n);// 从第三项开始每一项都跟前两项有关
    	}

    	cout << ans % 10000 << endl;
    	return 0;
    }

题目10

这个题忘记复制题目了，这个题是贪心算法

解题代码：

  • java:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    package wiki.zimo.exam2019;

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

    /**
    * 
    * @author zimo
    *
    */
    public class Demo10 {
    	public static void main(String[] args) {
    		Scanner input = new Scanner(System.in);
    		int n = input.nextInt();
    		Tree ts[] = new Tree[n];
    		
    		for (int i = 0;i < n;i++) {
    			ts[i] = new Tree();
    			ts[i].x = input.nextInt();
    			ts[i].y = input.nextInt();
    			ts[i].r = input.nextInt();
    		}
    		
    		int ans = 0;
    		HashSet<Tree> set = new HashSet<>();
    		
    		for (int i = 0;i < n;i++) {
    			for (int j = i + 1;j < n;j++) {
    				if (judge(ts[i],ts[j])) {
    					if (ts[i].r > ts[j].r) {
    						set.add(ts[i]);
    					} else {
    						set.add(ts[j]);
    					}
    				} else {
    					set.add(ts[i]);
    					set.add(ts[j]);
    				}
    			}
    		}
    		
    		for (Tree t : set) {
    			ans += t.r;
    		}
    		
    		System.out.println(ans);
    	}
    	
    	private static boolean judge(Tree t1, Tree t2) {
    		double x = t1.x - t2.x;
    		double y = t1.y - t2.y;
    		double dis = Math.sqrt(x * x + y * y);
    		return dis < t1.r + t2.r;
    	}

    	static class Tree{
    		int x;
    		int y;
    		int r;
    		
    		@Override
    		public int hashCode() {
    			final int prime = 31;
    			int result = 1;
    			result = prime * result + r;
    			result = prime * result + x;
    			result = prime * result + y;
    			return result;
    		}

    		@Override
    		public boolean equals(Object obj) {
    			Tree other = (Tree) obj;
    			if (r != other.r)
    				return false;
    			if (x != other.x)
    				return false;
    			if (y != other.y)
    				return false;
    			return true;
    		}

    		@Override
    		public String toString() {
    			return "Tree [x=" + x + ", y=" + y + ", r=" + r + "]";
    		}
    	}
    }

  • c++:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    #include <iostream>
    #include <sstream>
    #include <cmath>
    #include <set>

    using namespace std;

    class Tree {
    public:
    	int x;
    	int y;
    	int r;

    	bool equals(Tree obj) {
    		Tree other = obj;
    		if (r != other.r)
    			return false;
    		if (x != other.x)
    			return false;
    		if (y != other.y)
    			return false;
    		return true;
    	}

    	string toString() {
    		stringstream s1;
    		s1 << "Tree [x=" << x << ", y=" << y << ", r=" << r << "]";
    		return s1.str();
    	}
    };

    struct TreeFunctor {
    	bool operator()(const Tree &left, const Tree &right) {
    		return (left.x < right.x);
    	}
    };

    	bool judge(Tree t1, Tree t2) {
    		double x = t1.x - t2.x;
    		double y = t1.y - t2.y;
    		double dis = sqrt(x * x + y * y);
    		return dis < t1.r + t2.r;
    	}

    	int main() {
    		int n = 0;
    		cin >> n;
    		Tree ts[n];

    		for (int i = 0; i < n; i++) {
    			cin >> ts[i].x >> ts[i].y >> ts[i].r;
    		}

    		int ans = 0;
    		set<Tree,TreeFunctor> se;

    		for (int i = 0; i < n; i++) {
    			for (int j = i + 1; j < n; j++) {
    				if (judge(ts[i], ts[j])) {
    					if (ts[i].r > ts[j].r) {
    						se.insert(ts[i]);
    					} else {
    						se.insert(ts[j]);
    					}
    				} else {
    					se.insert(ts[i]);
    					se.insert(ts[j]);
    				}
    			}
    		}

    		set<Tree,TreeFunctor>::iterator it;
    		for (it = se.begin(); it != se.end(); it++) {
    			ans += (*it).r;
    		}

    		cout << ans << endl;

    		return 0;
    	}
相关文章
觉得不错，打赏一下
0%