0. 序言

第一题花了10分钟A掉了，第二题30分钟A掉了，还有80分钟呢，以为第三题稳了。结果到最后才憋出来30%，目前牛客网上没看到思路，求大佬指点。

1. 将字母分为3个等级输出

输入一个字符串，高级为"bdfhkl"，中级为"aceimnorstuvwxz"，低级为"gjqpy"，请将字符串按字母等级分割为3个字符串，每个字符串内按字典序排序输出。如果字符串为空输出null。
三个按字典序排序的优先队列就OK了，水题。

import java.util.PriorityQueue;
import java.util.Scanner;

public class Main1 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.next();
        PriorityQueue<Character> q1 = new PriorityQueue<>();
        PriorityQueue<Character> q2 = new PriorityQueue<>();
        PriorityQueue<Character> q3 = new PriorityQueue<>();

        for(int i=0;i<s.length();i++){
            switch (fun(s.charAt(i))){
                case 1:q1.add(s.charAt(i));break;
                case 2:q2.add(s.charAt(i));break;
                case 3:q3.add(s.charAt(i));break;
                default:break;
            }
        }
        if(q1.size()!=0){
            while(q1.size()!=0)
                System.out.print(q1.poll());
            System.out.println();
        }else
            System.out.println("null");
        if(q2.size()!=0){
            while(q2.size()!=0)
                System.out.print(q2.poll());
            System.out.println();
        }else
            System.out.println("null");
        if(q3.size()!=0){
            while(q3.size()!=0)
                System.out.print(q3.poll());
            System.out.println();
        }else
            System.out.println("null");
    }
    public static int fun(char c){
        switch (c){
            case 'b':
            case 'h':
            case 'f':
            case 'k':
            case 'l':
            case 'd':
                return 1;
            case 'g':
            case 'j':
            case 'p':
            case 'q':
            case 'y':
                return 3;
            default:
                return 2;
        }
    }
}

2. 推荐歌曲

每首歌属于一个流派，如pop/jazz等，不清楚流派的为UnKnown Style。
输入有三种情况：

• I songName songStyle ： 表示将流派为songStyle的、歌名为songName的歌加载到曲库。
• P songName : 表示用户完整听完了名为songName的歌。
• B songName : 表示用户切歌了名为songName的歌。

如若用户完整听完一首歌，则对这首歌的喜好度+3，如若这首歌与上次完整听完的歌是一个流派，则该流派内除了这首歌的喜好度+1。
如若用户切了一首歌，则对这首歌的喜好度-2，如若这首歌与上次切掉的歌是一个流派，则该流派内除了这首歌的喜好度-1。
按喜好度顺序输出歌名和它的流派，若喜好度相同，按字典序排序。

看起来复杂，起始就是根据题意模拟即可，关键在于设计双向映射的数据结构。一共用到了3个map，根据需要相互转换。
Map<String,List<string>> map;//表示一个流派下有哪些歌
Map<String,String> map2;//表示一首歌属于哪个流派
Map<String,Integer> map3;//表示歌的分数</string>

import java.util.*;

public class Main2 {

    static class Song{
        String name;
        String lib;
        int point;

        public Song(String name, String lib,int point) {
            this.name = name;
            this.lib = lib;
            this.point = point;
        }
    }

    static Map<String,List<String>> map;//lib - songs
    static Map<String,String> map2;//song - lib
    static Map<String,Integer> map3;//song - points

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        map = new HashMap<>();
        map2 = new HashMap<>();
        map3 = new HashMap<>();
        String lastP ="";
        String lastB = "";
        while(scanner.hasNextLine()){
            String s = scanner.nextLine();
            if(s.equals(""))
                break;
            String type = s.split(" ")[0];
            if(type.equals("I")){
                List<String> list =  map.getOrDefault(s.split(" ")[2], new ArrayList<>());
                list.add(s.split(" ")[1]);
                map.put(s.split(" ")[2],list);
                map2.put(s.split(" ")[1],s.split(" ")[2]);
                map3.put(s.split(" ")[1],0);
            }else if(type.equals("P")){
                String name = s.split(" ")[1];
                map3.put(name,map3.get(name)+3);
                if(map2.get(name).equals(lastP)){
                    String lib = map2.get(name);
                    for(String songNames:map.get(lib)){
                        if(!songNames.equals(name))
                            map3.put(songNames,map3.get(songNames)+1);
                    }
                }
                lastP = map2.get(name);

            }else{
                String name = s.split(" ")[1];
                map3.put(name,map3.get(name)-2);
                if(map2.get(name).equals(lastB)){
                    String lib = map2.get(name);
                    for(String songNames:map.get(lib)){
                        if(!songNames.equals(name))
                            map3.put(songNames,map3.get(songNames)-1);
                    }
                }
                lastB = map2.get(name);
            }
        }
        Queue<Song> q = new PriorityQueue<>(new Comparator<Song>() {
            @Override
            public int compare(Song o1, Song o2) {
                if(o1.point==o2.point)
                    return o1.name.compareTo(o2.name);
                return -o1.point + o2.point;
            }
        });
        for(String key:map3.keySet())
            q.add(new Song(key,map2.get(key),map3.get(key)));
        while(q.size()!=0){
            Song song = q.poll();
            System.out.println(song.name+" "+song.lib);
        }
    }
}

3.切水果

40*50的方格上，有若干个水果，可以横向/纵向/斜向（斜率为±1）4个角度消去一条直线上的水果，问至少需要几刀可以全部切除。
用了贪心，bfs，dfs，分别过了10% 30% 20%。贪心明显是不对的，但是也不至于过那么少吧。。。

方法一：贪心(10%)

每次取最大收益的一刀。当然贪心理论是不对的，我可以找出反例，但应该能覆盖不少用例啊~

import java.util.*;

public class Main30 {

    static Map<String,List<Integer>> map;
    static class D{
        String type;
        List<Integer> list;

        public D(String type, List<Integer> list) {
            this.type = type;
            this.list = list;
        }
    }
    static int[] temp;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        map = new HashMap<>();
        temp = new int[n];
        for(int i = 0;i<n;i++){
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            add(x,y,i);
        }
        Queue<D> q = new PriorityQueue<>(new Comparator<D>() {
            @Override
            public int compare(D o1, D o2) {
                int cnt1 = 0;
                int cnt2 = 0;
                for(int a:o1.list)
                    if(temp[a]==0)
                        cnt1++;
                for(int a:o2.list)
                    if(temp[a]==0)
                        cnt2++;
                return -cnt1+cnt2;
            }
        });
        for(String key:map.keySet())
            q.add(new D(key,map.get(key)));

        int all = 0;
        int res = 0;
        while(q.size()!=0){
            D d = q.poll();
            res++;
            for(int i:d.list){
                if(temp[i]==0){
                    temp[i] = 1;
                    all++;
                }
            }
            if(all==n)
                break;
        }
        System.out.println(res);
    }
    public static void add(int x,int y,int i){
        //纵向
        List<Integer> list1 = map.getOrDefault("0-"+y, new ArrayList<>());
        list1.add(i);
        map.put("0-"+y,list1);
        //横向
        list1 = map.getOrDefault("1-"+x, new ArrayList<>());
        list1.add(i);
        map.put("1-"+x,list1);
        //从左上到右下
        list1 = map.getOrDefault("2-"+(y-x), new ArrayList<>());
        list1.add(i);
        map.put("2-"+(y-x),list1);
        //从右上到左下
        list1 = map.getOrDefault("3-"+(x+y), new ArrayList<>());
        list1.add(i);
        map.put("3-"+(x+y),list1);
    }
}

方法二：BFS（30%,TLE)

将剩余水果列表作为节点，每次拓展时，将列表里每个节点的四刀作为可能性，消去列表x||y||x+y||x-y相同的，作为子节点继续加入队列，直到某个列表为空，则当前次数为最少次数。不知道还能怎么优化...

import java.util.*;

public class Main31 {

    static Map<String,Set<List<Integer>>> map;

    static int[][] a;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        map = new HashMap<>();
        a = new int[n][2];
        for(int i = 0;i<n;i++){
            a[i][0] = scanner.nextInt();
            a[i][1] = scanner.nextInt();
        }
        Queue<List<Integer> > q = new LinkedList<>();
        List<Integer> root =  new ArrayList<>();
        for(int i=0;i<n;i++)
            root.add(i);
        q.add(root);
        int res = 0;
        while(q.size()!=0){
            res++;
            Queue<List<Integer> > q2 = new LinkedList<>();
            while(q.size()!=0){
                List<Integer> list = q.poll();
                Set<List<Integer>> lists = expand(list);
                for(List<Integer> t:lists){
                    if(t.size()==0){
                        System.out.println(res);
                        return;
                    }
                }
                q2.addAll(lists);
            }
            q = q2;
        }

    }


    public static Set<List<Integer>> expand(List<Integer> list){
        if(map.containsKey(list.toString()))
            return map.get(list.toString());
        Set<List<Integer>> res = new HashSet<>();
        List<Integer> list1;
        for(int e:list){
            int x = a[e][0];
            list1 = new ArrayList<>();
            for(int ee:list)
                if(a[ee][0]!=x)
                    list1.add(ee);
            res.add(list1);

            int y = a[e][1];
            list1 = new ArrayList<>();
            for(int ee:list)
                if(a[ee][1]!=y)
                    list1.add(ee);
            res.add(list1);

            int xy = a[e][0]-a[e][1];
            list1 = new ArrayList<>();
            for(int ee:list)
                if(a[ee][0]-a[ee][1]!=xy)
                    list1.add(ee);
            res.add(list1);

            int yx = a[e][0]+a[e][1];
            list1 = new ArrayList<>();
            for(int ee:list)
                if(a[ee][0]+a[ee][1]!=yx)
                    list1.add(ee);
            res.add(list1);
        }
        map.put(list.toString(),res);
        return res;
    }
}

方法三：DFS（20%,TLE)

扩展方法和bfs一样，不过每个dfs方法里记载当前的次数，如果次数已经大于了目前最少次数，则剪枝。另外用一个map做缓存。
对于某个节点扩展出的四条dfs路径，优先执行收益更高的，即局部贪心，但好像也没什么用...

import java.util.*;

public class MainF {

    static Map<String,Integer> map;
    static int[][] a;
    static int step;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        map = new HashMap<>();
        a = new int[n][2];
        step = Integer.MAX_VALUE;
        for(int i = 0;i<n;i++){
            a[i][0] = scanner.nextInt();
            a[i][1] = scanner.nextInt();
        }
        Queue<List<Integer> > q = new LinkedList<>();
        List<Integer> root =  new ArrayList<>();
        for(int i=0;i<n;i++)
            root.add(i);
        dfs(0,root);
        System.out.println(step);
    }

    public static void dfs(int cnt, List<Integer> list){
        if(cnt>step)
            return;
        if(map.containsKey(list.toString())){
            if(map.get(list.toString())<cnt)
                return;
        }

        if(list.size()==0)
            step = Math.min(step,cnt);
        List<Integer> list1,list2,list3,list4;
        for(int e:list){
            int x = a[e][0];
            list1 = new ArrayList<>();
            for(int ee:list)
                if(a[ee][0]!=x)
                    list1.add(ee);
            int y = a[e][1];
            list2 = new ArrayList<>();
            for(int ee:list)
                if(a[ee][1]!=y)
                    list2.add(ee);
            int xy = a[e][0]-a[e][1];
            list3 = new ArrayList<>();
            for(int ee:list)
                if(a[ee][0]-a[ee][1]!=xy)
                    list3.add(ee);
            int yx = a[e][0]+a[e][1];
            list4 = new ArrayList<>();
            for(int ee:list)
                if(a[ee][0]+a[ee][1]!=yx)
                    list4.add(ee);
                Queue<List<Integer>> q= new PriorityQueue<>(new Comparator<List<Integer>>() {
                    @Override
                    public int compare(List<Integer> o1, List<Integer> o2) {
                        return o1.size()-o2.size();
                    }
                });
            q.add(list1);
            q.add(list2);
            q.add(list3);
            q.add(list4);
            while(q.size()!=0){
                List<Integer> list5 = q.poll();
                dfs(cnt+1,list5);
            }
            map.put(list.toString(),cnt);
        }
    }
}

改进：我为什么要对于每个节点的四种方式排序效率最优啊？明明可以所有节点的四种方式一起排效率最优，相当于贪心了。事后诸葛亮

import java.util.*;

public class MainF {

    static Map<String,Integer> map;
    static int[][] a;
    static int step;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        map = new HashMap<>();
        a = new int[n][2];
        step = Integer.MAX_VALUE;
        for(int i = 0;i<n;i++){
            a[i][0] = scanner.nextInt();
            a[i][1] = scanner.nextInt();
        }
        Queue<List<Integer> > q = new LinkedList<>();
        List<Integer> root =  new ArrayList<>();
        for(int i=0;i<n;i++)
            root.add(i);
        dfs(0,root);
        System.out.println(step);
    }

    public static void dfs(int cnt, List<Integer> list){
        if(cnt>step)
            return;
        if(map.containsKey(list.toString())){
            if(map.get(list.toString())<cnt)
                return;
        }

        if(list.size()==0)
            step = Math.min(step,cnt);
        List<Integer> list1,list2,list3,list4;
        Queue<List<Integer>> q= new PriorityQueue<>(new Comparator<List<Integer>>() {
                    @Override
                    public int compare(List<Integer> o1, List<Integer> o2) {
                        return o1.size()-o2.size();
                    }
                });
        for(int e:list){
            int x = a[e][0];
            list1 = new ArrayList<>();
            for(int ee:list)
                if(a[ee][0]!=x)
                    list1.add(ee);
            int y = a[e][1];
            list2 = new ArrayList<>();
            for(int ee:list)
                if(a[ee][1]!=y)
                    list2.add(ee);
            int xy = a[e][0]-a[e][1];
            list3 = new ArrayList<>();
            for(int ee:list)
                if(a[ee][0]-a[ee][1]!=xy)
                    list3.add(ee);
            int yx = a[e][0]+a[e][1];
            list4 = new ArrayList<>();
            for(int ee:list)
                if(a[ee][0]+a[ee][1]!=yx)
                    list4.add(ee);

            q.add(list1);
            q.add(list2);
            q.add(list3);
            q.add(list4);
        }
        while(q.size()!=0){
            List<Integer> list5 = q.poll();
            dfs(cnt+1,list5);
        }
        map.put(list.toString(),cnt);
    }
}