【2014年蓝桥杯Java-B组省赛题解】_14届蓝桥杯javab组

一、武功秘籍（模拟）

标题：武功秘籍

    小明到X山洞探险，捡到一本有破损的武功秘籍（2000多页！当然是伪造的）。他注意到：书的第10页和第11页在同一张纸上，但第11页和第12页不在同一张纸上。

    小明只想练习该书的第81页到第92页的武功，又不想带着整本书。请问他至少要撕下多少张纸带走？

这是个整数，请通过浏览器提交该数字，不要填写任何多余的内容。
1
2
3
4
5
6
7

10|11 12|13 14|15 … 80|81 82|83 …90|91 92|93，注意书页的格式即可。
答案：7

二、切面条（找规律）

标题：切面条

    一根高筋拉面，中间切一刀，可以得到2根面条。

    如果先对折1次，中间切一刀，可以得到3根面条。

    如果连续对折2次，中间切一刀，可以得到5根面条。

    那么，连续对折10次，中间切一刀，会得到多少面条呢？

答案是个整数，请通过浏览器提交答案。不要填写任何多余的内容。
1
2
3
4
5
6
7
8
9
10
11

找规律：2^n + 1
答案：1025

三、猜字母（模拟）

标题：猜字母

    把abcd...s共19个字母组成的序列重复拼接106次，得到长度为2014的串。

    接下来删除第1个字母（即开头的字母a），以及第3个，第5个等所有奇数位置的字母。

    得到的新串再进行删除奇数位置字母的动作。如此下去，最后只剩下一个字母，请写出该字母。

答案是一个小写字母，请通过浏览器提交答案。不要填写任何多余的内容。
1
2
3
4
5
6
7
8
9

直接模拟就可以，删除的字母用vis数组标记为1。

public class Main {
    public static void main(String[] args) {
        int[] nums = new int[2015];
        int index = 0;
        for (int i = 1; i <= 106; i++) {
            for (int j = 1; j <= 19; j++) {
                nums[index++] = j;
            }
        }
        // index = 2014
        int[] vis = new int[2015];
        while (index != 1) {
            int tmp = 0;
            for (int i = 0; i < 2014; i++) {
                // 每个被删除的数都标记为1，只看没有删除的数（=0）
                if (vis[i] == 0) {
                    tmp++;
                    if (tmp % 2 == 1) {
                        vis[i] = 1;
                        index--;
                    }
                }
            }
        }
        for (int i = 0; i < 2014; i++) {
            if (vis[i] == 0) {
                System.out.println(nums[i]);
            }
        }
    }
}
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

答案：q

四、五、为程序填空题

六、奇怪的分式（模拟）

标题：奇怪的分式

    上小学的时候，小明经常自己发明新算法。一次，老师出的题目是：

    1/4 乘以 8/5 

    小明居然把分子拼接在一起，分母拼接在一起，答案是：18/45 （参见图1.png）

    老师刚想批评他，转念一想，这个答案凑巧也对啊，真是见鬼！

    对于分子、分母都是 1~9 中的一位数的情况，还有哪些算式可以这样计算呢？

    请写出所有不同算式的个数（包括题中举例的）。

    显然，交换分子分母后，例如：4/1 乘以 5/8 是满足要求的，这算做不同的算式。

    但对于分子分母相同的情况，2/2 乘以 3/3 这样的类型太多了，不在计数之列!

注意：答案是个整数（考虑对称性，肯定是偶数）。请通过浏览器提交。不要书写多余的内容。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

注意题目中只要求一个分数的分子分母不同，对两个分数的分子分母是没有要求的！并且允许交换分子分母，这也算是不同的算式。直接按照题目意思模拟即可，注意用最大公约数gcd来给分数化简，比较最简形式。

public class Main {
    // 求最大公约数用来约分
    static int gcd (int a, int b) {
        if (b == 0) {
            return a;
        } else {
            return gcd(b, a % b);
        }
    }
    public static void main(String[] args) {
        // 分子分母都是1-9的一位数
        // 分子分母不能相同
        int ans = 0;
        for (int i = 1; i <= 9; i++) {
            for (int j = 1; j <= 9; j++) {
                if (j == i) {
                    continue;
                }
                for (int k = 1; k <= 9; k++) {
                    for (int l = 1; l <= 9; l++) {
                        if (l == k) {
                            continue;
                        }
                        // i j k l分别模拟两个分式的分子分母
                        int a1 = i * 10 + k;
                        int a2 = j * 10 + l;
                        int tmp1 = gcd(a1, a2);
                        a1 = a1 / tmp1;
                        a2 = a2 / tmp1;
                        int b1 = i * k;
                        int b2 = j * l;
                        int tmp2 = gcd(b1, b2);
                        b1 = b1 / tmp2;
                        b2 = b2 / tmp2;
                        if (a1 == b1 && a2 == b2) {
                            ans++;
                            System.out.println(a1 + "/" + a2);
                        }
                    }
                }
            }
        }
        System.out.println(ans);
    }
}
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

答案：14

七、扑克排序（贪心）

标题：扑克序列

    A A 2 2 3 3 4 4， 一共4对扑克牌。请你把它们排成一行。
    要求：两个A中间有1张牌，两个2之间有2张牌，两个3之间有3张牌，两个4之间有4张牌。

    请填写出所有符合要求的排列中，字典序最小的那个。

例如：22AA3344 比 A2A23344 字典序小。当然，它们都不是满足要求的答案。


请通过浏览器提交答案。“A”一定不要用小写字母a，也不要用“1”代替。字符间一定不要留空格。
1
2
3
4
5
6
7
8
9
10
11

先放字典序最小的，并且要满足题目要求，依次放数。
答案：2342A3A4

八、分糖果（模拟）

注意题目中坐成一圈！！，第一个小朋友的左边就是最后一个小朋友，先记录要分的糖果数，分完了再加到他们自己身上，而不是边加边分。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = scan.nextInt();
        }
        int ans = 0;
        while (true) {
            int[] cnt = new int[n];
            int index = 0;
            for (int i = 0; i < n; i++) {
                cnt[index++] = nums[i] / 2;
                nums[i] = nums[i] / 2;
            }
            for (int i = 0; i < index; i++) {
                if (i == 0) {
                    nums[n - 1] += cnt[i];
                } else {
                    nums[i - 1] += cnt[i];
                }
            }
            for (int i = 0; i < n; i++) {
                if (nums[i] % 2 == 1) {
                    nums[i]++;
                    ans++;
                }
            }
            int tmp = nums[0];
            int i;
            for (i = 1; i < n; i++) {
                if (tmp != nums[i]) {
                    break;
                }
            }
            if (i == n) {
                System.out.println(ans);
                break;
            }
        }
    }
}
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

九、地宫取宝（DFS搜搜）

自己只想到了DFS，提交只有42分，后面几个例子超时，正解是记忆化搜索：DFS+DP。

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

public class Main {
    static int ans = 0;
    // 只能向右、向下
    static int[] xx = {0, 1};
    static int[] yy = {1, 0};
    static int[][] vis = new int[51][51];
    static LinkedList<Integer> price = new LinkedList<>();
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int m = scan.nextInt();
        int k = scan.nextInt();
        int[][] map = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                map[i][j] = scan.nextInt();
            }
        }
        price.add(map[0][0]);
        vis[0][0] = 1;
        dfs (map, k, 0, 0);
        price = new LinkedList<>();
        vis = new int[51][51];
        dfs (map, k, 0, 0);
        System.out.println(ans);
    }
    static void dfs(int[][] map, int k, int x, int y) {
        int n = map.length;
        int m = map[0].length;
        if (x == n - 1 && y == m - 1 && k == price.size()) {
            ans++;
            ans %= 1000000007;
            return;
        }
        if (k < price.size()) {
            return;
        }
        for (int i = 0; i < 2; i++) {
            int tmpx = x + xx[i];
            int tmpy = y + yy[i];
            if (tmpx >= n || tmpy >= m || vis[tmpx][tmpy] == 1) {
                continue;
            }
            int flag = 1;
            for (int j = 0; j < price.size(); j++) {
                if (map[tmpx][tmpy] <= price.get(j)) {
                    flag = 0;
                    break;
                }
            }
            vis[tmpx][tmpy] = 1;
            if (flag == 1) {
                price.add(map[tmpx][tmpy]);
                dfs(map, k, tmpx, tmpy);
                price.removeLast();
                // 由于每一步在可以拿的时候，可以选择不拿
                // 所以需要分两种情况遍历，两种情况遍历完之后才回溯
                dfs(map, k, tmpx, tmpy);
                // 回溯
                vis[tmpx][tmpy] = 0;
            } else {
                dfs(map, k, tmpx, tmpy);
                // 回溯
                vis[tmpx][tmpy] = 0;
            }
        }
    }
}
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

一定要注意每一步如果可以拿，那么可以选择不拿或者拿，所以要分开搜索，两种情况遍历完后再回溯。

十、※矩阵翻转硬币（数学推理、BigInteger求sqrt）

对每一个硬币进行一次Q操作时，会对所有第 i * x行，第 j * y列的硬币进行翻转，其中i和j为任意操作可行的正整数，行号和列号都是从1开始。

如果矩阵大小为5x6，对于第1行，第1列的硬币进行Q操作，它可以使得(1,1) (1,2) (1,3) … (1,6); （2,1) (2,2) (2,3) … (2,6)；(3,1)…直到最后的(5,6)翻转一次。那么对于第i行，第j列的硬币，会执行多少次翻转？

(1,4)，会因为(1,1)(1,2)(1,4)执行Q操作而翻转，所以就是看4的因子（包括自己）有多少个因子，第i行、第j列硬币，执行的翻转次数 = i的因子数 * j的因子数。如果翻转次数为奇数，说明原先是反面；如果翻转次数为偶数，说明原先是正面（因为执行完所有的Q操作后，都是正面朝上）。

要使得i的因子数 * j的因子数 = 奇数，那么i 和 j都必须是平方数，因为只有平方数的因子数为奇数个，而且只有奇数 * 奇数 = 奇数，奇数 * 偶数 = 偶数，偶数 * 偶数 = 偶数，所以必须保证i 和 j 的因字数都是奇数个，也就要求i 和j 都是平方数。

我们要找到所有反面的硬币数，那么不就是看n , m中分别有多少个平方数，平方数的因子数 * 平方数的因子数 = 奇数（原来的硬币也就是反面）。这里用到的是排列组合的知识，m个平方数 * n个平方数 = mn种可能 = mn个反面硬币。

平方数的个数怎么求？= sqrt(n)，例如1-4，sqrt(4) = 2 = 1、4，所以答案 = sqrt(m) * sqrt(n)。

sqrt(m) * sqrt(n)对于题目中的大部分输入，是超出数据范围的，必须得转换成BigInteger求sqrt，由于BigInteger没有sqrt函数，必须用二分实现，如下。

class Solution {
    public int sqrt(int m) {
        if (m == 0 || m == 1) {
            return 1;
        }
        int left = 0;
        int right = m;
        int mid;
        while (left <= right) {
            mid = left + (right - left) / 2;
            if (mid == m / mid) {
                return mid;
            } else if (mid < m / mid) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left - 1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

知道二分模拟sqrt方法后，只需要把上述的int改成BigInteger即可，最终的代码如下：

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String n = scan.next();
        String m = scan.next();
        // sqrt(n,m)向下取整
        // 答案就是sqrt(n) * sqrt(m)
//        System.out.println((int)Math.sqrt(n) * (int)Math.sqrt(m));
        // 上述答案无法对所有数据规模做出解答
        // 最大数据是10^1000，需要用到Big
        BigInteger left = new BigInteger("0");
        BigInteger right = new BigInteger(n);
        BigInteger right1 = new BigInteger(m);
        System.out.println(search(left, right, new BigInteger(n)).multiply(search(left, right1, new BigInteger(m))));

    }
    static BigInteger search(BigInteger left, BigInteger right, BigInteger n) {
        BigInteger mid;
        // left <= right
        while (left.compareTo(right) == -1 || left.compareTo(right) == 0) {
            // mid = (l+r) / 2
            mid = left.add(right).divide(new BigInteger("2"));
            if (mid.compareTo(n.divide(mid)) == 0) {
                // mid == n / mid; mid * mid == n
                return mid;
            } else if (mid.compareTo(n.divide(mid)) == -1) {
                // mid < n / mid
                left = mid.add(new BigInteger("1"));
            } else {
                // mid > n / mid
                right = mid.subtract(new BigInteger("1"));
            }
        }
        return left.subtract(new BigInteger("1"));
    }
}
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