美团9.3日 4+1编程题

import java.util.*;

/**
 * @author bty
 * @date 2022/9/3
 * @since 1.8
 **/
public class Main {


    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();

        Map<Integer, Integer> val2Idx = new HashMap<>();

        for (int i = 0; i < n; i++) {
            int temp = in.nextInt();
            val2Idx.put(temp,i);
        }


        int[] res = new int[n];

        for (Integer val : val2Idx.keySet()) {
            int mex = calcMex(val2Idx.keySet(), val);
            Integer idx = val2Idx.get(val);
            res[idx] = mex;
        }

        for (int i : res) {
            System.out.print(i);
            System.out.print(" ");
        }


    }

    public static int calcMex(Set<Integer> set,int val){

        int result = 0;
        while(set.contains(result)){
            if(val==result) return val;
            result++;
        }
        return result;
    }
}

import java.util.*;

/**
 * @author bty
 * @date 2022/9/3
 * @since 1.8
 * 
 **/
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] parents = new int[n + 1];
        parents[1] = 1;
        for (int i = 2; i <= n; i++) {
            int parent = in.nextInt();
            parents[i] = parent;
        }
        in.nextLine();
        String marks = in.nextLine();
        char[] markArr = marks.toCharArray();

        Map<Integer, Set<Character>> result = new HashMap<>();

        Map<Integer,Set<Integer>> fathers = new HashMap<>();
        for (int i = 1; i <= n; i++) {
            fathers.put(i,new HashSet<>());
            result.put(i,new HashSet<>());
        }

        for (int i = 1; i <= n; i++) {
            int tempJ = i;
            while (parents[tempJ] != tempJ) {
                fathers.get(i).add(parents[tempJ]);
                tempJ = parents[tempJ];
            }
            fathers.get(i).add(i);
        }
        for (Integer son : fathers.keySet()) {
            Set<Integer> fatherSet = fathers.get(son);
            for (Integer father : fatherSet) {
                result.get(father).add(markArr[son-1]);
            }
        }


        for (int i = 1; i <= n; i++) {
            System.out.print(result.get(i).size());
            System.out.print(" ");
        }


    }
}

import java.util.Scanner;

/**
 * @author bty
 * @date 2022/9/3
 * @since 1.8
 **/
public class Main3 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int k = in.nextInt();

        int[] position = new int[m+1];
        for (int i = 1; i <= m; i++) {
            int curPosition = in.nextInt();
            position[i] = curPosition;
        }
        int[] ideaSalary = new int[m+1];
        for (int i = 1; i <= m; i++) {
            int curSalary = in.nextInt();
            ideaSalary[i] = curSalary;
        }
        int[] lowSalary = new int[m+1];
        for (int i = 1; i <=m; i++) {
            int curSalary = in.nextInt();
            lowSalary[i] = curSalary;
        }

        int[] dp = new int[m+1];

        if(position[1]==k){
            dp[1] = ideaSalary[1];
        } else{
            dp[1] = lowSalary[1];
        }
        if(m==1){
            System.out.println(dp[1]);
            return;
        }

        for (int i = 2; i <= m; i++) {


            for (int j = 1; j < i; j++) {
                if(position[j]!=position[i]){
                    dp[i] = Math.max(dp[j]+lowSalary[i],dp[i]);
                } else {
                    dp[i] = Math.max(dp[j]+ideaSalary[i],dp[i]);
                }
            }
        }
        System.out.println(dp[m]);
    }
}