【蓝桥日记③】2016第七届省赛（软件类）JavaA组✿答案解析

【蓝桥日记③】2016第七届省赛（软件类）JavaA组✿答案解析

官网题库中搜索相应题目

1、煤球数目

考点：找规律，模拟求和

package sevenSession;

/*** 2016第七届  1、煤球数目 ***/
public class test1 {
    public static void main(String[] args) {
        int pre = 1, res = 1;
        for (int i = 2; i <= 100; i++) {
            pre += i;
            res += pre;
        }
        System.out.println(res);
    }
}

答案：171700

---

2、生日蜡烛

考点：暴力枚举

package sevenSession;

/*** 2016第七届  2、生日蜡烛 ***/
public class test2 {
    public static void main(String[] args) {
        int candles = 236, begin = 0;
        for (int j = 1; j <= 100; j++) {
            int k = j, sum = 0;
            while (sum < candles) {
                sum += k;
                k += 1;
            }
            if (sum == candles) {
                begin = j;
                break;
            }
        }
        System.out.println(begin);
    }
}

答案：26

---

3、搭积木

考点：全排列

package sevenSession;

/*** 2016第七届  3、搭积木 ***/
public class test3 {
    static int res;

    public static void main(String[] args) {
        int[] a = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
        res = 0;
        backtrack(a, 0, a.length);

        System.out.println(res);
    }

    static private void backtrack(int[] a, int begin, int end) {
        if (begin == end) {
            if (check(a)) res++;
            return;
        }
        for (int i = begin; i < end; i++) {
            int t = a[i]; a[i] = a[begin]; a[begin] = t;
            backtrack(a, begin + 1, end);
            t = a[i]; a[i] = a[begin]; a[begin] = t;
        }
    }

    static private boolean check(int[] a) {
        if (a[0] > a[1] || a[0] > a[2]) return false;
        if (a[1] > a[3] || a[1] > a[4]) return false;
        if (a[2] > a[4] || a[2] > a[5]) return false;
        if (a[3] > a[6] || a[3] > a[7]) return false;
        if (a[4] > a[7] || a[4] > a[8]) return false;
        if (a[5] > a[8] || a[5] > a[9]) return false;
        return true;
    }
}

答案：768

---

4、分小组

考点：排列组合

package sevenSession;

/*** 2016第七届  4、分小组 ***/
public class test4 {
    public static String remain(int[] a) {
        String s = "";
        for (int i = 0; i < a.length; i++) {
            if (a[i] == 0) s += (char) (i + 'A');
        }
        return s;
    }

    public static void f(String s, int[] a) {
        for (int i = 0; i < a.length; i++) {
            if (a[i] == 1) continue;
            a[i] = 1;
            for (int j = i + 1; j < a.length; j++) {
                if (a[j] == 1) continue;
                a[j] = 1;
                for (int k = j + 1; k < a.length; k++) {
                    if (a[k] == 1) continue;
                    a[k] = 1;
                    if (k == 3)
                        System.out.println(s + " " + (char)(i + 'A') + (char)(j + 'A') + (char)(k + 'A') + " " + remain(a));
                    a[k] = 0;
                }
                a[j] = 0;
            }
            a[i] = 0;
        }
    }

    public static void main(String[] args) {
        int[] a = new int[9];
        a[0] = 1;

        for (int b = 1; b < a.length; b++) {
            a[b] = 1;
            for (int c = b + 1; c < a.length; c++) {
                a[c] = 1;
                String s = "A" + (char) (b + 'A') + (char) (c + 'A');
                f(s, a);
                a[c] = 0;
            }
            a[b] = 0;
        }
    }
}

答案：System.out.println(s + " " + (char)(i + 'A') + (char)(j + 'A') + (char)(k + 'A') + " " + remain(a));

---

5、抽签

考点：排列组合+递归

package sevenSession;

/*** 2016第七届  5、抽签 ***/
public class test5 {
    public static void f(int[] a, int k, int n, String s) {
        if (k == a.length) {
            if (n == 0) System.out.println(s);
            return;
        }

        String s2 = s;
        for (int i = 0; i <= a[k]; i++) {
            f(a, k + 1, n - i, s2);
            s2 += (char) (k + 'A');
        }
    }

    public static void main(String[] args) {
        int[] a = {4, 2, 2, 1, 1, 3};
        f(a, 0, 5, "");
    }
}

答案：f(a, k + 1, n - i, s2);

---

6、寒假作业

考点：排列组合

package sevenSession;

/*** 2016第七届  6、剪邮票 ***/
public class test6 {
    static int res;
    public static void main(String[] args) {
        int[] a = new int[13];
        for (int i = 1; i <= 13; i++) a[i - 1] = i;
        res = 0;
        backtrack(a, 0, 13);

        System.out.println(res);
    }

    static private void backtrack(int[] a, int begin, int end) {
        if (begin == end && check(a)) {
            res++;
            return;
        }
        for (int i = begin; i < end; i++) {
            int t = a[begin]; a[begin] = a[i]; a[i] = t;
            backtrack(a, begin + 1, end);
            t = a[begin]; a[begin] = a[i]; a[i] = t;
        }
    }

    static private boolean check(int[] a) {
        return a[0] + a[1] == a[2] && a[3] - a[4] == a[5] &&
                a[6] * a[7] == a[8] && (a[9] % a[10] == 0 && a[9] / a[10] == a[11]);
    }
}

答案：64

---

7、剪邮票

考点：组合问题+DFS

package sevenSession;

import java.util.ArrayDeque;
import java.util.Queue;

/*** 2016第七届  7、剪邮票 ***/
public class test7 {
    static int res = 0;
    public static void main(String[] args) {
        int[] a = new int[12];

        backtrack(a, 0, 12, 5);
        System.out.println(res);
    }

    static private void backtrack(int[] a, int begin, int end, int k) {
        if (end - begin + 1 < k) return;
        if (k == 0) {
            if(check(a)) res++;
        }
        for (int i = begin; i < end; i++) {
            a[i] = 1;
            backtrack(a, i + 1, end, k - 1);
            a[i] = 0;
        }
    }

    static private boolean check(int[] a) {
        Queue<int[]> queue = new ArrayDeque<>();
        boolean[] mark = new boolean[12];
        for (int i = 0; i < 12; i++) {
            if (a[i] == 1) {
                queue.offer(new int[]{i / 4, i % 4});
                mark[i] = true;
                break;
            }
        }

        if (queue.isEmpty()) return false;
        int cnt = 1;
        int[] dirs = {-1, 0, 1, 0, -1};
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            for (int i = 0; i < 4; i++) {
                int x = cur[0] + dirs[i], y = cur[1] + dirs[i + 1];
                int xy = x * 4 + y;
                if (x < 0 || y < 0 || x >= 3 || y >= 4) continue;
                if (a[xy] == 0 || mark[xy]) continue;
                queue.offer(new int[]{x, y});
                mark[xy] = true;
                cnt++;
            }
        }

        return cnt == 5;
    }
}

答案：116

---

8、取球博弈

考点：博弈+记忆化搜索

package sevenSession;

import java.util.Arrays;
import java.util.Scanner;

/*** 2016第七届  8、取球博弈 ***/
public class test8 {
    static int[] ns = new int[3];
    static char[][][] cache = new char[1000][2][2];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        for (int i = 0; i < 3; i++) ns[i] = sc.nextInt();
        Arrays.sort(ns);
        char[] res = new char[5];
        for (int i = 0; i < 5; i++) {
            int num = sc.nextInt();
            res[i] = f(num, 0, 0);
        }
        sc.close();
        for (char c : res) System.out.print(c + " ");
    }

    private static char f(int num, int me, int you) {
        if (num < ns[0]) {
            if ((me & 1) == 1 && (you & 1) == 0) {
                cache[num][me][you] = '+';
                return '+';
            } else if ((me & 1) == 0 && (you & 1) == 1) {
                cache[num][me][you] = '-';
                return '-';
            } else {
                cache[num][me][you] = '0';
                return '0';
            }
        }

        if (cache[num][me][you] != '\0') return cache[num][me][you];

        boolean fair = false;
        for (int n : ns) {
            if (num >= n) {
                char c = f(num - n, you, (me + n) % 2);
                if (c == '-') {
                    cache[num][me][you] = '+';
                    return '+';
                } else if (c == '0') {
                    fair = true;
                }
            }
        }
        if (fair) {
            cache[num][me][you] = '0';
            return '0';
        }
        cache[num][me][you] = '-';
        return '-';
    }
  
}

---

9、交换瓶子

package sevenSession;
import java.util.Scanner;

/*** 2016第七届  9、交换瓶子 ***/
public class test9 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] ns = new int[n + 1];
        for (int i = 0; i < n; i++) {
            ns[i + 1] = sc.nextInt();
        }
        sc.close();

        int res = 0, i = 1, j = 0;
        while (i <= n) {
            if (i != ns[i]) {
                for (j = i + 1; j <= n; j++) {
                    if (ns[j] == i) break;
                }
                int t = ns[i];
                ns[i] = ns[j];
                ns[j] = t;
                res++;
                continue;
            }
            i++;
        }

        System.out.println(res);
    }
}

---

10、压缩变换

方法一：暴力法（4/8）

package sevenSession;

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

/*** 2016第七届  10、压缩变换 ***/
public class test10 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) nums[i] = sc.nextInt();
        sc.close();

        int[] res = new int[n];
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            if (!map.containsKey(nums[i])) {
                res[i] = -nums[i];
            } else {
                res[i] = getKinds(nums, map.get(nums[i]), i);
            }
            map.put(nums[i], i);
        }

        for (int x : res) System.out.print(x + " ");
    }

    private static int getKinds(int[] nums, int begin, int end) {
        HashSet<Integer> set = new HashSet<Integer>();
        for (int i = begin + 1; i < end; i++) set.add(nums[i]);
        return set.size();
    }

}

方法二：线段树，区间查询（AC）

线段树知识可以参考我的往期总结：高级数据结构（Ⅲ）线段树（Segment Tree）

package sevenSession;

import java.util.HashMap;
import java.util.Scanner;

/*** 2016第七届  10、压缩变换 线段树区间查询 ***/
public class test10_2 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) nums[i] = sc.nextInt();
        sc.close();

        SegmentTree segTree = new SegmentTree();
        int[] res = new int[n];
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            if (!map.containsKey(nums[i])) {
                res[i] = -nums[i];
                segTree.update(i, 1);
            } else {
                res[i] = segTree.query(map.get(nums[i]) + 1, i - 1);
                segTree.update(map.get(nums[i]), 0);
                segTree.update(i, 1);
            }
            map.put(nums[i], i);
        }

        for (int x : res) System.out.print(x + " ");
    }
}

class SegmentTree {
    private static final int N = 100001;

    private TreeNode root;
    class TreeNode {
        TreeNode left, right;
        int cnt;
    }

    public SegmentTree() {
        root = new TreeNode();
    }

    public void update(int index, int val) {
        root = update(root, 0, N, index, val);
    }

    private TreeNode update(TreeNode node, int low, int high, int index, int val) {
        createNode(node);
        if (low == high && low == index) {
            node.cnt = val;
            return node;
        }
        int mid = low + (high - low) / 2;
        if (index >= low && index <= mid) {
            node.left = update(node.left, low, mid, index, val);
        } else {
            node.right = update(node.right, mid + 1, high, index, val);
        }
        node.cnt = node.left.cnt + node.right.cnt;
        return node;
    }

    public int query(int L, int R) {
        return query(root, 0, N, L, R);
    }

    private int query(TreeNode node, int low, int high, int L ,int R) {
        if (low > R || high < L) return 0;
        if (low >= L && high <= R) return node.cnt;
        int mid = low + (high - low) / 2;
        int sumLeft  = query(node.left, low, mid, L, R);
        int sumRight = query(node.right, mid + 1, high, L, R);
        return sumLeft + sumRight;
    }

    private void createNode(TreeNode node) {
        if (node.left == null) node.left = new TreeNode();
        if (node.right == null) node.right = new TreeNode();
    }

}

---

参考：【蓝桥杯JavaA组】2013-2018年试题讲解（附含C语言版）

高级数据结构（Ⅲ）线段树（Segment Tree）

3~7是排列组合题，只要会一个，举一反三。取球博弈，想想还是第一次真正做博弈的题目呢，之前只刷过简单的题，现在用记忆化搜索和递归来进行模拟，很有趣。最后一道题压缩变换又用到了线段树区间求和，算是对前面的学习巩固了下。还是那句话，加油加油ヾ(◍°∇°◍)ﾉﾞ！