考试时间： 2023-09-16 （2小时）      T1   小美正在参加比赛，一共有 n 场比赛，赢得一场可以获得 1 分，如果上一场也赢了，可以获得额外的 1 分。现在给你 n 场比赛的结果，你需要计算小美的分数。   输入描述   第一行一个整数n，表示比赛的场数。 下一行n个整数，表示每场比赛的结果，1 表示赢，0 表示输。 1 ≤ n ≤    输出描述   一个整数，表示小美的分数。   示例   输入：51 1 1 0 1输出：6说明：第一场比赛获胜，获得1分。第二场比赛获胜，并且上场比赛也获胜，获得2分。第三次比赛获胜，并且上场比赛也获胜，获得2分。第四场比赛输了，获得0分。第五场比赛获胜，获得1分。   题解   import java.util.Scanner;// P1public 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 51 2 33 2 1输出：1说明：最多只能击败一个怪物。   题解       动态规划      import java.util.ArrayList;import java.util.List;import java.util.Scanner;// P3public 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   输入：51 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位就没有必要进行选择，因为这样的选择不会优于只选择一个元素的情况）；          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个城市，小