1. Xiao Mei's Addition [Easy]

Given an array, perforrm consecutive additions, but you can change one plus sign into a multiplication sign. Determine which plus sign to change to maximize the final result.

Solution: Only by changing the plus sign between two adjacent numbers with the maximum product can the overall result be maximized. First, find the positions of these two numbers, then subtract these two numbers from the total sum and add their product.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] arr = new long[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextLong();
        }
        System.out.println(maxSumAfterReplace(arr));
    }

    public static long maxSumAfterReplace(long[] nums) {
        long sum = 0;
        int maxIdx = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            sum += nums[i];
            if (nums[i] * nums[i + 1] > nums[maxIdx] * nums[maxIdx + 1]) {
                maxIdx = i;
            }
        }
        sum += nums[nums.length - 1];
        return sum - nums[maxIdx] - nums[maxIdx + 1] + nums[maxIdx] * nums[maxIdx + 1];
    }
}

Complexity: Time O(n), Space O(n).

2. Xiao Mei's Array Operation [Tricky]

Given an array, each operation selects two numbers, one increments by 1 and the other decrements by 1. Find the maximum possible frequency of the mode after any number of operations.

Solution: If the sum is divisible by the length, all numbers can become the average. Otherwise, remove either the maximum or minimum element as a "waste" to make the rest divisible. Then compute the minimum operations to make all elements equal to either floor or ceil of the average.

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] arr = new long[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextLong();
        }
        System.out.println(minOperations(arr));
    }

    public static long minOperations(long[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        long sum = 0;
        for (long num : nums) sum += num;
        if (sum % n == 0) {
            return countOps(nums, sum / n, 0, n - 1) / 2;
        }
        // Remove max
        long avg1 = (sum - nums[n - 1]) / (n - 1);
        long ops1 = countOps(nums, avg1, 1, n - 2) + Math.abs(avg1 - nums[0]) + Math.abs((sum - nums[n - 1] - avg1 * (n - 1)));
        long ops2 = countOps(nums, avg1 + 1, 1, n - 2) + Math.abs(avg1 + 1 - nums[0]) + Math.abs((sum - nums[n - 1] - (avg1 + 1) * (n - 1)));
        // Remove min
        long avg3 = (sum - nums[0]) / (n - 1);
        long ops3 = countOps(nums, avg3, 1, n - 2) + Math.abs(avg3 - nums[n - 1]) + Math.abs((sum - nums[0] - avg3 * (n - 1)));
        long ops4 = countOps(nums, avg3 + 1, 1, n - 2) + Math.abs(avg3 + 1 - nums[n - 1]) + Math.abs((sum - nums[0] - (avg3 + 1) * (n - 1)));
        return Math.min(Math.min(ops1, ops2), Math.min(ops3, ops4)) / 2;
    }

    private static long countOps(long[] nums, long target, int left, int right) {
        long count = 0;
        for (int i = left; i <= right; i++) {
            if (nums[i] < target) count += target - nums[i];
            else if (nums[i] > target) count += nums[i] - target;
        }
        return count;
    }
}

Complexity: Time O(n log n), Space O(n).

3. Xiao Mei's 01 String Flip [DP]

Define weight of a 01 string as the minimum flips to make adjacent characters different. For a given string, compute the sum of weights of all substrings with length >= 2.

Solution: Use dynamic programming. For each substring [i, j], compute the minimum flips to make it alternating. dp[i][j][0] and dp[i][j][1] represent the minimum flips if the substring ends with 0 or 1 respectively.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        System.out.println(totalWeight(s));
    }

    public static int totalWeight(String s) {
        int n = s.length();
        int[][][] dp = new int[n][n][2];
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == '0') {
                dp[i][i][0] = 0;
                dp[i][i][1] = 1;
            } else {
                dp[i][i][0] = 1;
                dp[i][i][1] = 0;
            }
        }
        int total = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (s.charAt(j) == '0') {
                    dp[i][j][0] = dp[i][j - 1][1];
                    dp[i][j][1] = dp[i][j - 1][0] + 1;
                } else {
                    dp[i][j][0] = dp[i][j - 1][1] + 1;
                    dp[i][j][1] = dp[i][j - 1][0];
                }
                total += Math.min(dp[i][j][0], dp[i][j][1]);
            }
        }
        return total;
    }
}

Complexity: Time O(n^2), Space O(n^3).

4. Xiao Mei's Takeout Order ID [Easy]

Order IDs range from 1 to m; when exceeding m, restart from 1. Given the order number q, find its ID.

Solution: Use modulo operation. If q % m == 0, then ID is m; otherwise, it's q % m.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        int[][] queries = new int[t][2];
        for (int i = 0; i < t; i++) {
            queries[i][0] = sc.nextInt();
            queries[i][1] = sc.nextInt();
        }
        for (int id : computeIDs(queries)) {
            System.out.println(id);
        }
    }

    public static int[] computeIDs(int[][] queries) {
        int[] res = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int m = queries[i][0];
            int q = queries[i][1];
            res[i] = q % m == 0 ? m : q % m;
        }
        return res;
    }
}

Complexity: Time O(n), Space O(n).

5. Xiao Mei's Array Operation 2 [Easy]

Given an array and k operations (each operation: select two indices u and v, increase nums[u] by 1, decrease nums[v] by 1), after performing all operations, check if the array is non-decreasing.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        String[] results = new String[t];
        for (int i = 0; i < t; i++) {
            int n = sc.nextInt();
            int k = sc.nextInt();
            int[] arr = new int[n];
            for (int j = 0; j < n; j++) arr[j] = sc.nextInt();
            int[][] ops = new int[k][2];
            for (int j = 0; j < k; j++) {
                ops[j][0] = sc.nextInt() - 1;
                ops[j][1] = sc.nextInt() - 1;
            }
            results[i] = isNonDecreasing(arr, ops);
        }
        for (String s : results) System.out.println(s);
    }

    public static String isNonDecreasing(int[] nums, int[][] ops) {
        for (int[] op : ops) {
            nums[op[0]]++;
            nums[op[1]]--;
        }
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] < nums[i - 1]) return "No";
        }
        return "Yes";
    }
}

Complexity: Time O(n), Space O(n).

6. Xiao Mei's Array Construction [Hard, DP]

Given array a, construct array b with positive integers, same length, same sum, but each element different from a. Count number of such b.

Solution: DP. dp[i][j] = number of ways to have sum i with length j. Initialize dp[sum][len] considering constraints. Transition: for last element value k (1 to i-1), if not equal to a[j-1], add dp[i-k][j-1].

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] a = new long[n];
        for (int i = 0; i < n; i++) a[i] = sc.nextLong();
        System.out.println(countArrays(a));
    }

    public static long countArrays(long[] a) {
        int n = a.length;
        long sum = 0;
        for (long v : a) sum += v;
        long[][] dp = new long[(int)(sum + 1)][n + 1];
        final long MOD = 1000000007L;
        for (int i = 1; i <= sum; i++) {
            dp[i][1] = (a[0] == i) ? 0 : 1;
        }
        for (int i = 2; i <= sum; i++) {
            for (int j = 2; j <= n; j++) {
                long ways = 0;
                for (int k = 1; k < i; k++) {
                    if (a[j - 1] == k) continue;
                    ways = (ways + dp[i - k][j - 1]) % MOD;
                }
                dp[i][j] = ways;
            }
        }
        return dp[(int)sum][n];
    }
}

Complexity: Time O(n^2 * sum), Space O(n^2).

7. Meituan Merchant Registration System [Easy]

Register merchants with name (lowercase letters) and address. If name not registered, register as main store. If already registered, compare address: if same as main store, fail; else register as branch. Output names sorted lexicographically, with main address and number of branches.

import java.util.*;

public class Main {
    static Map<String, String> mainStore = new HashMap<>();
    static Map<String, Set<String>> branches = new HashMap<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.nextLine());
        for (int i = 0; i < n; i++) {
            String[] parts = sc.nextLine().split(" ");
            process(parts[0], parts[1]);
        }
        List<String> names = new ArrayList<>(mainStore.keySet());
        Collections.sort(names);
        for (String name : names) {
            System.out.println(name + " " + mainStore.get(name) + " " + branches.get(name).size());
        }
    }

    static void process(String name, String addr) {
        if (!name.matches("[a-z]+")) return;
        if (!mainStore.containsKey(name)) {
            mainStore.put(name, addr);
            branches.put(name, new HashSet<>());
        } else {
            if (!mainStore.get(name).equals(addr)) {
                branches.get(name).add(addr);
            }
        }
    }
}

Complexity: Time O(n log n), Space O(n).

Summary

Most problems are easy; challenging ones involve dynamic programming. Key is to understand the problem and connect to DP patterns.