hihocoder46

http://hihocoder.com/contest/offers46/problems
题目1 : AEIOU
只是自定义了一个顺序而已，本质上还是最长递增子序列，可以用N*logN解决，
但是这里只有5种char，可以O(N)解决
而且注意到aei是一组，ou是一组，所以可以分开来计算
用aei来说，用AEI表示到i位置时以i位置结尾的最长子序列

package l461;

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        char[] cs = sc.next().toCharArray();
        StringBuilder s1=new StringBuilder(), s2=new StringBuilder();
        for(char c:cs) 
            if(c=='o'||c=='u') s2.append(c);
            else s1.append(c);
        
        char[]cs1=s1.toString().toCharArray(),cs2=s2.toString().toCharArray();
        
        int A=0,E=0,I=0;
        for(int i=0;i<cs1.length;i++){
            if(cs1[i]=='a') A++;
            else if(cs1[i]=='e') E=Math.max(E+1,A+1);
            else I=Math.max(I+1, Math.max(E+1, A+1));
        }
        
        int O=0,U=0;
        for(int i=0;i<cs2.length;i++){
            if(cs2[i]=='o') O++;
            else U=Math.max(U+1, O+1);
        }
        
        System.out.println(Math.max(A, Math.max(E, I)) + Math.max(O, U));
    }

}

题目2 : 数字游戏
BFS复杂度是节点的个数，是10^{n}，BFS各种prune仍然TLE后换一种思路
先定义好交换index的映射关系，然后对每个位置O(1)解决需要增减的次数，复杂度n*10！

package l462;

import java.util.Scanner;

public class Main {

    public static int min = Integer.MAX_VALUE;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        String a=sc.next(), b=sc.next();
        
        boolean[] vs = new boolean[n];
        int[]map=new int[n];
        dfs(a.toCharArray(),b.toCharArray(),0,map,vs);
        System.out.println(min);
    }

    private static void dfs(char[] cs1, char[] cs2, int i, int[] map, boolean[] vs) {
        if(i==map.length) {
            int res=0;
            for(int k=0;k<map.length;k++)
                res+=Math.min(Math.abs(cs1[k]-cs2[map[k]]), Math.min(Math.abs(cs1[k]-cs2[map[k]]+10), Math.abs(cs1[k]-cs2[map[k]]-10)));
            res+=cicrcle(map);
            min=Math.min(min, res);
            return;
        }
        
        for(int j=0;j<vs.length;j++) {
            if(!vs[j]) {
                vs[j]=true;
                map[i]=j;
                dfs(cs1,cs2,i+1,map,vs);
                vs[j]=false;
            }
        }
    }

    private static int cicrcle(int[] map) {
        boolean[] vis=new boolean[map.length];
        int res=0;
        for(int i=0;i<map.length;i++) {
            if(vis[i] || map[i]==i) continue;
            int j=map[i],cnt=1;
            vis[i]=true;
            while(j!=i) {
                vis[j]=true;
                cnt++;
                j=map[j];
            }
            res+=cnt-1;
        }
        return res;
    }
}

题目3 : 第K小分数
二分

package l463;

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        long l=sc.nextLong();
        int[]a=new int[n];
        for(int i=0;i<n;i++)a[i]=sc.nextInt();
        
        double lo=0, hi=1,mid=0.5;
        while(true) {
            mid=(lo+hi)/2;
            long t=get(a,mid);
            if(t>l) hi=mid;
            else if(t<l) lo=mid;
            else break;
        }
        
        String res="";
        double tt=-1;
        for(int i:a) {
            int t=(int)(mid*i);
            if((t+0.0)/i>tt) {
                tt=(t+0.0)/i;
                res=""+t+"/"+i;
            }
        }
        System.out.println(res);
    }

    private static long get(int[] a, double mid) {
        long res=0;
        for(int i:a) {
            res+=(int)(mid*i);
        }
        return res;
    }
}

题目4 : 逆序异或和
按位解决https://acm.masterliu.net/hihocoder/offer46/
用树状数组优化查找，按bit和某位是1是0构造树状数组

1. 注意数据溢出
2. 出后往前遍历求小于A的之前的有多少个，因为不知道tree[i][j]实际有多少个数

package l464;

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+1];
        int max=-1;
        for(int i=1;i<=n;i++){
            a[i]=sc.nextInt();
            max=Math.max(max, a[i]);
        }
        int[][][] tree = new int[20][2][1+max];
        
        long res = 0;
        // since we do not know the length of tree[bit][1], we have to reverse array
        for(int i=n; i>=1; i--)
            for(int bit=0,t=a[i]; bit<20; bit++,t>>=1) {
                if((t & 1)==1) {  // to be effective for xor
                    res += sum(a[i], tree[bit][0]) * (long)(1<<bit);
                    insert(a[i], tree[bit][1], 1, max);
                } else {
                    res += sum(a[i], tree[bit][1]) * (long)(1<<bit);
                    insert(a[i], tree[bit][0], 1, max);
                }
            }
        System.out.println(res);
    }
    
    private static int sum(int i, int[] c) {
        int sum = 0;
        while(i>0) {
            sum += c[i];
            i -= lowbit(i);
        }
        return sum;
    }

    private static void insert(int i, int[] c, int v, int N) {
        while(i<=N) {
            c[i] += v;
            i += lowbit(i);
        }
    }

    private static int lowbit(int i) {
        return i & (-i);
    }
}