hihocoder53

http://hihocoder.com/contest/offers53/problems
题目1 : 继承顺位
建树，然后前序遍历

package l531;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
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();
        Set<String> dead=new HashSet<String>();
        Map<String,List<String>> child = new HashMap<String,List<String>>();
        String k=sc.next();
        for(int i=0;i<n;i++) {
            String t1=sc.next(),t2=sc.next();
            if("birth".equals(t1)) {
                String t3=sc.next();
                if(!child.containsKey(t2)) child.put(t2, new ArrayList<String>());
                child.get(t2).add(t3);
            } else {
                dead.add(t2);
            }
        }
        
        List<String>res=new ArrayList<String>();
        dfs(child,k,res);
        for(String t:res) {
            if(!k.equals(t) && !dead.contains(t))
                System.out.println(t);
        }
    }

    private static void dfs(Map<String, List<String>> child, String k, List<String> res) {
        res.add(k);
        if(!child.containsKey(k)) return;
        for(String t:child.get(k)) {
            dfs(child,t,res);
        }
    }
}

题目2 : hiho字符串3
递归

package l532;

import java.util.Scanner;

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

    private static char get(int i, long t) {
        if(i==1) return t%2==0?'i':'h';
        char res=get(i-1,(t+1)/2);
        if(res=='h') return t%2==0?'i':'h';
        else if(res=='i') return t%2==0?'o':'i';
        else return t%2==0?'h':'o';
    }

}

题目3 : 最长一次上升子序列
把原问题分解成两个子问题，求0到i的最长下降子序列，和i到n的最长下降子序列，最长下降子序列用最小末尾辅助数组优化到NlogN
一直WA，不知bug在何处

package l533;

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        int[]a=new int[n];
        for(int i=0;i<n;i++)a[i]=-sc.nextInt();
        int[][] dp = new int[n][2];
        for(int i=0;i<n;i++)dp[i][0]=1;
        int[] lis = LIS(a), lds = LDS(a);
        
        int max=lis[n-1];
        for(int i=0;i<n-1;i++) {
            max=Math.max(max, lis[i]+lds[i+1]);
        }
        System.out.println(max);
    }

    private static int[] LDS(int[] a) {
        int[] b = new int[a.length];
        for(int i=0;i<a.length;i++)b[i]=-a[a.length-1-i];
        int[] t = LIS(b);
        int[] res = new int[a.length];
        for(int i=0;i<a.length;i++)res[i]=t[a.length-1-i];
        return res;
    }

    private static int[] LIS(int[] a) {
        int[] helper = new int[1+a.length]; //预留index为0
        int[] res = new int[a.length];
        res[0] = 1;
        helper[0]=Integer.MIN_VALUE;
        helper[1]=a[0];
        int p=1;
        
        for(int i=1;i<a.length;i++) {
            if(a[i]>helper[p]) {
                helper[++p] = a[i];
                res[i] = p;
            } else {
                int t=Arrays.binarySearch(helper, 0, p, a[i]);
                int pos=t>0?t:-(t+1);
                helper[pos] = a[i];
                res[i] = pos;
            }
        }
        return res;
    }
}