蓝桥-往届省赛

三体攻击

三体人将对地球发起攻击。为了抵御攻击，地球人派出了 A × B × C 艘战舰，在太空中排成一个 A 层 B 行 C 列的立方体。其中，第 i 层第 j 行第 k 列的战舰（记为战舰 (i, j, k)）的生命值为 d(i, j, k)。

三体人将会对地球发起 m 轮“立方体攻击”，每次攻击会对一个小立方体中的所有战舰都造成相同的伤害。具体地，第 t 轮攻击用 7 个参数 lat, rat, lbt, rbt, lct, rct, ht 描述：所有满足 i ∈ [lat, rat],j ∈ [lbt, rbt],k ∈ [lct, rct] 的战舰 (i, j, k) 会受到 ht 的伤害。如果一个战舰累计受到的总伤害超过其防御力，那么这个战舰会爆炸。地球指挥官希望你能告诉他，第一艘爆炸的战舰是在哪一轮攻击后爆炸的。

输入格式： 从标准输入读入数据。第一行包括 4 个正整数 A, B, C, m；

第二行包含 A × B × C 个整数，其中第 (i − 1) × B × C + (j − 1) × C + k个数为 d(i, j, k)；

第 3 到第 m + 2 行中，第 (t + 2) 行包含 7 个正整数 lat, rat, lbt, rbt, lct, rct, ht。

输出格式： 输出到标准输出。输出第一个爆炸的战舰是在哪一轮攻击后爆炸的。保证一定存在这样的战舰。

样例输入：

2 2 2 3
1 1 1 1 1 1 1 1
1 2 1 2 1 1 1
1 1 1 2 1 2 1
1 1 1 1 1 1 2

样例输出： 2

样例解释： 在第 2 轮攻击后，战舰 (1,1,1) 总共受到了 2 点伤害，超出其防御力导致爆炸。

数据约定： 对于 10% 的数据，B = C = 1； 对于 20% 的数据，C = 1； 对于 40% 的数据，A × B × C, m ≤ 10, 000； 对于 70% 的数据，A, B, C ≤ 200； 对于所有数据，A × B × C ≤ 10^6, m ≤ 10^6, 0 ≤ d(i, j, k), ht ≤ 10^9。

正则问题

考虑一种简单的正则表达式：只由 x、( )、| 组成。求出这个正则表达式能接受的最长字符串的长度。

例如， ((xx|xxx)x|(x|xx))xx 能接受的最长字符串是： xxxxxx，长度是6。

输入：

一个由x、()、 |组成的正则表达式。输入长度不超过100，保证合法。

输出：

这个正则表达式能接受的最长字符串的长度。

输入：

((xx|xxx)x|(x|xx))xx

程序应该输出：

6

---

把正则表达式分为两部分：

• 一部分是原表达式中由括号组成的一个更小的子表达式。
• 另一部分则为原表达式中非括号部分。

例如样例中的((xx|xxx)x|(x|xx))xx这个表达式分为：

• ((xx|xxx)x|(x|xx))即原式括号内的子表达式。当然，这个子表达式中还有更小的子表达式。
• XX即原式中的非括号部分。

我们循环遍历每个字符，计数所能接受的最长字符串的长度，同时，每遇到一个子表达式，我们递归地去求解这个表达式接受的最大长度。也就是说，每层递归中，我们遍历当前子表达式，每个字符有4种可能：

• (，说明即将遇到一个子表达式，递归求解该子表达式的长度，累加到当前结果cur。
• )，递归边界，说明一个子表达式结束，返回结果Math.max(cur, pre)，其中，pre用于记录当前表达式中|符号前面的最大长度。
• |，说明该符号前后两侧均有一个长度，我们要取两者中较大者，因此需要用变量pre记录之前的结果。
• X，增加当前X字符的数量。

最后，指针p遍历完表达式返回结果Math.max(cur, pre)。

---

第七届

8 取球博弈

题目

两个人玩取球的游戏。一共有N个球，每人轮流取球，每次可取集合{n1,n2,n3}中的任何一个数目。如果无法继续取球，则游戏结束。此时，持有奇数个球的一方获胜。如果两人都是奇数，则为平局。假设双方都采用最聪明的取法，第一个取球的人一定能赢吗？试编程解决这个问题。

输入格式：

第一行3个正整数n1 n2 n3，空格分开，表示每次可取的数目 (0<n1,n2,n3<100)
第二行5个正整数x1 x2 … x5，空格分开，表示5局的初始球数(0<xi<1000)

输出格式：

一行5个字符，空格分开。分别表示每局先取球的人能否获胜。能获胜则输出+，次之，如有办法逼平对手，输出0，无论如何都会输，则输出-

例如，输入：

1 2 3
1 2 3 4 5

程序应该输出：

+ 0 + 0 -

再例如，输入：

1 4 5
10 11 12 13 15

程序应该输出：

0 - 0 + +

再例如，输入：

2 3 5
7 8 9 10 11

程序应该输出：

+ 0 0 0 0

再例如，输入：

1 7 8
900 901 903 905 907

程序应该输出：

0 + - - +

资源约定：

峰值内存消耗（含虚拟机） < 256M
CPU消耗 < 3000ms

请严格按要求输出，不要画蛇添足地打印类似：“请您输入…” 的多余内容。所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。注意：不要使用package语句。不要使用jdk1.7及以上版本的特性。注意：主类的名字必须是：Main，否则按无效代码处理。

思路

形如这样的博弈题，我们都可以递归去枚举所有局面然后得出胜负。但本题需要注意的是球数比较多，而可取的球数又可能比较少，这样递归的深度会很大，导致无法通过所有测试样例，因此我们需要使用记忆化递归。

此外，还需要注意到，博弈局面与两方所持球数无关，而与所持球数的奇偶有关，因此我们可以只记录奇偶（1和0）而不记录具体球数。

递归过程中，我们首先去判断是否曾经记录过当前局面，若记录过则直接返回记录的结果，否则枚举所有可取球数的情况（共3种），这里要注意，当前人取球后，便成为下个取球人，而另一个人则在下次递归中成为当前取球人，因此要注意方法中参数的变化。当无法继续取球时，直接根据奇偶判定结果。返回当前局面的胜负之前，要先记录。

其他实现细节请参考代码中的详细注释。

代码

public class Main {
    private static int[] take = new int[3];// 记录可取的球数
    // 三维字符数组map用于记忆化递归
    // 剩余cnt个球时，当前取球人有cur个球，下个取球人有next个球
    // map[cnt][cur][next]记录上局面下当前取球人取球得到的结果
    // 又由于博弈结果只与奇偶有关，因此cur与next不记录具体球数，而用0表示偶数，1表示奇数
    private static Character[][][] map = new Character[1000][2][2];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        for (int i = 0; i < 3; i++)
            take[i] = sc.nextInt();
        Arrays.sort(take);
        for (int i = 0; i < 5; i++)
            System.out.print(play(sc.nextInt(), 0, 0) + " ");
        System.out.println();
    }

    /**
     * 记忆化递归得到博弈结果，由于结果只与奇偶有关，因此参数不记录具体球数
     * @param cnt  剩余球数
     * @param cur  当前取球人球数的奇偶
     * @param next 下个取球人球数的奇偶
     * @return 结果
     */
    private static char play(int cnt, int cur, int next) {
        if (map[cnt][cur][next] != null) // 当前局面曾经记录过则直接返回
            return map[cnt][cur][next];
        if (cnt < take[0]) {// 无法继续取球则直接判定结果
            if ((cur & 1) == 1 && (next & 1) == 0)
                return '+';
            if ((cur & 1) == 0 && (next & 1) == 1)
                return '-';
            return '0';
        }
        boolean tie = false;// 记录是否能平局
        for (int i = 0; i < 3; i++) {
            if (take[i] > cnt)// 不够取
                break;
            // 注意play方法后两个参数的变化
            // 当前取球人取完后，便成为下个取球人，另一个人则成为新的当前取球人
            // 当前取球人取完，下个取球人成为当前取球人去取球
            char res = play(cnt - take[i], next, cur + take[i] & 1);
            if (res == '-') {// 新的取球人输了，说明旧的取球人能赢
                map[cnt][cur][next] = '+';// 记录结果
                return '+';
            }
            if (res == '0') {// 出现过平局
                tie = true;
            }
        }
        if (tie) {// 不能赢，能平则平
            map[cnt][cur][next] = '0';
            return '0';
        }
        map[cnt][cur][next] = '-';
        return '-';
    }
}

10 压缩变换

题目

小明最近在研究压缩算法。他知道，压缩的时候如果能够使得数值很小，就能通过熵编码得到较高的压缩比。然而，要使数值很小是一个挑战。最近，小明需要压缩一些正整数的序列，这些序列的特点是，后面出现的数字很大可能是刚出现过不久的数字。对于这种特殊的序列，小明准备对序列做一个变换来减小数字的值。变换的过程如下： 从左到右枚举序列，每枚举到一个数字，如果这个数字没有出现过，则将数字变换成它的相反数，如果数字出现过，则看它在原序列中最后的一次出现后面（且在当前数前面）出现了几种数字，用这个种类数替换原来的数字。比如，序列(a1, a2, a3, a4, a5)=(1, 2, 2, 1, 2)在变换过程为： a1: 1未出现过，所以a1变为-1； a2: 2未出现过，所以a2变为-2； a3: 2出现过，最后一次为原序列的a2，在a2后、a3前有0种数字，所以a3变为0； a4: 1出现过，最后一次为原序列的a1，在a1后、a4前有1种数字，所以a4变为1； a5: 2出现过，最后一次为原序列的a3，在a3后、a5前有1种数字，所以a5变为1。 现在，给出原序列，请问，按这种变换规则变换后的序列是什么。

输入格式：

输入第一行包含一个整数n，表示序列的长度。
第二行包含n个正整数，表示输入序列。

输出格式：

输出一行，包含n个数，表示变换后的序列。

例如，输入：

5
1 2 2 1 2

程序应该输出：

-1 -2 0 1 1

再例如，输入：

12
1 1 2 3 2 3 1 2 2 2 3 1

程序应该输出：

-1 0 -2 -3 1 1 2 2 0 0 2 2

数据规模与约定：

对于30%的数据，n<=1000； 对于50%的数据，n<=30000； 对于100%的数据，1 <=n<=100000，1<=ai<=10^9

资源约定：

峰值内存消耗（含虚拟机） < 256M
CPU消耗 < 3000ms

思路

题意不难，我们在得到一个重复出现的数字后，需要查询该位置和它上一次出现的位置之间含有的不重复数的个数，暴力求解是会超时的。我们不妨尝试线段树这种适合多次区间查询的数据结构，同时搭配使用哈希表，记录每个数最后一次出现的位置。

接下来的问题在于线段树的结点要维护什么？我们建立一个表示下标0到n-1区间的线段树，每个结点维护一个值，用于表示该区间内有几个不重复数。这样一来，我们遇到一个重复出现的数后，就在线段树中查询对应区间，得到不重复数的个数，作为压缩结果；遇到一个未出现过的数，就用相反数作为压缩结果。我们用哈希表来判断一个数是否出现过，以上就是解题的主要思路。

由于线段树结点中记录的是区间内不重复数的个数，所以我们要在线段树内去重。具体来说，若得到一个未出现过的数，用相反数作为压缩结果后，将其存入哈希表，同时存入线段树，即令树中所有包含它的区间的结点值加一，表示该区间内多了这个不重复数；若得到一个出现过的数，我们查询哈希表得到上一次出现的位置，由此得到一个查询区间，我们要在线段树中查询这个区间内有多少个不重复的数，要注意，我们此后必须更新哈希表，更新线段树（两次）。具体做法：由于线段树维护的是区间中不重复数的个数，而当前数又是重复出现过的，所以我们需要在该数上一次出现的所有区间内删除它，表示这些区间少了这个数，这个数将出现在新的区间中，表示新区间多了这个不重复数（因为之前的区间已做了删除，所以它目前就是不重复数），这一减一增是对线段树的两次更新。

代码

public class Main {
    // 线段树
    static class SegmentTree {
        int L, R;// 所维护的区间的左右端点
        int cnt;// 结点值，即某数最后一次出现的位置是否在此，是则为1，否则为0
        SegmentTree left, right;// 左右子树

        SegmentTree(int l, int r) {
            L = l;
            R = r;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++)
            a[i] = sc.nextInt();
        int[] ans = new int[n];
        Map<Integer, Integer> map = new HashMap<>();// 哈希表记录各数最后一次出现的下标
        SegmentTree root = buildST(0, n - 1);// 线段树维护0至n-1这个下标区间，记录有几个不重复数在此区间内最后一次出现
        for (int i = 0; i < n; i++) {
            if (!map.containsKey(a[i])) {// 第一次出现
                ans[i] = -a[i];
            } else {
                // 得到最后一次出现的位置
                int lastidx = map.get(a[i]);
                // 查询这个区间内有几个不重复数最后一次出现
                // 之所以统计的是最后一次出现的数的个数是为了不重复
                // 所以接下来要将该数上次出现的位置置0，因为现在有新的最后一次出现的位置
                // 若不置0，同样的数会被重复计算，得到的就不是该区间内不重复数的个数
                ans[i] = query(root, lastidx + 1, i - 1);
                update(root, lastidx, -1);
            }
            map.put(a[i], i);// 更新最后一次出现的位置
            update(root, i, 1);// 在新的位置处置1，表示在该区间内最后一次出现，上次出现的位置已置0，防止重复统计
        }
        for (int i : ans)
            System.out.print(i + " ");
    }

    /**
     * 建树
     * @param L 线段树左端点
     * @param R 线段树右端点
     * @return 返回树
     */
    private static SegmentTree buildST(int L, int R) {
        if (L == R)// 到达叶子结点
            return new SegmentTree(L, R);
        SegmentTree root = new SegmentTree(L, R);
        int mid = L + R >> 1;
        // 递归构建左右子树
        root.left = buildST(L, mid);
        root.right = buildST(mid + 1, R);
        return root;
    }

    /**
     * 对结点进行更新，自底向上更新区间
     * @param root 需要更新的子树
     * @param idx  要更新的叶子结点下标
     * @param val  增量
     */
    private static void update(SegmentTree root, int idx, int val) {
        if (root.L == root.R) {// 到达叶子结点
            root.cnt += val;
            return;
        }
        int mid = root.L + root.R >> 1;
        if (idx <= mid)// 需要更新左子树
            update(root.left, idx, val);
        else// 需要更新右子树
            update(root.right, idx, val);
        root.cnt = root.left.cnt + root.right.cnt;// 更新根结点
    }

    /**
     * 区间查询
     * @param root  查询的子树
     * @param begin 查询区间的起点
     * @param end   查询区间的终点
     * @return 结果
     */
    private static int query(SegmentTree root, int begin, int end) {
        if (begin > end) // 可能存在不合法区间，则该区间查询结果为0，表示这没有不重复的数
            return 0;
        if (root.L == begin && root.R == end)// 结点与查询区间吻合，直接返回结点值
            return root.cnt;
        int res = 0;
        int mid = root.L + root.R >> 1;
        if (begin <= mid) {
            if (end <= mid)// 整个区间在左子树
                res = query(root.left, begin, end);
            else// 区间横跨左右子树
                res = query(root.left, begin, mid) + query(root.right, mid + 1, end);
        } else {// 整个区间在右子树
            res = query(root.right, begin, end);
        }
        return res;
    }
}