第一题

答案

import java.util.Scanner;

public class mayiT1 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        scanner.nextLine();
        String s = scanner.nextLine();
        String t = scanner.nextLine();
        scanner.close();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) >= 'A' && s.charAt(i) <= 'Z') {
                System.out.print(Character.toUpperCase(s.charAt(i)));
            } else if (s.charAt(i) >= 'a' && s.charAt(i) <= 'z') {
                System.out.print(Character.toLowerCase(s.charAt(i)));
            } else if (s.charAt(i) >= '0' && s.charAt(i) <= '9') {
                System.out.print((int) t.charAt(i));
            } else {
                System.out.print('_');
            }
        }
    }
}

第二题

思路

二叉树即为特殊的图，用邻接表存储，把编号为1的结点当作根(0,0)，dfs求每个点的坐标，即可得出答案。

答案

import java.util.*;

public class mayiT2 {
    static List<Integer>[] tree;
    static Map<Integer, Coordinate> map;
    static boolean[] visited;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int q = scanner.nextInt();
        tree = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) {
            tree[i] = new ArrayList<>();
        }
        for (int i = 1; i <= n - 1; i++) {
            int u = scanner.nextInt();
            int v = scanner.nextInt();
            tree[u].add(v);
            tree[v].add(u);
        }
        int root = 1;
        map = new HashMap<>();
        visited = new boolean[n + 1];
        visited[1] = true;
        map.put(root, new Coordinate(0, 0));
        dfs(root);
        for (int i = 0; i < q; i++) {
            int c1 = scanner.nextInt();
            int c2 = scanner.nextInt();
            System.out.println(Math.abs(map.get(c1).getX() - map.get(c2).getX()) + Math.abs(map.get(c1).getY() - map.get(c2).getY()));
        }

        scanner.close();
    }

    private static void dfs(int root) {
        boolean left = true; // 是否是左孩子
        tree[root].sort(Integer::compareTo);
        for (int child : tree[root]) {
            if (!visited[child]) {
                visited[child] = true;
                if (left) {
                    left = false;
                    map.put(child, new Coordinate(map.get(root).getX() - 1, map.get(root).getY() - 1));
                    dfs(child);
                } else {
                    map.put(child, new Coordinate(map.get(root).getX() + 1, map.get(root).getY() - 1));
                    dfs(child);
                }
            }
        }
    }

    static class Coordinate {
        int x;
        int y;

        public Coordinate(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public int getX() {
            return x;
        }

        public int getY() {
            return y;
        }
    }
}

第三题

题目描述

给定n个元素ai，要求计算以下表达式的值：

输入描述

第一行包含一个整数n，表示元素的个数，满足1 ≤ n ≤ 10^5^

第二行包含n个整数a1，a2，...，an，其中1 ≤ ai ≤ 10^5^

输出描述

输出一个整数，表示计算得到的值s

示例1

输入

3
1 2 3

输出

9

说明

对于输入的样例，计算过程如下

具体计算：

当i=1时：1+0+0=1

当i=2时：2+1+0=3

当i=3时：3+1+1=5

将所有结果相加，得到S=1+3+5=9

思路

采用 计数优化 方式

1. 计数数组 count：统计输入数组中每个数的出现次数，加快后续计算。
2. 前缀和数组 prefixSum：计算前缀和，用于快速统计某个区间的数的个数。
3. 优化计算 floor(ai/aj)：
   • 直接遍历 ai 并累加 floor(ai / aj) 的贡献，避免双重循环暴力计算，提高效率。

时间复杂度

• 预处理 count 和 prefixSum：O(n)
• 计算 S：O(n log n) 级别，优于 O(n²)

答案

import java.util.Scanner;

public class mayiT3 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] nums = new int[n];
        int maxVal = 0;
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
            maxVal = Math.max(maxVal, nums[i]);
        }
        scanner.close();

        // 统计每个数出现的次数
        int[] count = new int[maxVal + 1];
        for (int num : nums) {
            count[num]++;
        }

        // 计算前缀和，用于快速查询小于等于某个数的总个数
        int[] prefixSum = new int[maxVal + 1];
        for (int i = 1; i <= maxVal; i++) {
            prefixSum[i] = prefixSum[i - 1] + count[i];
        }

        long ans = 0;
        // 遍历每个可能的 a[i]
        for (int num = 1; num <= maxVal; num++) {
            if (count[num] == 0) { // 跳过未出现的数
                continue;
            }
            // 计算当前 a[i] 对所有 a[j] 的贡献
            for (int k = 1; k * num <= maxVal; k++) {
                int lower = k * num;
                int upper = Math.min(maxVal, (k + 1) * num - 1);
                int numCount = prefixSum[upper] - prefixSum[lower - 1];
                ans += (long) count[num] * k * numCount;
            }
        }
        System.out.println(ans);
    }
}