hihocoder47

http://hihocoder.com/contest/offers47/problems
题目1 : 删除树节点
模拟一遍，维持map根据parent node查找child node

package l471;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt(),k=sc.nextInt();
        int[]a=new int[1+n];
        for(int i=1;i<=n;i++)a[i]=sc.nextInt();
        int[]p=new int[n+1];
        Map<Integer, Set<Integer>>map=new HashMap<Integer, Set<Integer>>();
        for(int i=1;i<=n;i++) {
            p[i]=sc.nextInt();
            if(!map.containsKey(p[i])) map.put(p[i], new HashSet<Integer>());
            map.get(p[i]).add(i);
        }
        
        for(int i=1;i<=n;i++) {
            if(a[i]<k) {
                if(map.containsKey(i))
                    for(int s:map.get(i)) {
                        p[s] = p[i];
                        map.get(p[i]).add(s);
                    }
                p[i] = -1;
                map.remove(i);
            }
        }
        
        for(int i=1;i<=n-1;i++) System.out.print(p[i]+" ");
        System.out.println(p[n]);
    }
}

题目3 : 公平分队II
1.Hi一开始一定要尽量均分，然后交换最多能带来2N-2的增益，如果不均分，即使交换有2N-1的增益，那也最多跟均分一样
2.如果不能均分，则尽量差别不大，比如N=3，可以有2中分法：
1 4 5 && 2 3 6
1 4 6 && 2 3 5
2种情况如果Ho选大的，Hi最后交换都会得到4 5 6
如果Ho选小的，反而Hi最后交换后得到的都是3 5 6
同理，Hi必须这样分得差别不大
写出来其实代码是一样的

package l472;

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        if(n==1) {
            System.out.println(2);
            return;
        }
        long nn=n;
        long sum=(1+2*nn)*nn;
        System.out.println(sum/2+(2*n-2));
    }
}