美团笔试AK（9月9日）

T3 栈+贪心

import java.util.Stack;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        String s = scanner.next();
        int n1 = s.length();
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < n1; i++) {
            if (!stack.isEmpty() && stack.peek() == s.charAt(i)) {
                stack.pop();
            } else {
                stack.push(s.charAt(i));
            }
        }
        if (stack.size() >= 2 * k) {
            System.out.println(stack.size() - 2 * k);
        } else {
            k -= stack.size() / 2;
            int t = stack.size() % 2;
            if (t == 1) {
                System.out.println(1);
            } else if (k % 2 == 1) {
                System.out.println(2);
            }else{
                System.out.println(0);
            }
        }
    }
}

T4 简单构造

package test;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = 1;
        while (t-- > 0) {
            solve(scanner);
        }
    }

    public static void solve(Scanner scanner) {
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int pre = 1;
        int l = 0;

        for (int i = 1; i <= n; ++i) {
            if (m - (l + pre) >= n - i) {
                System.out.print(l + pre + " ");
                pre += l;
                l++;
            } else {
                pre++;
                System.out.print(pre + " ");
            }
        }
        System.out.println();
    }
}

T5 前后缀算贡献

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
        }
        long ans = 0;
        long Mod = 1000000007;
        for (int k = 0; k < 30; k++) {
            int[] ones = new int[n];
            int[] zeros = new int[n];
            for (int i = 0; i < n; i++) {
                ones[i] = (a[i] >> k) & 1;
                zeros[i] = 1 - ones[i];
            }
            long[] S1 = new long[n + 1];
            long[] S2 = new long[n + 1];
            S1[0] = 0;
            S2[0] = 0;
            for (int i = 0; i < n; i++) {
                if (ones[i] == 1) {
                    S1[i + 1] = S1[i] + i + 1;
                    S2[i + 1] = S2[i];
                } else {
                    S1[i + 1] = S1[i];
                    S2[i + 1] = S2[i] + i + 1;
                }
            }
            for (int i = n - 1; i >= 0; i--) {
                if (ones[i] == 1) {
                    ans += (long) (n - i) * (1 << k) % Mod * S2[i] % Mod;
                } else {
                    ans += (long) (n - i) * (1 << k) % Mod * S1[i] % Mod;
                }
                ans %= Mod;
            }
            ans %= Mod;
        }
        System.out.println(ans % Mod);
    }
}