美团笔试记录

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

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; ++i) {
            arr[i] = sc.nextInt();
        }
        Arrays.sort(arr);
        List<List<Integer>> ret = new ArrayList<>();
        boolean[] vis = new boolean[n];
        search(arr, ret, new ArrayList<>(), 0, vis);
        StringBuilder cache = new StringBuilder();
        cache.append(ret.size()).append("
");
        if (n > 0) {
            for (List<Integer> list : ret) {
                cache.append(list.get(0));
                for (int i = 1; i < n; ++i) {
                    cache.append(" ").append(list.get(i));
                }
                cache.append("
");
            }
        }
        System.out.println(cache);
    }

    private static void search(int[] arr, List<List<Integer>> ret, ArrayList<Integer> list, int idx, boolean[] vis) {
        if (idx == arr.length) {
            ret.add(new ArrayList<>(list));
            return;
        }
        for (int i = 0; i < arr.length; ++i) {
            if (vis[i] || i > 0 && arr[i] == arr[i-1] && vis[i-1]) {
                continue;
            }
            vis[i] = true;
            list.add(arr[i]);
            search(arr, ret, list, idx + 1, vis);
            vis[i] = false;
            list.remove(list.size() - 1);
        }
    }

}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.next();
        StringBuilder buf = new StringBuilder(str);
        int n = sc.nextInt();
        Map<Character, PriorityQueue<Integer>> map = new HashMap<>();
        for (char ch = 'a'; ch <= 'z'; ch++) {
            map.put(ch, new PriorityQueue<>());
        }
        for (int i = 0; i < str.length(); ++i) {
            map.get(str.charAt(i)).add(i);
        }
        StringBuilder cache = new StringBuilder();
        while (n-- > 0) {
            int opt = sc.nextInt();
            if (opt == 1) {
                char ch = sc.next().charAt(0);
                map.get(ch).add(buf.length());
                buf.append(ch);
            } else if (opt == 2) {
                int pos1 = sc.nextInt() - 1;
                char ch = buf.charAt(pos1);
                Integer[] arr = map.get(ch).toArray(new Integer[0]);
                int delta = Integer.MAX_VALUE;
                if (arr.length > 1) {
                    int idx1 = Arrays.binarySearch(arr, pos1);
                    if (idx1 >= 0) {
                        if (idx1 != 0) {
                            delta = Math.abs(arr[idx1 - 1] - pos1);
                        }
                        if (idx1 != arr.length - 1) {
                            delta = Math.min(delta, Math.abs(arr[idx1 + 1] - pos1));
                        }
                    }
                }
                cache.append(delta == Integer.MAX_VALUE ? -1: delta).append("
");
            }
        }
        System.out.println(cache);
    }
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; ++i) {
            arr[i] = sc.nextInt();
        }
        int[] preSum = new int[n+1];
        for (int i = 1; i <= n; ++i) {
            preSum[i] = preSum[i-1] + arr[i-1]; // preSum[i] = arr[0..i)
        }
        int m = sc.nextInt();
        StringBuilder cache = new StringBuilder();
//        Tree tree = Tree.buildTree(0, arr.length - 1, arr);
        while(m-- > 0) {
            int opt = sc.nextInt();
            int L = sc.nextInt() - 1;
            int R = sc.nextInt() - 1;
            if (opt == 1) {
                int sum = preSum[R+1] - preSum[L];
                cache.append(sum).append("
");
            } else if (opt == 2) {
                long res = 0;
                long sum = preSum[R+1] - preSum[L];
                for (int j = L; j <= R; ++j) {
                    res += (sum - arr[j]) * (sum - arr[j]);
                }
                cache.append(res).append("
");
            } else if (opt == 3) {
//                int maxV = tree.query(L, R);
                int maxV = getMax(arr, L, R);
                cache.append(maxV).append("
");
            }
        }
        System.out.println(cache);
    }

    private static int getMax(int[] arr, int l, int r) {
        int maxV = arr[l];
        for (int i = l + 1;i <= r; ++i) {
            if (arr[i] > maxV) {
                maxV = arr[i];
            }
        }
        return maxV;
    }
}
class Tree {
    int left;
    int right;
    int maxV;
    Tree lson;
    Tree rson;

    public Tree(int left, int right) {
        this.left = left;
        this.right = right;
    }

    static Tree buildTree(int left, int right, int[] arr) {
        Tree tree = new Tree(left, right);
        if (left > right) {
            tree.maxV = Integer.MIN_VALUE;
            return tree;
        }
        if (left == right) {
            tree.maxV = arr[left];
            return tree;
        }
        int mid = left + right >> 1;
        tree.lson = buildTree(left, mid, arr);
        tree.rson = buildTree(mid +1, right, arr);
        tree.maxV = Math.max(tree.lson.maxV, tree.rson.maxV);
        return tree;
    }

    int query(int L, int R) {
        if (L <= left && right <= R) {
            return maxV;
        }
        int MaxV = Integer.MIN_VALUE;
        if (L <= lson.right) {
            maxV = lson.query(L, R);
        }
        if (R >= rson.left) {
            maxV = Math.max(maxV, rson.query(L, R));
        }
        return maxV;
    }

}