考试时间： 2023-09-16 （2小时）

T1

小美正在参加比赛，一共有 n 场比赛，赢得一场可以获得 1 分，如果上一场也赢了，可以获得额外的 1 分。现在给你 n 场比赛的结果，你需要计算小美的分数。

输入描述

第一行一个整数n，表示比赛的场数。 下一行n个整数，表示每场比赛的结果，1 表示赢，0 表示输。 1 ≤ n ≤

输出描述

一个整数，表示小美的分数。

示例

输入：
5
1 1 1 0 1

输出：
6

说明：
第一场比赛获胜，获得1分。
第二场比赛获胜，并且上场比赛也获胜，获得2分。
第三次比赛获胜，并且上场比赛也获胜，获得2分。
第四场比赛输了，获得0分。
第五场比赛获胜，获得1分。

题解

import java.util.Scanner;

// P1
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = in.nextInt();

        int score = a[0];
        for (int i = 1; i < n; i++) {
            if (a[i] == 1) {
                score += (a[i - 1] == 1) ? 2 : 1;
            }
        }
        System.out.println(score);
    }
}

T2

小美在训练场打靶，靶一共有 10 环，靶的中心位于 (0,0)，如果打中的位置在以靶心为圆心，半径为 1 的圆内，则得 10 分，之后每向外一圈分数减 1，直到 1 分，每圈的半径都比上一圈大 1。即如果打中的位置在以靶心为圆心，半径为i的圆内，则得 11 - i 分。

如果打中的位置不在任何一圈内，则得 0分。

输入描述

一行两个整数 x，y，表示打中的位置坐标。

1 ≤ x,y ≤ 10

输出描述

输出一个整数，表示得分。

示例1

输入：
1 0

输出：
10

示例2

输入：
1 1

输出：
9

题解

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int x = in.nextInt(), y = in.nextInt();
        int dd = x * x + y * y;

        // 特别容易遗漏
        int res = dd == 0 ? 11 : 0;
        for (int i = 1; i < 12; i++) {
            if (dd <= i * i) {
                res = 11 - i;
                break;
            }
        }
        System.out.println(res);
    }
}

T3

小美在玩游戏，游戏中有 n 个怪物，怪物的血量为 ， 攻击力为 ， 小美的血量为H，攻击力为A， 小美可以击败血量和攻击力都小于自己的怪物，并且打败怪物后血量降为怪物的血量，攻击力降为怪物的攻击力，小美想知道最多可以打败多少怪物。

输入描述

第一行三个整数 n,H，A，分别表示怪物的数量，小美的血量，小美的攻击。

第二行n个整数 , 表示怪物的血量。

第三行n个整数 ，表示怪物的攻击力。

1 ≤ n ≤

输出描述

输出一个整数表示答案。

示例1

输入：
3 4 5
1 2 3
3 2 1

输出：
1

说明：
最多只能击败一个怪物。

题解

动态规划

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

// P3
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), H = in.nextInt(), A = in.nextInt();
        Monster[] list = new Monster[n];
        for (int i = 0; i < n; i++) list[i] = new Monster();
        for (int i = 0; i < n; i++) list[i].h = in.nextInt();
        for (int i = 0; i < n; i++) list[i].a = in.nextInt();

        Solution solution = new Solution();
        System.out.println(solution.solve(list, H, A));
    }
}

class Monster {
    public int h, a;
    // 最多可以打败多个其他怪物
    public int max;
}


class Solution {
    public int solve(Monster[] list, int H, int A) {
        List<Monster> monsters = new ArrayList<>();
        for (Monster monster : list) {
            if (monster.a < A && monster.h < H) {
                monsters.add(monster);
            }
        }

        Monster xm = new Monster();
        xm.a = A;
        xm.h = H;
        monsters.add(xm);
        monsters.sort((o1, o2) -> {
            if (o1.a != o2.a) {
                return o1.a - o2.a;
            } else {
                return o2.h - o1.h;
            }
        });
        for (int i = 1; i < monsters.size(); i++) {
            Monster cur = monsters.get(i);
            for (int l = 0; l < i; l++) {
                Monster prev = monsters.get(l);
                if (prev.a < cur.a && prev.h < cur.h) {
                    cur.max = Math.max(cur.max, prev.max + 1);
                }
            }
        }

        return xm.max;
    }
}

P4

小美有一个长度为n的数组，她想从中选出至少一个或多个数，使得这些个数的按位与的结果可以被 整除。例如小美有一个数组[1,2,4,12]，那么她可以选出[4,12]，因为 4 &12= 4，可以被 整除，所以 m 的最大值为 2。请帮小美选数，使得整数m尽可能的大。

输入描述

第一行一个整数几，表示数组的长度。

第二行几个整数 ，表示数组的元素。

输出描述

输出一个整数，表示 m 的最大值。

示例1

输入：
5
1 2 3 20 28

输出：
2

说明：
选择20和28，20&28 = 20，可以被 22 整除，所以m 的最大值为 2。

题解

2^m == （1 << m） 从这里可以看出，如果 k % (2^m) == 0 这里的 m 就是k二进制后从低位到高位第一个1出现的位置。

然后两种情况进行枚举找到最佳答案：

1. 只选中一个元素；
2. 选择两个元素（元素没有相同的1位就没有必要进行选择，因为这样的选择不会优于只选择一个元素的情况）；

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = in.nextInt();

        Solution solution = new Solution();
        System.out.println(solution.solve(a));
    }
}


class Solution {
    int max = 0;

    public int solve(int[] a) {
        // 对元素进行分组 groupMap.get(i) 表示二进制第i位值为1的数字
        Map<Integer, List<Integer>> groupMap = new HashMap<>();
        for (int num : a) {
            int bit = 0;
            boolean foundOne = false;

            int k = num;
            while (k != 0) {
                if ((k & 1) == 1) {
                    //这里更新结果，是判断只选当前元素是的结果值（即第一个１所在的位置）
                    if (!foundOne) max = Math.max(bit, max);

                    // Map<bit, num>
                    groupMap.computeIfAbsent(bit, p -> new ArrayList<>()).add(num);
                    foundOne = true;
                }

                k >>= 1;
                bit++;
            }
        }

        // 这里是尝试选取两个元素，进行求最佳的解
        // 元素没有相同的1位就没有必要进行选择，因为这样的选择不会优于只选择一个元素的情况
        for (List list : groupMap.values()) {
            int n = list.size();
            for (int i = 0; i < n; i++) {
                int ai = (int) list.get(i);
                for (int j = i + 1; j < n; j++) {
                    int aj = (int) list.get(j);

                    this.max = Math.max(max, f(ai & aj));
                }
            }
        }


        return max;
    }

    // 求 k 二进制，从低位到高位第一个1出现的位置,  这个位置即为 k % (2^m) == 0 的最大的 m
    public int f(int k) {
        int bit = 0;
        while (k != 0) {
            if ((k & 1) == 1) break;

            k >>= 1;
            bit++;
        }

        return bit;
    }
}

T5

地图上有n个城市，小