20200227奇安信模拟笔试

选择题

1、有 ABCDEF 六个城市，每一个城市都和其他所有城市直接相连，问从 A — B 有（）种连接方式，路径不允许在两个城市之间往返。

解：简单的排列计算。
A - B：1种。
A - ? - B：4种。
A - ? - ? - B： = 12种。
A - ? - ? - ? - B： = 24种。
A - ? - ? - ? - ? - B： = 24种。
一共是：1+4+12+24+24 = 65种。

2、在如下8*6的矩阵中，请计算从A移动到B一共有（）种走法，要求每次只能向上或向右移动一格，并且不能通过P。

解：因为只能向上或者向右移动，A向上走5步，再向右走7步到B，共12步，路径总方案数： = 792种。又因为不能经过P，所以要减去经过P的路径：A->P：，P->B：， = 300种，792 - 300 = 492 种。

3、众里寻他千百度，蓦然回首，那人却在灯火阑珊处。——辛弃疾《青玉案》描述的是（回溯）。

解：回溯算法是一种试探法，基本思路是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。这正符合辛弃疾《青玉案》的笔意。

4、使用KMP算法在文本串S中找模式串P是一种常见的方法。假设S=P={xyxyyxxyx}，亦即将S对自己进行匹配，匹配过程中正确的next数组是（）。

解：按照常规做法，先找出每个子串[0, i]的最长公共前后缀长度：
x y x y y x x y x
0 0 1 2 0 1 1 2 3
把上面的序列整体向右移动一个单位，首个位置补-1，即求得next数组：（一般在程序中这样写比较方便，因为数组是从下标0开始计算的，若数组下标从1开始，就需要数组中每个元素都加1）
x y x y y x x y x
-1 0 0 1 2 0 1 1 2
把next数组中每个元素都加1，即得答案：每个i位置表示的是子串[0,i-1]中最长公共前后缀长度+1处的位置！
x y x y y x x y x
0 1 1 2 3 1 2 2 3

5、假设某段通信电文仅由 6 个字母 ABCDEF 组成，字母在电文中出现的频率分别为2，3，7，15，4，6。根据这些频率作为权值构造哈夫曼编码，最终构造出的哈夫曼树带权路径长度与字母 B 的哈夫曼编码分别为______。（这里假定左节点的值小于右节点的值）

解：首先构造一棵哈夫曼树（思路：每次把权值最小的两棵二叉树合并），然后进行哈夫曼编码（目的：为了使得存储空间最小，同时没有二义性的前缀码），便有下面这张图。通过计算可得最终构造出的哈夫曼树带权路径长度：15 + 4 × 3 + 2 × 4 + 3 × 4 + 6 × 3 + 7 × 3 = 15 + 12 + 8 + 12 + 18 + 21 = 86，字母 B 的哈夫曼编码为1011。

6、常用于函数调用的数据结构是（栈）。
7、cookie附带于http请求中，cookie有大小限制，用户可以主动禁止cookie，https协议下cookie是加密传输的。
8、程序的完整编译过程分为是：预处理，编译，汇编等，如下关于编译阶段的编译优化的说法中不正确的是（）。
A. 死代码删除指的是编译过程直接抛弃掉被注释的代码；
B. 函数内联可以避免函数调用中压栈和退栈的开销；
C. for循环的循环控制变量通常很适合调度到寄存器访问；
D. 强度削弱是指执行时间较短的指令等价的替代执行时间较长的指令。

解：A。死代码是指永远不会执行到的代码，不是注释，比如if(0){…}，大括号里的就是死代码。

编程题

1、（已AC）【排序子序列】牛牛定义排序子序列为一个数组中一段连续的子序列,并且这段子序列是非递增或者非递减排序的。牛牛有一个长度为n的整数数组A，他现在有一个任务是把数组A分为若干段排序子序列，牛牛想知道他最少可以把这个数组分为几段排序子序列。
如样例所示，牛牛可以把数组A划分为[1,2,3]和[2,2,1]两个排序子序列，至少需要划分为2个排序子序列，所以输出2。
输入描述：

输入的第一行为一个正整数n(1 ≤ n ≤ 10^5)
第二行包括n个整数A_i(1 ≤ A_i ≤ 10^9)，表示数组A的每个数字。

输出描述：

输出一个整数表示牛牛可以将A最少划分为多少段排序子序列

输入

6
1 2 3 2 2 1

输出

2

• 思路：简单模拟。

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr = new int[n];
        int res = 0, pre = 0;
        int flag = 0; // 0表示初始状态， 1 非递增， 2 非递减
        for (int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
            if (i == 0) {
                pre = arr[i];
                continue;
            }
            if (arr[i] >= pre) {
                if (flag == 2) { // 仍为非递减
                    pre = arr[i];
                } else if (flag == 0) { // 初始状态
                    if (arr[i] > pre) {
                        flag = 2; // 标记为非递减
                    }
                    pre = arr[i];
                } else if (flag == 1) { // 上一个状态为非递增
                    if (arr[i] > pre) { // 若 >
                        flag = 0; // 重置为初始状态
                        pre = arr[i];
                        res++;
                    } // 否则 = 不管
                }
            } else { // arr[i] < pre
                if (flag == 1) { // 仍为非递增
                    pre = arr[i];
                } else if (flag == 0) { // 初始状态
                    flag = 1; // 标记为非递增
                    pre = arr[i];
                } else if (flag == 2) { // 上一个状态为非递减
                    flag = 0; // 重置为初始状态
                    pre = arr[i];
                    res++;
                }
            }
        }
        res++;
        System.out.println(res);
    }
}
//4
//1 2 3 1

//6
//1 2 3 2 2 1

2、（已AC）【组队竞赛】牛牛举办了一次编程比赛，参加比赛的有3*n个选手，每个选手都有一个水平值a_i。现在要将这些选手进行组队，一共组成n个队伍，即每个队伍3人。牛牛发现队伍的水平值等于该队伍队员中第二高水平值。
例如:
一个队伍三个队员的水平值分别是3,3,3.那么队伍的水平值是3
一个队伍三个队员的水平值分别是3,2,3.那么队伍的水平值是3
一个队伍三个队员的水平值分别是1,5,2.那么队伍的水平值是2
为了让比赛更有看点,牛牛想安排队伍使所有队伍的水平值总和最大。
如样例所示:
如果牛牛把6个队员划分到两个队伍
如果方案为：
team1:{1,2,5}， team2:{5,5,8}， 这时候水平值总和为7。
而如果方案为：
team1:{2,5,8}， team2:{1,5,5}， 这时候水平值总和为10。
没有比总和为10更大的方案，所以输出10。
输入描述：

输入的第一行为一个正整数n(1 ≤ n ≤ 10^5)
第二行包括3*n个整数a_i(1 ≤ a_i ≤ 10^9)，表示每个参赛选手的水平值。

输出描述：

输出一个整数表示所有队伍的水平值总和最大值。

输入

2
5 2 8 5 1 5

输出

10

• 思路：贪心。先升序排，再从倒数第2个开始往前以间隔2个单位取值相加，直到取完n个数为止。

import java.util.Arrays;
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr = new int[3 * n];
        long res = 0;
        // 挑选出n个数，求其和
        for (int i = 0; i < 3 * n; i++) {
            arr[i] = in.nextInt();
        }
        Arrays.sort(arr);
        int cnt = 0;
        for (int i = 3 * n - 2; i >= 0; i -= 2) {
            res += arr[i];
            cnt++;
            if (cnt == n)
                break;
        }
        System.out.println(res);
    }
}
// 1 2 4 8 16 32 64 128 256

3、（未AC）【训练部队】 小牛牛是牛牛王国的将军，为了训练出精锐的部队，他会对新兵进行训练。部队进入了n个新兵,每个新兵有一个战斗力值和潜力值，当两个新兵进行决斗时，总是战斗力值高的获胜。获胜的新兵的战斗力值就会变成对手的潜力值 + 自己的战斗力值 - 对手的战斗力值。败者将会被淘汰。若两者战斗力值一样，则会同归于尽，双双被淘汰。 小牛牛想知道通过互相决斗之后新兵中战斗力值+潜力值最高的一个可能达到多少，你能帮助小牛牛将军求出来吗？
输入描述：

输入包括n+1行，第一行包括一个整数n(1 ≤ n ≤ 10^5)；
接下来的n行，每行两个整数x和y(1 ≤ x, y ≤ 10^9)，分别表示这个新兵的战斗力值和潜力值。

输出描述：

输出一个整数,表示新兵中战斗力值+潜力值最高的一个能达到多少。

输入

2
1 2
2 1

输出

4

• 思路：数学推导！从部队中挑选出一名战士，显然只能与那些潜力值大于战斗力值的士兵战斗才能获得更高的战斗力，通过比较可以求出符合条件的增量为：sum(b-a)。假设要和其他人战斗的这位士兵的战斗力值为x，潜力值为y。若x < y，因为y-x已加到增量值sum(b-a)中，所以ans = sum(b-a) - (y-x) + x + y = sum(b-a) + 2*x。若x>=y，则ans = sum(b-a) + x + y。于是，我们发现在比较过程中只需要取max(2*x, x+y)，即最终的答案：ans = sum(b-a) + max(2*x, x+y)。

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        long ans = 0, res = 0;
        long a, b;// 注意类型尽量保持一致，否则可能出现错误
        for (int i = 0; i < n; i++) {
            a = in.nextInt();
            b = in.nextInt();
            if (a < b) {
                ans += b - a;
                res = Math.max(res, a + a);
            } else
                res = Math.max(res, a + b);
        }
        System.out.println(ans + res);
    }
}