2019年第一届全国高校计算机能力挑战赛区域赛
第一套试卷
编程的个人解答源码及思路
1.统计1到N（含）之间所有平方数的个数，并输出这个数目。提示：平方数
的个数，如4是2的平方数，16是4的平方数，5不是平方数。
输入说明：一个整数N（N<100000）。
输出说明：平方数的个数。
输入样例：50
输出样例：7
参考源码：
1. import java.util.Scanner;
2. public class FirstProblemPreliminary {
3. public static void main(String[] args) {
4. Scanner in = new Scanner(System.in);
5. long n=in.nextLong();
6. long count=0;
7. long sqrtRoot=1;
8. while(sqrtRoot*sqrtRoot<=n){
9. count=count+1;
10. sqrtRoot=sqrtRoot+1;
11. }
12. System.out.println(count);
13. }
14. }
算法思路：
模拟算法。
运行截图：
运行实例1（题目上的测试用例）
运行实例2（最大值99999）
运行实例3（最小值1）
运行实例4（负数或者0）
2.统计整数区间[N,M]（N,M<100000）中所有非偶数的合数个数，并输出这个数。输入说明：两个整数N、M；
输出说明：非偶数的合数个数
输入样例：2 16
输出样例：2
参考源码：
1. import java.util.Scanner;
2. public class SecondProblemPreliminary {
3. public static void main(String[] args) {
4. Scanner in = new Scanner(System.in);
5. long N = in.nextLong();
6. long M = in.nextLong();
7. long count = 0;
8. for (long i = N; i <= M; i++) {
9. if (i % 2 == 0) {
10. continue;
11. }
12. count = count + judge(i);
13. }
14. System.out.println(count);
15. }
16.
17. private static long judge(long oneNumber) {
18. long number = 0;
19. for (int i = 2; i <= oneNumber - 1; i++) {
20. if (oneNumber % i == 0) {
21. number = 1;
22. break;
23. }
24. }
25. return number;
26. }
27. }
算法思路：
模拟算法，注意合数的条件。
运行截图：
运行实例1（题目上的测试用例）
运行实例2（1不是素数也不是合数）
3.对于给定的字符数组（字符数少于10000），统计其中字母类型、数字类型和符号类型的字符出现次数，其中字母类型是英文字母a-z之间的字符（不区分大小写）；数字类型是0-9之间的字符；符号类型是除英文字母、数字及空格外的其它字符。
输入说明：一个字符序列；
输出说明：分三行输出：第一行字母类型，以a-z标识；第二行数字类型，以0-9标识；第三行符号类型，以others标识。每行格式如下：
类别标识 出现次数（中间用一个空格分隔）
输入样例：
Hello World!
输出样例：
a-z 10
0-9 0
others 1
参考源码：
1. import java.util.Scanner;
2. public class ThirdProblemPreliminary {
3. public static void main(String[] args) {
4. Scanner in = new Scanner(System.in);
5. String inputStr = in.nextLine();
6. int letterNumber = 0, digitNumber = 0, othersNumber = 0;
7. int length1 = inputStr.length();
8. for (int i = 0; i < length1; i++) {
9. if (inputStr.charAt(i) >= 'a' && inputStr.charAt(i) <= 'z') {
10. letterNumber = letterNumber + 1;
11. continue;
12. }
13. if (inputStr.charAt(i) >= 'A' && inputStr.charAt(i) <= 'Z') {
14. letterNumber = letterNumber + 1;
15. continue;
16. }
17. if (inputStr.charAt(i) >= '0' && inputStr.charAt(i) <= '9') {
18. digitNumber = digitNumber + 1;
19. continue;
20. }
21. if (inputStr.charAt(i) == ' ') {
22. continue;
23. }
24. othersNumber = othersNumber + 1;
25. }
26. System.out.println("a-z " + letterNumber);
27. System.out.println("0-9 " + digitNumber);
28. System.out.println("others " + othersNumber);
29. }
30. }
算法思路：
模拟算法。
运行截图：
运行实例1（题目测试用例）
运行实例2（全是数字）
运行实例3（全是字母）
4.由N（N<=10000）个整数组成的数组，其中连续K（K<=200）个元素构成一个区间，称为K区间。一个K区间中任意两个数求其差值的绝对值，其中最大的绝对值记为Dk。请计算整个数组中，所有K区间中的最大Dk值，并输出。输入说明：第一行是两个整数N和K，第二行输入N个数，表示数组中的元素。输出说明：最大Dk值。
输入样例：
8 2
12 23 27 34 35 36 8 45
输出样例：
37
参考源码：
1. import java.util.Arrays;
2. import java.util.Scanner;
3. public class FourthProblemPreliminary {
4. public static void main(String[] args) {
5. Scanner in = new Scanner(System.in);
6. String firstLineStr = in.nextLine();
7. int n = Integer.parseInt(firstLineStr.split(" ")[0]);
8. int k = Integer.parseInt(firstLineStr.split(" ")[1]);
9. int[] data = new int[n];
10. int[] tempData=new int[k];
11. for (int i = 0; i < n; i++) {
12. data[i] = in.nextInt();
13. }
14. int fromIndex = 0;
15. int maxValue = Integer.MIN_VALUE;
16. while (true) {
17. int endIndex = fromIndex + k;
18. if (endIndex > n) {
19. break;
20. }
21. tempData=Arrays.copyOfRange(data,fromIndex,endIndex);
22. Arrays.sort(tempData);
23. int diffValue = tempData[tempData.length-1] - tempData[0];
24. if (diffValue > maxValue) {
25. maxValue = diffValue;
26. }
27. fromIndex=fromIndex+1;
28. }
29. System.out.println(maxValue);
30. }
31. }
算法思路：
对原始数组依次截取K个元素构成新数组，进行排序，求最大值-最小值（数组的最后一个元素-数组的第一个元素），然后进行循环比较，可求出Dk。注意各种参数的边界条件。
运行截图：
运行实例1（题目测试用例1）
运行实例2（k=1）
运行实例3
5.给定一个只包含0-9、'+'、'*'的合法数学表达式（长度<1000），规定加号'+'的优先级高于乘号'*'，请输出计算结果。
输入说明：合法的数学表达式
输出说明