第六届省赛(软件类)真题----Java大学A组答案及解析
- 熊怪吃核桃
- 星系炸弹
- 九数分三组
- 循环节长度
- 打印菱形
- 加法变乘法
- 牌型种数
- 移动距离
- 垒骰子
- 灾后重建
一、熊怪吃核桃
森林里有一只熊怪，很爱吃核桃。不过它有个习惯，每次都把找到的核桃分成相等的两份，吃掉一份，留一份。如果不能等分，熊怪就会扔掉一个核桃再分。第二天再继续这个过程，直到最后剩一个核桃了，直接丢掉。 有一天，熊怪发现了1543个核桃，请问，它在吃这些核桃的过程中，一共要丢掉多少个核桃。 请填写该数字（一个整数），不要填写任何多余的内容或说明文字。
答案：5
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18public class Main {
public static void main(String[] args) {
int sum = 1543;
System.out.println(f(sum));
}
private static int f(int sum) {
if (sum == 1) {
return 1;
}
if (sum % 2 == 0) {
return f(sum/2);
} else {
return f(sum - 1)+1;
}
}
}
二、星系炸弹
在X星系的广袤空间中漂浮着许多X星人造“炸弹”，用来作为宇宙中的路标。 每个炸弹都可以设定多少天之后爆炸。 比如：阿尔法炸弹2015年1月1日放置，定时为15天，则它在2015年1月16日爆炸。 有一个贝塔炸弹，2014年11月9日放置，定时为1000天，请你计算它爆炸的准确日期。 请填写该日期，格式为 yyyy-mm-dd 即4位年份2位月份2位日期。比如：2015-02-19 请严格按照格式书写。不能出现其它文字或符号。
答案：2017-08-05
解析：注意细节，是大于12月还是大于等于12月
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
27public class Main {
public static void main(String[] args) {
int y = 2014;
int m = 11;
int d = 9;
int[] mm1 = {0,31,28,31,30,31,30,31,31,30,31,30,31};
for (int i = 1; i <= 1000; i++) {
d+=1;
if (d > mm1[m]) {
d = 1;
m+=1;
if (m > 12) {
m = 1;
y+=1;
if ((y%4 == 0 && y%100 != 0) || y%400 == 0) {
mm1[2] = 29;
} else {
mm1[2] = 28;
}
}
}
}
System.out.printf("%d-%02d-%02d",y,m,d);
}
}
三、九数分三组
1~9的数字可以组成3个3位数，设为：A,B,C, 现在要求满足如下关系： B = 2 * A C = 3 * A
请你写出A的所有可能答案，数字间用空格分开，数字按升序排列。 注意：只提交A的值，严格按照格式要求输出。
答案： 192 219 273 327
解析：没有267这个答案，题目中要求1-9，而非0-9,注意！！！
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
27import java.util.HashSet;
import java.util.Set;
public class Main {
static Set set = new HashSet<>();
public static void main(String[] args) {
for (int a = 135; a < 333; a++) {
f(a);
f(2*a);
f(3*a);
if (set.size() == 9 && !set.contains(0)) {
System.out.println(a);
}
set.clear();
}
}
private static void f(int a) {
int x = a%10;
int y = a/10%10;
int z = a/100;
set.add(x);
set.add(y);
set.add(z);
}
}
四、循环节长度
两个整数做除法，有时会产生循环小数，其循环部分称为：循环节。
比如，11/13=6=>0.846153846153..... 其循环节为[846153] 共有6位。
下面的方法，可以求出循环节的长度。
请仔细阅读代码，并填写划线部分缺少的代码。
1
2
3
4
5
6
7
8
9
10
11
12
13
14public static int f(int n, int m)
{
n = n % m;
Vector v = new Vector();
for(;;)
{
v.add(n);
n *= 10;
n = n % m;
if(n==0) return 0;
if(v.indexOf(n)>=0) _________________________________ ; //填空
}
}
注意，只能填写缺少的部分，不要重复抄写已有代码。不要填写任何多余的文字。
答案：return v.size() - v.indexOf(n)
五、打印菱形
给出菱形的边长，在控制台上打印出一个菱形来。 为了便于比对空格，我们把空格用句点代替。 当边长为8时，菱形为：
下面的程序实现了这个功能，但想法有点奇怪。
请仔细分析代码，并填写划线部分缺失的代码。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25public class A
{
public static void f(int n)
{
String s = "*";
for(int i=0; i<2*n-3; i++) s += ".";
s += "*";
String s1 = s + "\n";
String s2 = "";
for(int i=0; i<n-1; i++){
//System.out.println("=>"+s);
s = "." + _____________________________________ + "*"; //填空
s1 = s + "\n" + s1;
s2 += s + "\n";
}
System.out.println(s1+s2);
}
public static void main(String[] args)
{
f(8);
}
}
注意，只能填写缺少的部分，不要重复抄写已有代码。不要填写任何多余的文字。
答案：s.substring(0, s.length()-3) 解析：s是"............."，每次从左边截取"....."，除去需要拼接一个"."和一个""整体个数还要-1，所以一共是减三
六、加法变乘法
我们都知道：1+2+3+ ... + 49 = 1225 现在要求你把其中两个不相邻的加号变成乘号，使得结果为2015
比如：
1+2+3+...+1011+12+...+2728+29+...+49 = 2015
就是符合要求的答案。
请你寻找另外一个可能的答案，并把位置靠前的那个乘号左边的数字提交（对于示例，就是提交10）。
注意：需要你提交的是一个整数，不要填写任何多余的内容。
答案：16
1
2
3
4
5
6
7
8
9
10
11
12public class Main
{
public static void main(String[] args) {
for (int i = 1; i < 49; i++) {
for (int j = 1; j < 49; j++) {
if (i*(i+1) + j*(j+1) -(2*i+2*j+2)== 2015-1225) {
System.out.println(i);
}
}
}
}
}
七、牌型种数
小明被劫持到X赌城，被迫与其他3人玩牌。 一副扑克牌（去掉大小王牌，共52张），均匀发给4个人，每个人13张。 这时，小明脑子里突然冒出一个问题： 如果不考虑花色，只考虑点数，也不考虑自己得到的牌的先后顺序，自己手里能拿到的初始牌型组合一共有多少种呢？ 请填写该整数，不要填写任何多余的内容或说明文字。
答案：3598180
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
27public class Main {
static int[] books = new int[5];
static int sum = 0;
static int ans = 0;
public static void main(String[] args) {
dfs(1);
System.out.println(ans);
}
private static void dfs(int u) {
if (sum > 13) {
return;
}
if (u > 13) {
if (sum == 13) {
ans++;
return;
}
} else {
for (int i = 0; i < 5; i++) {
sum += i;
dfs(u+1);
sum -= i;
}
}
}
}
八、移动距离
X星球居民小区的楼房全是一样的，并且按矩阵样式排列。其楼房的编号为1,2,3... 当排满一行时，从下一行相邻的楼往反方向排号。 比如：当小区排号宽度为6时，开始情形如下： 1 2 3 4 5 6 12 11 10 9 8 7 13 14 15 ..... 我们的问题是：已知了两个楼号m和n，需要求出它们之间的最短移动距离（不能斜线方向移动）
输入为3个整数w m n，空格分开，都在1到10000范围内 w为排号宽度，m,n为待计算的楼号。 要求输出一个整数，表示m n 两楼间最短移动距离。
例如： 用户输入： 6 8 2 则，程序应该输出： 4
再例如： 用户输入： 4 7 20 则，程序应该输出： 5
资源约定： 峰值内存消耗（含虚拟机） < 256M CPU消耗 < 1000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
注意：不要使用package语句。不要使用jdk1.7及以上版本的特性。
注意：主类的名字必须是：Main，否则按无效代码处理。
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
27import java.util.Scanner;
public class Main {
static int n, a, b;
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
n = input.nextInt();
a = input.nextInt();
b = input.nextInt();
int c = f1(a);
int d = f1(b);
System.out.println(Math.abs(d+f2(b, d)-c-f2(a, c)));
}
private static int f1 (int i) {
if (i%n == 0) {
return i/n;
}
return i/n+1;
}
private static int f2 (int i, int e) {
if (e % 2 == 0) {
return e*n-i+1;
} else {
return i - (e-1)*n;
}
}
}
九、垒骰子
赌圣atm晚年迷恋上了垒骰子，就是把骰子一个垒在另一个上边，不能歪歪扭扭，要垒成方柱体。 经过长期观察，atm 发现了稳定骰子的奥秘：有些数字的面贴着会互相排斥！ 我们先来规范一下骰子：1 的对面是 4，2 的对面是 5，3 的对面是 6。 假设有 m 组互斥现象，每组中的那两个数字的面紧贴在一起，骰子就不能稳定的垒起来。 atm想计算一下有多少种不同的可能的垒骰子方式。 两种垒骰子方式相同，当且仅当这两种方式中对应高度的骰子的对应数字的朝向都相同。 由于方案数可能过多，请输出模 10^9 + 7 的结果。 不要小看了 atm 的骰子数量哦～
「输入格式」 第一行两个整数 n m n表示骰子数目 接下来 m 行，每行两个整数 a b ，表示 a 和 b 不能紧贴在一起。
「输出格式」 一行一个数，表示答案模 10^9 + 7 的结果。
「样例输入」 2 1 1 2
「样例输出」 544
「数据范围」 对于 30% 的数据：n <= 5 对于 60% 的数据：n <= 100 对于 100% 的数据：0 < n <= 10^9, m <= 36
资源约定： 峰值内存消耗（含虚拟机） < 256M CPU消耗 < 2000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
注意：不要使用package语句。不要使用jdk1.7及以上版本的特性。
注意：主类的名字必须是：Main，否则按无效代码处理。
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
81import java.util.Scanner;
public class Main2 {
static final double MOD = 10e9-7;
static int[][] arr = new int[6][6];
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int n = input.nextInt();
int m = input.nextInt();
/**
* 初始化arr数组
* */
for (int i = 0; i < 6; i++) {
for (int j = 0; j < 6; j++) {
arr[i][j] = 1;
}
}
for (int i = 0; i < m; i++) {
int a = input.nextInt();
int b = input.nextInt();
arr[a-1][b-1] = 0;
arr[b-1][a-1] = 0;
}
/**
*
* */
int[][] ans = pow(arr, n-1);
int sum = 0;
for (int i = 0; i < 6; i++) {
for (int j = 0; j < 6; j++) {
sum += ans[i][j]%MOD;
}
}
/**
* 旋转情况 4^n
* */
sum *= Math.pow(4, n)%MOD;
System.out.println((int)(sum%MOD));
}
private static int[][] pow(int[][] arr, int k) {
/**
* 单位矩阵
* */
int[][] ans = new int[6][6];
for (int i = 0; i < 6; i++) {
ans[i][i] = 1;
}
/**
* 矩阵快速幂核心算法
* */
while (k != 0) {
if (k % 2 != 0) {
ans = Multiply(arr, ans);
}
/**
* 每次算多加一颗骰子，这样算比单纯n次相乘要快
* */
arr = Multiply(arr, arr);
k >>= 1;
}
return ans;
}
private static int[][] Multiply(int[][] m, int[][] n) {
// 标准计算矩阵乘法算法
int rows = m.length;
int cols = n[0].length;
int[][] r = new int[rows][cols];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
for (int k = 0; k < m[i].length; k++) {
r[i][j] += (m[i][k] * n[k][j])%MOD;
}
}
}
return r;
}
}
十、灾后重建
Pear市一共有N（<=50000）个居民点，居民点之间有M（<=200000）条双向道路相连。这些居民点两两之间都可以通过双向道路到达。这种情况一直持续到最近，一次严重的地震毁坏了全部M条道路。 震后，Pear打算修复其中一些道路，修理第i条道路需要Pi的时间。不过，Pear并不打算让全部的点连通，而是选择一些标号特殊的点让他们连通。 Pear有Q（<=50000）次询问，每次询问，他会选择所有编号在[l,r]之间，并且 编号 mod K = C 的点，修理一些路使得它们连通。由于所有道路的修理可以同时开工，所以完成修理的时间取决于花费时间最长的一条路，即涉及到的道路中Pi的最大值。 你能帮助Pear计算出每次询问时需要花费的最少时间么？这里询问是独立的，也就是上一个询问里的修理计划并没有付诸行动。
【输入格式】 第一行三个正整数N、M、Q，含义如题面所述。 接下来M行，每行三个正整数Xi、Yi、Pi，表示一条连接Xi和Yi的双向道路，修复需要Pi的时间。可能有自环，可能有重边。1<=Pi<=1000000。
接下来Q行，每行四个正整数Li、Ri、Ki、Ci，表示这次询问的点是[Li,Ri]区间中所有编号Mod Ki=Ci的点。保证参与询问的点至少有两个。
【输出格式】 输出Q行，每行一个正整数表示对应询问的答案。
【样例输入】 7 10 4 1 3 10 2 6 9 4 1 5 3 7 4 3 6 9 1 5 8 2 7 4 3 2 10 1 7 6 7 6 9 1 7 1 0 1 7 3 1 2 5 1 0 3 7 2 1
【样例输出】 9 6 8 8
【数据范围】 对于20%的数据，N,M,Q<=30 对于40%的数据，N,M,Q<=2000 对于100%的数据，N<=50000,M<=2*10^5,Q<=50000. Pi<=10^6. Li,Ri,Ki均在[1,N]范围内，Ci在[0,对应询问的Ki)范围内。
资源约定： 峰值内存消耗（含虚拟机） < 256M CPU消耗 < 5000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。 所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。 注意：不要使用package语句。不要使用jdk1.7及以上版本的特性。 注意：主类的名字必须是：Main，否则按无效代码处理。
解析：不会做，再网上找了好久才找到这个答案，虽然代码量非常多，用到了太多的算法，但确实没找到合适的答案，暂时先贴上，希望有人能够出更简洁的代码！！！
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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135import java.util.ArrayList;
import java.util.Scanner;
public class Main {
//使用Prim算法，获取输入图的最小生成树
public int[][] getPrim(int[][] value) {
int[][] result = new int[value.length][value[0].length]; //存放最终最小生成树的边权值
int[] used = new int[value.length]; //用于判断顶点是否被遍历
for(int i = 1, len = value.length;i < len;i++)
used[i] = -1; //初始化，所有顶点均未被遍历
used[1] = 1; //从顶点1开始遍历，表示顶点已经被遍历
int count = 1; //记录已经完成构造最小生成树的顶点
int len = value.length;
while(count < len) { //当已经遍历的顶点个数达到图的顶点个数len时，退出循环
int tempMax = Integer.MAX_VALUE;
int tempi = 0;
int tempj = 0;
for(int i = 1;i < len;i++) { //用于遍历已经构造的顶点
if(used[i] == -1)
continue;
for(int j = 1;j < len;j++) { //用于遍历未构造的顶点
if(used[j] == -1) {
if(value[i][j] != 0 && tempMax > value[i][j]) {
tempMax = value[i][j];
tempi = i;
tempj = j;
}
}
}
}
result[tempi][tempj] = tempMax;
result[tempj][tempi] = tempMax;
used[tempj] = 1;
count++;
}
return result;
}
//使用floyd算法获取所有顶点之间的最短路径的具体路径
public void floyd(int[][] primTree, int[][] path) {
int[][] tree = new int[primTree.length][primTree.length];
for(int i = 1;i < primTree.length;i++)
for(int j = 1;j < primTree.length;j++)
tree[i][j] = primTree[i][j];
for(int k = 1;k < primTree.length;k++) {
for(int i = 1;i < primTree.length;i++) {
for(int j = 1;j < primTree[0].length;j++) {
if(tree[i][k] != 0 && tree[k][j] != 0) {
int temp = tree[i][k] + tree[k][j];
if(tree[i][j] == 0) {
tree[i][j] = temp;
path[i][j] = k; //存放顶点i到顶点j之间的路径节点
}
}
}
}
}
}
//返回a与b之间的最大值
public int max(int a, int b) {
return a > b ? a : b;
}
//根据最短路径，返回顶点start~end之间的最大权值边
public int dfsMax(int[][] primTree, int[][] path, int start, int end) {
if(path[start][end] == 0)
return primTree[start][end];
int mid = path[start][end]; //start和end的中间顶点
return max(dfsMax(primTree, path, start, mid), dfsMax(primTree, path, mid, end));
}
//根据最小生成树，返回各个顶点到其它顶点行走过程中，权值最大的一条边
public int[][] getMaxValue(int[][] primTree) {
int[][] path = new int[primTree.length][primTree[0].length];
floyd(primTree, path); //获取具体最短路径
int[][] result = new int[primTree.length][primTree[0].length];
for(int i = 1;i < primTree.length;i++) {
for(int j = 1;j < primTree.length;j++) {
if(j == i)
continue;
int max = dfsMax(primTree, path, i, j);
result[i][j] = max;
}
}
return result;
}
//打印出题意结果
public void printResult(int[][] value, int[][] result) {
int[][] primTree = getPrim(value); //获取输入图的最小生成树
int[][] maxResult = getMaxValue(primTree); //获取各个顶点到其它顶点最短路径中最大权值边
for(int i = 0;i < result.length;i++) {
int L = result[i][0];
int R = result[i][1];
int K = result[i][2];
int C = result[i][3];
ArrayList<Integer> list = new ArrayList<Integer>();
for(int j = L;j <= R;j++) {
if(j % K == C)
list.add(j);
}
int max = 0;
for(int j = 0;j < list.size();j++) {
for(int k = j + 1;k < list.size();k++) {
if(max < maxResult[list.get(j)][list.get(k)])
max = maxResult[list.get(j)][list.get(k)];
}
}
System.out.println(max);
}
return;
}
public static void main(String[] args) {
Main test = new Main();
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int M = in.nextInt();
int Q = in.nextInt();
int[][] value = new int[N + 1][N + 1];
for(int i = 1;i <= M;i++) {
int a = in.nextInt();
int b = in.nextInt();
int tempV = in.nextInt();
value[a][b] = tempV;
value[b][a] = tempV;
}
int[][] result = new int[Q][4];
for(int i = 0;i < Q;i++) {
result[i][0] = in.nextInt();
result[i][1] = in.nextInt();
result[i][2] = in.nextInt();
result[i][3] = in.nextInt();
}
test.printResult(value, result);
}
}