米哈游8.3秋招笔试

数组价值

米小游有一个长度为 n 的数组，其中第 i 个元素为 ai。现在定义数组的价值是最大的相邻数字的乘积。例如数组为 [3,5,1,2] ，相邻元素的乘积分别是 35=15,51=5和1*2=2 ，则数组的价值是这些数字中的最大值，即 15。

现在米小游想要任选数组中的某两个相邻的元素进行交换（你必须使用这次交换机会），他想知道最大可以将数组的价值更改为多少？

输入描述

第一行输入一个整数 n(2<=n<=10^5) 表示数组的长度。 第二行输入 n 个整数 a1,a2,…..,an (1<=ai<=10^5) 表示数组中的值。

输出描述

在一行上输出一个整数表示答案。

示例 1

输入

1
2
3
3 1 10

输出

1
30

说明

交换 3 和 1 ，则数组变为 [1,3,10] ，此时最大价值为 3*10=30 。交换 1 和 10 也可以达到相同的最大价值。

示例 2

输入

1
2
4
1 2 10 8

输出

80

说明

如果交换 2 和 10 ，则数组的价值会减少。但是由于必须使用交换机会，所以可以交换 1 和 2 ，这样数组的价值仍为 80。

我的思路与代码

模拟。

我还以为得分类，没想到不用，直接遍历数组，

  • i ×(i+1)
  • i ×(i+2)

核心就以上

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
private static void T1() {
        Scanner in = new Scanner(System.in);
        int len = in.nextInt();
//        if (len == 2) {
//            System.out.println(in.nextInt() * in.nextInt());
//        }
//        else if (len == 3) {
//            int one = in.nextInt();
//            int two = in.nextInt();
//            int three = in.nextInt();
//            int a = one * two;
//            int b = two * three;
//            int c = one * three;
//            System.out.println(Math.max(a, Math.max(b, c)));
//        }
//        else if (len == 4) {
//            int one = in.nextInt();
//            int two = in.nextInt();
//            int three = in.nextInt();
//            int four = in.nextInt();
//            int a = one * two;
//            int end = three * four;
////            ======
////            int b = two * three;
//            int c = one * three;
//            int d = two * four;
//            System.out.println(Math.max(a, Math.max(end, Math.max(c, d))));
//        }

//        else {
        long[] nums = new long[len];
        for (int i = 0; i < len; i++) {
            nums[i] = in.nextLong();
        }
        long max = 0;
        for (int i = 0; i < len - 1; i++) {
            if (i + 2 < len) {
                max = Math.max(max, nums[i] * nums[i + 2]);
            }
            max = Math.max(max, nums[i] * nums[i + 1]);
        }
        System.out.println(max);
//        }
    }

米小游买商品

商店里有 n个商品，分别编号为 1~n ，每个商品都有一个价值 vali和体积 wi，米小游有一个有一个 m 容量的背包，他能够装得下任意多个体积之和不超过 m 的商品。

米小游认为有些东西一起购买会带来灾难，比如可莉的角色立牌和蹦蹦炸弹的小手办，所以他设定了 k组互斥关系，每组关系给定两个数字 a,b，表示编号为 a 的商品和编号为 b的商品不能同时购买。

米小游希望装下的物品的价值之和最大，请你帮帮他求出最大价值。

输入描述

第一行输入三个整数 n,m,k(1<=n<=15;1<=m<=10^9;0<=k<=15)表示商品数量、背包容量和互斥关系数量。

接下来 n行，每行输入两个整数 wi,vali(1<=wi,vali<=10^9) 表示每个物品的体积和价值。

接下来 k行，每行输入两个整数 a,b(1<=a,b<=n,a≠b)，描述一组互斥关系。

输出描述

在一行上输出一个整数表示答案。

示例 1

输入

1
2
3
4
5
6
3 100 2
15 19
20 30
15 19
1 2
2 3

输出

1
38

说明

根据两组互斥关系，买了 2 就不能买 1 和 3，所以我们可以购买物品 1 和物品 3，这样达到最大价值 。

示例 2

输入

1
2
3
4
5
6
3 20 2
15 19
20 30
15 19
1 2
2 3

输出

1
30

说明

背包容量只有20，只能装下一个物品，选择第二个物品，价值30。

思路与代码

暴力枚举+哈希表。

首先观察题目中的n只有15，因此可以直接使用回溯来解（也可以使用二进制来枚举）。回溯的思路如下：

  1. 每个物品有2种选择：选或者不选。无论什么情况下都可以不选择。关键是何时可以选择呢？
  2. 必须保证当前的背包容量是足够的，并且已经选择的物品并不会与当前物品出现互斥关系，这个可以使用哈希来进行快速判断。
  3. 不断更新所有可能的答案即可。
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
import java.util.*;

public class Main {
    private static int n, m, k;
    private static int[][] stocks; // {weight, value}
    private static Set<Integer>[] mutexes;
    private static int res = 0;

    private static boolean check(int i, Set<Integer> vst) {
        for (int v : vst) {
            if (mutexes[v].contains(i)) {
                return false;
            }
        }
        return true;
    }

    private static void backtrace(int i, int curValue, int curWeight, Set<Integer> vst) {
        if (i >= n) {
            res = Math.max(res, curValue);
            return;
        }
        backtrace(i + 1, curValue, curWeight, vst);

        if (check(i, vst) && curWeight + stocks[i][0] <= m) {
            vst.add(i);
            backtrace(i + 1, curValue + stocks[i][1], curWeight + stocks[i][0], vst);
            vst.remove(i);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        m = sc.nextInt();
        k = sc.nextInt();

        stocks = new int[n][2];
        mutexes = new HashSet[n];
        for (int i = 0; i < n; i++) {
            mutexes[i] = new HashSet<>();
        }

        for (int i = 0; i < n; i++) {
            stocks[i][0] = sc.nextInt(); // weight
            stocks[i][1] = sc.nextInt(); // value
        }

        for (int i = 0; i < k; i++) {
            int a = sc.nextInt() - 1;
            int b = sc.nextInt() - 1;
            mutexes[a].add(b);
            mutexes[b].add(a);
        }

        Set<Integer> vst = new HashSet<>();
        backtrace(0, 0, 0, vst);

        System.out.println(res);
        sc.close();
    }
}

删点

米小游和派蒙在进行一场游戏。游戏在一个基环树（点数与边数相等的无向简单连通图）上进行，定义图中一个点的度数为与其相连的边数，二人轮流进行以下操作：

● 选择图中一个度数为 1 的点，删除这个点以及与这个点相连的边。

图中有一个特殊的点 x ，删除了点 x 的玩家即获得胜利。

现在，由米小游先进行操作。在双方都采取最优策略的情况下，胜者是谁？

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 T(1<=T<=1000) 代表数据组数，每组测试数据描述如下：

第一行输入两个整数 n,x(3<=n<=10^5, 1<=x<=n) 表示图的点数及特殊点的编号。

此后 n 行，第 i 行输入两个整数 ui 和 vi (1<=vi,ui<=n ; ui!=vi) 表示树上第 i 条边连接节点 ui 和 vi 。保证图联通，没有重边。

除此之外，保证给定的边构成一个基环树，所有的 n 之和不超过 2*10^5 。

输出描述

对于每一组测试数据，在一行上输出胜者的名字（ Xiaoyo 或 Pyrmont ）。特别地，若点 x 不可能被删除，请输出 Draw 。

示例 1

输入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
3
4 2
1 2
1 3
1 4
3 4
5 2
1 2
1 3
1 4
3 4
2 5
3 1
1 2
1 3
2 3

输出

1
2
3
Xiaoyo
Pyrmont
Draw

思路与代码

拓扑排序+GTO博弈论。

所谓的基环树指的是：在一棵树的基础上加上一个环。

以后大家看到这种：每个人都会按照最优策略进行选择，最后判断谁会获胜。这种字眼的时候，基本就可以确定是一个GTO（博弈论）的题目。基本的做题思路就是找到一个规律可以直接得出结论的。

对于这道题，有一个显而易见的结论，如果x在环中，那么无论如何删点都不可能删的掉，因此必然是Draw。

如果点不在环中呢？

我们可以考虑在删除x点之前（包括x），有多少个节点是可以删除的？假设这个值是cnt。

如果cnt是偶数的话，那么Xiaoyo作为先选取的一方，一定是无法删除这个点的。因为双方的操作是对称的。

反之，则是Pyrmont获胜。

因此大题思路与拓扑排序类似，不断地将度数为1的节点加入队列，记录在删除x节点之前最多可以访问的节点数（包括x节点）。最后判断x的奇偶性即可。

需要注意的是

  1. 如果x节点是在环中的，那么我们永远无法遍历到这个节点，此时必然是Draw。
  2. 如果x节点的度数初始值就是1，那么此时Xiaoyo获胜。
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
import java.util.*;

public class Main {
    private static void solve() {
        int n = sc.nextInt();
        int x = sc.nextInt();
        
        List<List<Integer>> graph = new ArrayList<>(n + 1);
        for (int i = 0; i <= n; ++i) {
            graph.add(new ArrayList<>());
        }

        int[] indegre = new int[n + 1];
        for (int i = 0; i < n; ++i) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            graph.get(a).add(b);
            graph.get(b).add(a);
            indegre[a]++;
            indegre[b]++;
        }

        Deque<Integer> q = new ArrayDeque<>();
        for (int i = 1; i <= n; ++i) {
            if (indegre[i] == 1) {
                if (i == x) {
                    System.out.println("Xiaoyo");
                    return;
                }
                q.add(i);
            }
        }

        int cnt = 0;
        boolean flg = false;
        while (!q.isEmpty()) {
            int node = q.poll();
            cnt++;
            if (node == x) {
                flg = true;
                continue;
            }
            for (int next : graph.get(node)) {
                indegre[next]--;
                if (indegre[next] == 1) {
                    q.add(next);
                }
            }
        }

        if (!flg) {
            System.out.println("Draw");
        } else if (cnt % 2 == 0) {
            System.out.println("Pyrmont");
        } else {
            System.out.println("Xiaoyo");
        }
    }
    static Scanner sc = new Scanner(System.in);
    public static void main(String[] args) {
        int T = sc.nextInt();
        for (int i = 0; i < T; ++i) {
            solve();
        }
        sc.close();
    }
}

总结分析

难度对我来说比较大，还是基础不牢。

  • 第一题以后要注意使用long类型

  • 第二题的迷惑性字眼让我以为是dp，其实是暴力 以后要注意看数据范围，看是不是直接爆破

  • 第三题我以为是并查集+看有没有环

    • 拓扑排序一生之敌啊，这么多次都出现了拓扑，图论还是重要。得加强了

笔试题解
#米哈游
米哈游8.3秋招笔试
https://hexo-blog-five-swart.vercel.app/2024/08/05/米哈游秋招笔试/
作者
方立
发布于
2024年8月5日
许可协议