hihocoder54

http://hihocoder.com/contest/offers54/problems
题目1 : 小数数字
模拟除法，WA，不清楚哪里出现bug
应该出出现重复的余数才break，而不是重复的商

package l541;

import java.util.HashSet;
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(),m=sc.nextInt();
        Set<Integer>s=new HashSet<Integer>();
        while(true) {
            n*=10;
            while(n<m) {
                n=10*n;
                s.add(0);
            }
            if(s.contains(n/m)) break;
            s.add(n/m);
            n%=m;
            if(n==0) break;
        }
        StringBuilder sb=new StringBuilder();
        for(int i=0;i<10;i++)
            if(s.contains(i))sb.append(i);
        System.out.println(sb.toString());
    }
}

题目2 : 回文字符串2
分成2部分，一部分多出一个数，
如果是前面部分多，表示要删掉的数在前面，那就从中间往外扩；
如果后面部分多，表示要删掉的数在后面，那就从两边往中间扩
然后奇偶情况分开来考虑
回文：（1）中心往外面扩 （2）因为有字符比较，有时也可以用trie
因为只有1个多余字符，直接（1）就OK

package l542;

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s=sc.next();
        char[]cs=s.toCharArray();
        int res=cs.length;
        int mid=cs.length/2;
        if(cs.length%2==0) {
            int t1=get(s,cs,0,cs.length-1),t2=get2(s,cs,mid-1,mid+1);
            if(t1!=-1) res=Math.min(res,t1);
            if(t2!=-1) res=Math.min(res,t2);
        }else {
            int t1=get(s,cs,0, cs.length-1),t2=get2(s,cs,mid, mid+1);
            if(t1!=-1) res=Math.min(res,t1);
            if(t2!=-1) res=Math.min(res,t2);
        }
        System.out.println(res+1);
    }

    private static int get2(String s, char[] cs, int i, int j) {
        while(j<cs.length && cs[i]==cs[j]) {
            i--;
            j++;
        }
        if(isPard(s.substring(0,i+1)+s.substring(j, cs.length))) return i;
        return -1;
    }

    private static int get(String s, char[] cs, int i, int j) {
        int flag = j/2;
        while(i<flag && cs[i]==cs[j]) {
            i++;
            j--;
        }
        if(isPard(s.substring(i,j))) return j;
        return -1;
    }

    private static boolean isPard(String s) {
        char[]cs=s.toCharArray();
        int i=0,j=cs.length-1;
        while(i<j && cs[i]==cs[j]) {
            i++;
            j--;
        }
        return i>=j;
    }
}

题目3 : 最小差值
一开始想二分来着，然后对每个mid计算是否存在一种选法使得最大差为mid，但是直接判断是不是存在没啥思路，然后想着枚举第一个数然后DFS，估摸着DFS肯定TLE，想着枚举选出来的最大值或者最小值可能会吧复杂度降下来，但是没想出来

那就直接枚举最大值（或者最小值）吧，然后让选的最小值尽量大就好了，一开始TreeSet TLE，优化为指针数组AC

package l543;

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
import java.util.TreeSet;

public class Copy_2_of_Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt(),m=sc.nextInt();
        int[][] a=new int[n][m];
        TreeSet<Integer>[] ts = new TreeSet[n];
        Set<Integer> vis= new HashSet<Integer>();
        int min = Integer.MIN_VALUE, max=Integer.MIN_VALUE;
        for(int i=0;i<n;i++)ts[i]=new TreeSet<Integer>();
        for(int i=0;i<n;i++){
            int min2=Integer.MAX_VALUE,max2=Integer.MIN_VALUE;
            for(int j=0;j<m;j++){
                a[i][j]=sc.nextInt();
                ts[i].add(a[i][j]);
                vis.add(a[i][j]);
                min2 = Math.min(min2, a[i][j]);
                max2 = Math.max(max2, a[i][j]);
            }
            min = Math.max(min, min2);
            max = Math.max(max, max2);
        }
        
        int res=Integer.MAX_VALUE;
        for(int i=min; i<=max; i++) {
            if(!vis.contains(i)) continue;
            int t=Integer.MAX_VALUE;
            boolean flag = true;
            for(int p=0;p<n;p++) {
                Integer tt=ts[p].floor(i);
                if(tt==null) {
                    flag = false;
                    break;
                } else {
                    t=Math.min(t, tt);
                }
            }
            if(flag) res=Math.min(res, i-t);
        }
        System.out.println(res);
    }
}

package l543;

import java.util.Arrays;
import java.util.HashSet;
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(),m=sc.nextInt();
        int[][] a=new int[n][m];
        Set<Integer> vis= new HashSet<Integer>();
        int min = Integer.MIN_VALUE, max=Integer.MIN_VALUE;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                a[i][j]=sc.nextInt();
                vis.add(a[i][j]);
            }
            Arrays.sort(a[i]);
            min = Math.max(min, a[i][0]);
            max = Math.max(max, a[i][m-1]);
        }
        
        int res=Integer.MAX_VALUE;
        int[] points = new int[n];
        for(int i=min; i<=max; i++) {
            if(!vis.contains(i)) continue;
            int t=Integer.MAX_VALUE;
            for(int p=0;p<n;p++) {
                int ps = points[p];
                while(ps<m-1 && a[p][ps+1]<=i) ps++;
                points[p] = ps;
                t=Math.min(t, a[p][ps]);
            }
            res=Math.min(res, i-t);
        }
        System.out.println(res);
    }
}