第一题

给定若干条线段 {[a,b]} a、b表示端点，如果a1<=a2<=b2<=b1就说线段[a1,b1] 包含线段[a2, b2]。 判断线段集合中是否存在一条线段包含另一条线段。

解法：

• 将数组按照 线段左端点从小到大排序，如果左端点一样，按照右端点从小到大排序。

• 从左到右遍历，针对当前的线段，遍历后面的线段，判断有没有被当前线段包含的线段

• 如果有，则返回

• 否则外层循环遍历下一个元素

public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] lines=new int[n][2];
        for(int i = 0; i < n; i++){
            lines[i][0]=sc.nextInt();
            lines[i][1]=sc.nextInt();
        }
        Arrays.sort(lines, new Comparator() { @Override public int compare(int[] o1, int[] o2) {
                int r1=o1[0]-o2[0];
                int r2=o1[1]-o2[1];
                if(r1==0) return r2;
                else return r1;
            }
        });
        for(int i=0;i<n-1;i++){
//            int start=lines[i][0];
            int end=lines[i][1];
            for(int j=i+1;j<n;j++){
                if(lines[j][1]<=end) {
                    System.out.println(true);
                    return;
                }
            }
        }
        System.out.println(false);
    }

第二题

（模拟题）轮流放牌、收牌。需要注意的是，每次到一个人的回合，可能会有多个放牌、收牌的过程（即每次放牌，牌堆中都存在一张点数相同的牌）。

    public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();
            int[] chick=new int[n];
            int[] duck=new int[n];
            for(int i=0;i<n;i++) chick[i]=sc.nextInt();
            for(int i=0;i<n;i++) duck[i]=sc.nextInt();
            ArrayList buff=new ArrayList();
            HashMap number2pos=new HashMap();
            int chickNum=0,ci=0;
            int duckNum=0, di=0;
            while (ci!=n||di!=n){
                if(ci<n){
                    while (buff.size()!=0&&ci<n){
                        int t = chick[ci];
                        if (number2pos.get(t) != null) {
                            int p = number2pos.get(t);
                            chickNum = chickNum + (buff.size() - p + 1);
                            ci++;
                            while (buff.size() != p) {
                                int rp = buff.get(p);
                                number2pos.remove(rp);
                                buff.remove(p);
                            }
                        }else break;
                    }
                    if(ci!=n) {
                        int t=chick[ci];
                        number2pos.put(t,buff.size());
                        buff.add(t);
                        ci++;
                    }
                }
                if(di<n){
                    while (buff.size()!=0&&di<n) {
                        int t = duck[di];
                        if (number2pos.get(t) != null) {
                            int p = number2pos.get(t);
                            duckNum = duckNum + (buff.size() - p + 1);
                            di++;
                            while (buff.size() != p) {
                                int rp = buff.get(p);
                                number2pos.remove(rp);
                                buff.remove(p);
                            }
                        }else break;
                    }
                    if(di!=n) {
                        int t=duck[di];
                        number2pos.put(t,buff.size());
                        buff.add(t);
                        di++;
                    }
                }
            }
            for(int l=0;l<buff.size();l++){
                if(buff.get(l)%2==0) duckNum++;
                else chickNum++;
            }
            System.out.println(chickNum+" "+duckNum);
        }

第三题

给定a,b,c 生成一个集合（范围是1-10^9），集合的生成规则为

1. 初始集合为{a}

2. 对于集合中的每个元素X，有X+B也属于该集合

3. 对于集合中的每个元素，X*c也属于该集合

给定数字q，判定q是否在集合中。

解法：如果q在集合中，q=ac^k+mb k,m>=0且为整数. 只要找到符合条件的k、m，就表示q属于这个集合。 tips：计算过程中使用long，防止溢出

 public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int num=sc.nextInt();
        for(int i=0;i<num;i++){
            System.out.println(check(sc.nextInt(),sc.nextInt(),sc.nextInt(),sc.nextInt()));
        }
    }
    public static int check(long a,long b,long c,long q){
        long accu=1;
        for(int k=0;k<32;k++){
            long m=a*accu;
            if(m>q) return 0;
            long res=q-m;
            if(res%b==0) return 1;
            accu*=c;
        }
        return 0;
    }

第四题

0-9 十个数字，每个数字给定若干个，要求把这些数字排列组成一个乘法算式；问如何排列，使得乘积最大。（贪心算法、大整数）

1. 可以证明，组成a*b的形式得到的答案最大，而不是多个数相乘。针对两个数，将他们直接拼接到一块比相乘的结果要大，得证。

2. 从最大的digit开始用，针对每个digit d, 判定是 concate(a,d)b大还是aconcate(b,d)大。选择较大的那种组合方式。

  public static void main(String[] args) {
                Scanner sc=new Scanner(System.in);
        LinkedList<Integer> digit=new LinkedList<>();
        for(int i=0;i<10;i++){
            int num=sc.nextInt();
            for(int j=0;j<num;j++){
                digit.addFirst(i);
            }
        }

        StringBuffer left=new StringBuffer(digit.peekFirst()+"");
        BigInteger leftb=new BigInteger(left.toString());
        digit.removeFirst();
        StringBuffer right=new StringBuffer(digit.peekFirst()+"");
        BigInteger rightb=new BigInteger(right.toString());
        digit.removeFirst();
        while (!digit.isEmpty()){
            BigInteger tmpl=new BigInteger(left.toString()+digit.peekFirst());
            BigInteger tmpr=new BigInteger(right.toString()+digit.peekFirst());
            if(tmpl.multiply(rightb).compareTo(leftb.multiply(tmpr))==1){//left big
                left.append(digit.peekFirst());
                leftb=tmpl;
            }else{
                right.append(digit.peekFirst());
                rightb=tmpr;
            }
            digit.removeFirst();
        }

        System.out.println(leftb.multiply(rightb));

    }