算法竞赛入门经典（第2版）第三章习题（Java）

• 算法竞赛入门经典第2版第三章习题Java

• Page41 提示3-7：在很多情况下，最好是在做一件事之前检查是不是可以做，而不要做完再后悔。因为“悔棋”往往比较麻烦。
• Page52 例题3-5：生成元：只需要一次性枚举1000000内的所有正整数m，标记“m加上m的各个数字之和得到的数有一个生成元是m”，最后查表即可。

第6题，题给的不全。
第12题懒得做了。
引用的包代码中并没有写，在eclipse下按Shift+Ctrl+o即可导入包

习题 3-1 得分（Score，ACM/ICPC Seoul 2005，UVA1585）

思路：定义一个变量x存放O连续的次数，出现O时总分z=z+x++，出现X时x置为1。

    public static void Score() {
        Scanner in = new Scanner(System.in);
        String[] zs = in.nextLine().split("");
        //存放O连续出现的次数
        int x = 1;
        //总分
        int z = 0;
        for (int i = 0; i < zs.length; i++) {
            if (zs[i].equals("O"))
                z = z + x++;
            else
                x = 1;
        }
        System.out.println(z);
    }

习题3-2 分子量（Molar Mass，ACM/ICPC Seoul 2007，UVa1586）

思路：将字符串C6H5OH放入字符数组中，遍历数组，使用switch判断，如果是元素字母，将其原子量加入总结果 zl 中，并存入当前原子量 q 中；如果是数字先存入原子个数 ge 中，当遍历到字母在进行结算，（ge-1)*q存入总结果zl中。

public static void MM() {
        Scanner in = new Scanner(System.in);
        //根据题目要求声明结果格式
        DecimalFormat df = new DecimalFormat("0.000");
        String[] fz = in.nextLine().split("");
        //记录分子量
        double zl = 0;
        //记录当前元素原子个数
        int ge = 0;
        //记录当前元素原子量
        double q = 0;
        for (int i = 0; i < fz.length; i++) {
            switch (fz[i]) {
            case "C":
                //存入总结果
                zl = zl + 12.01;
                //如果之前还有没加的原子，加入总结果
                if (ge > 0)
                    zl = zl + (ge - 1) * q;
                //原子个数清零
                ge = 0;
                //存放当前元素原子量
                q = 12.01;
                break;
            case "H":
                zl = zl + 1.008;
                if (ge > 0)
                    zl = zl + (ge - 1) * q;
                ge = 0;
                q = 1.008;
                break;
            case "O":
                zl = zl + 16.00;
                if (ge > 0)
                    zl = zl + (ge - 1) * q;
                ge = 0;
                q = 16.00;
                break;
            case "N":
                zl = zl + 14.01;
                if (ge > 0)
                    zl = zl + (ge - 1) * q;
                ge = 0;
                q = 14.01;
                break;
            //如果不是字母，计算当前原子个数。
            default:
                ge = ge * 10 + Integer.parseInt(fz[i]);
                //如果原字符串最后一个字符不是字母，会导致当前元素的原子量无法正常结算。
                if (i == fz.length - 1)
                    zl = zl + (ge - 1) * q;
                break;
            }
        }
        System.out.println(df.format(zl));
    }

3-3 数数字 （Digit Counting，ACM/ICPC Danang 2007，UVa1225）

思路：声明一个长度为10的数组，遍历字符串，将字符转换为具体数字存入数字

public static void DC() {
        Scanner in = new Scanner(System.in);
        //字符串数组
        String[] sz = in.nextLine().split("");
        //记录数字出现次数数组
        int[] ci = new int[10];
        for (int i = 0; i < sz.length; i++)
            ci[Integer.parseInt(sz[i])]++;
        for (int i = 0; i < ci.length; i++)
            System.out.println(i + " : " + ci[i]);
    }

习题3-4 周期串（Periodic Strings，UVa455）

思路：从0到length/2遍历字符串，下一个字母如果与首字母相同，则判断该子串是否为周期串。

public static void PS() {
        Scanner in = new Scanner(System.in);
        String str = in.nextLine();
        //将原字符串存入数组
        String[] sz = str.split("");
        //子串
        String c = "";
        for (int i = 0; i < sz.length / 2; i++) {
            c += sz[i];
            //判断下个字母是否与首字母相同
            if (sz[i + 1].equals(sz[0])) {
                String s = "";
                //判断是否与原字符串相同
                for (int j = 0; j < sz.length; j += c.length()) 
                    s += c;
                if (s.equals(str))
                    break;
                else
                    continue;
            }
        }
        System.out.println(c);
    }

习题3-5 谜题（Puzzle，ACM/ICPC World Finals 1993，UVa227）

思路：将网格存入二维数组，设置两个变量存放当前格的位置，switch执行不同操作，换内容即可

    public static void Puzzle() {
        Scanner in = new Scanner(System.in);
        //将命令存入数组
        String[] bu = in.nextLine().split("");
        String[][] fz = new String[5][5];
        fz[0] = new String[] { "T", "R", "G", "S", "J" };
        fz[1] = new String[] { "X", "D", "O", "K", "I" };
        fz[2] = new String[] { "M", "*", "V", "L", "N" };
        fz[3] = new String[] { "W", "P", "A", "B", "E" };
        fz[4] = new String[] { "U", "Q", "H", "C", "F" };
        for (String[] da : fz) {
            for (String yin : da)
                System.out.print(yin + " ");
            System.out.println();
        }
        //记录位置
        int x = 1;
        int y = 2;
        for (int i = 0; i < bu.length - 1; i++) {
            //如果不越界，交换值，并改变当前位置。
            switch (bu[i]) {
            case "A":
                if (y - 1 < 0) {
                    System.out.println("This puzzle has no final configuration");
                    break;
                } else {
                    String c = fz[y][x];
                    fz[y][x] = fz[y - 1][x];
                    fz[--y][x] = c;
                    break;
                }
            case "B":
                if (y + 1 >= fz.length) {
                    System.out.println("This puzzle has no final configuration");
                    break;
                } else {
                    String c = fz[y][x];
                    fz[y][x] = fz[y + 1][x];
                    fz[++y][x] = c;
                    break;
                }
            case "L":
                if (x - 1 < 0) {
                    System.out.println("This puzzle has no final configuration");
                    break;
                } else {
                    String c = fz[y][x];
                    fz[y][x] = fz[y][x - 1];
                    fz[y][--x] = c;
                    break;
                }
            case "R":
                if (x + 1 >= fz.length) {
                    System.out.println("This puzzle has no final configuration");
                    break;
                } else {
                    String c = fz[y][x];
                    fz[y][x] = fz[y][x + 1];
                    fz[y][++x] = c;
                    break;
                }

            }
        }
        for (String[] da : fz) {
            for (String yin : da)
                System.out.print(yin + " ");
            System.out.println();
        }
    }

习题3-7 DNA序列（DNA Consensus String，ACM/ICPC Seoul 2006，UVa1368）

思路：将DNA序列放入二维数组dna中，遍历每一列，用数组ddd记录每个字母的次数，然后遍历ddd数组找到最优解。

    public static void DNA() {
        Scanner in = new Scanner("6 10 ATGTTACCAT AAGTTACGAT AACAAAGCAA AAGTTACCTT AAGTTACCAA TACTTACCAA");
        int m = in.nextInt();
        int n = in.nextInt();
        //记录Hamming距离和的值
        int pin = 0;
        //最优解的DNA
        String jg = "";
        String[] ddd = { "A", "C", "G", "T" };
        String[][] dna = new String[m][n];
        //将字符存入dna数组
        for (int i = 0; i < m; i++)
            dna[i] = in.next().split("");
        for (int i = 0; i < n; i++) {
        //记录字母出现次数
            int[] ci = new int[4];
            for (int j = 0; j < m; j++) {
                switch (dna[j][i]) {
                case "A":
                    ci[0]++;
                    break;
                case "C":
                    ci[1]++;
                    break;
                case "G":
                    ci[2]++;
                    break;
                case "T":
                    ci[3]++;
                    break;
                }
            }
            //寻找出现次数最多的解
            int o = 0;
            for (int k = 1; k < 4; k++)
                if (ci[k] > ci[o])
                    o = k;
            pin += (m - ci[o]);
            jg += ddd[o];
        }
        System.out.println(pin + " " + jg);
    }

习题3-8 循环小数（Repeating Decimals，ACM/ICPC World Finals 1990,UVa202)

思路：刚开始以为根据结果找规律，实在找不到。然后百度了一下说，循环节跟余数有关，当出现重复的余数，就出现循环节。这样看来和前面的周期串问题相似。

public static void RD(){
        Scanner in=new Scanner(System.in);
        int a=in.nextInt();
        int b=in.nextInt();
        //标记，当出现相同的余数，停止循环
        int bj=0;
        //用来存放余数
        int[] ys=new int[10000];
        int y=a%b;
        //余数的个数
        int ysg=0;
        String gs="0.";
        while(bj==0&&y%b!=0){
            y=y*10%b;
            for(int i=0;i<ysg;i++)
                if(y==ys[i])
                    bj=1;
            ys[ysg++]=y;
        }
        //用到高精度数
        BigDecimal aa=new BigDecimal(Double.toString(a));
        BigDecimal bb=new BigDecimal(Double.toString(b));
        System.out.println(aa.divide(bb,ysg1,BigDecimal.ROUND_HALF_UP));
    }

习题3-9 子序列（All in All，UVa10340）

思路：使用两层循环，外层循环每走一个，判断是否和内层循环的当前字母相同，如果相同，内层循环则向前走一个。最后判断内层循环是否走到结尾，如果走到结尾就是子序列。

    public static void AiA() {
        Scanner in = new Scanner(System.in);
        String[] s = in.next().split("");
        String[] t = in.next().split("");
        //内层循环走的位置。
        int sp = 0;
        for (int tp = 0; tp < t.length; tp++) {
            for (; sp < s.length;) {
                if (t[tp].equals(s[sp]))
                    sp++;
                break;
            }
            if (sp > s.length - 1)
                break;
        }
        if (sp > s.length - 1)
            System.out.println("yes");
        else
            System.out.println("no");
    }

    public static void p9_1() {
        Scanner in = new Scanner(System.in);
        String[] s = in.next().split("");
        String[] t = in.next().split("");
        int j = 0;
        for (int i = 0; i < t.length && j < s.length; i++) {
            if (t[i].equals(s[j]))
                j++;
        }
        if (j == s.length)
            System.out.println("yes");
        else
            System.out.println("no");
    }

习题3-10盒子（Box，ACM/ICPC NEERC 2004，UVa1587）

思路：设长方体的六个面存入二维数组。每行变成长、宽的形式，然后排序，再判断每两行是否相同，最后判断第0个、第2个、第4个（排序后）长方形，每个长方形的长或宽等于其中一个长方形长或宽。

    public static void Box() {
         Scanner in = new Scanner(System.in);
         //声明二维数组
        int[][] jx = new int[6][2];
        //存入数据，按a大于等于b形式存入
        for (int i = 0; i < 6; i++) {
            jx[i][0] = in.nextInt();
            jx[i][1] = in.nextInt();
            if (jx[i][0] < jx[i][1]) {
                int c = 0;
                c = jx[i][0];
                jx[i][0] = jx[i][1];
                jx[i][1] = c;
            }
        }
        //按第一列排序
        for(int i=0;i<5;i++){
            for(int j=i+1;j<6;j++){
                if(jx[j][0]<jx[i][0]){
                    int[] x=new int[2];
                    x=jx[j];
                    jx[j]=jx[i];
                    jx[i]=x;
                }
            }
        }
        //按第二列排序
        for(int i=0;i<5;i++){
            for(int j=i+1;j<6;j++){
                if(jx[j][0]==jx[i][0]&&jx[j][1]<jx[i][1]){
                    int[] x=new int[2];
                    x=jx[j];
                    jx[j]=jx[i];
                    jx[i]=x;
                }
            }
        }
        //定义一个标记
        int bj=1;
        //判断长方形是否两两相等
        for(int i=0;i<6;i+=2){
            if(jx[i][0]!=jx[i+1][0]||jx[i][1]!=jx[i+1][1]){
                bj=0;
                break;
            }
        }
        if(bj==0){
            System.out.println("no");
            return;
        }
        //判断一个长方形的长或宽是否等于其中一个长方形的长或宽
        if((jx[0][0]==jx[2][0]&&jx[0][1]==jx[4][0]&&jx[2][1]==jx[4][1])||
            (jx[0][0]==jx[2][0]&&jx[0][1]==jx[4][1]&&jx[2][1]==jx[4][0])||
            (jx[0][0]==jx[2][1]&&jx[0][1]==jx[4][0]&&jx[2][0]==jx[4][1])||
            (jx[0][0]==jx[2][1]&&jx[0][1]==jx[4][1]&&jx[2][0]==jx[4][0])
            )
            System.out.println("yes");
        else
            System.out.println("no");
    }

习题 3-11 换抵挡装置（Kickdown，ACM/ICPC NEERC 2006，UVa1588）

思路：另n1为短条，n2为长条，即n1>=n2。将n1和n2存入数组。假设将长条固定住，让小条从左到右移动（从0移动到n2.length-n1.length），如果每处都小于4，结果为长条长度。否则，让短条左右超出长条移动移动（正负0到n1.length），如果每处都小于4输出结果（长条加短条移动的距离）。

public static void Kickdown() {
        Scanner in = new Scanner("2211221122 21212");
        //短条
        String[] znd = in.next().split("");
        //长条
        String[] znc = in.next().split("");
        if (znd.length > znc.length) {
            String[] jh = znd;
            znd = znc;
            znc = jh;
        }
        //将短条放入数组中
        int[] snd = new int[znd.length];
        for (int i = 0; i < snd.length; i++)
            snd[i] = Integer.parseInt(znd[i]);
        int[] snc = new int[znc.length];
        //将长条放入数组中
        for (int i = 0; i < snc.length; i++)
            snc[i] = Integer.parseInt(znc[i]);
        //定义短条移动的距离
        int yd = 0;
        while (yd <= snc.length - snd.length) {
        //判断每处是否小于4
            for (int i = 0; i < snd.length; i++) {
                if (snd[i] + snc[i + yd] > 3) {
                    yd++;
                    break;
                    //短条最后一处小于4输出结果
                } else if (i == snd.length - 1) {
                    System.out.println(znc.length);
                    return;
                }
            }
        }
        yd = 0;
        //移动的距离小于短条长度
        while (yd < snd.length) {
            yd++;
            //当移动的距离等于小条长度跳出循环。
            if (yd == snd.length)
                break;
            //定义两个标记，左边每处是否小于4，右边每处是否小于4
            int z = 1;
            int y = 1;
            for (int i = 0; i < snd.length  - yd; i++) {
                //如果左边有大于3的地方，z置为0
                if (snd[i + yd] + snc[i] > 3) {
                    z = 0;
                }
                //如果右边有大于3的地方，y置为0
                if (snd[i] + snc[i + (snc.length - snd.length) + yd] > 3) {
                    y = 0;
                }
                //如果两边都有大于3的地方，跳出内层循环，移动的距离yd加1
                if (y == 0 && z == 0)
                    break;
            }
            //如果内层的循环走完，并且两个标记有一个为1，结束循环，输出结果。
            if (y == 1 || z == 1)
                break;
        }
        System.out.println(znc.length + yd);
    }