[数据结构与算法]“蓝桥杯”练习系统 基础练习

??OJ 传送门

??想不出什么漂亮话，

??希望大家能精益求精把。

??可能会 $\mathrm{J}\mathrm{a}\mathrm{v}\mathrm{a}$、$\mathrm{C}$++ 混写，

??差别不大。

??以蓝桥的总和难度而言，

??基础练习入个门，然后历届真题一刷就能冲击国家一等奖，

??题库后面的那些题个人综合来看，

??建议是转其他平台刷，

??虽然我在哪多少都刷了点就是的了。

BASIC 1? 闰年判断

??OJ：蓝桥

??感觉应该分类为 $\mathrm{B}\mathrm{E}\mathrm{G}\mathrm{I}\mathrm{N}$，而非 $\mathrm{B}\mathrm{A}\mathrm{S}\mathrm{I}\mathrm{C}$。

??因为，可以说你的程序就算执行效率再高，与自然语言描述的闰年判断差距也不大，

??如：

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int year = in.nextInt();
        if ((year % 4 == 0 && year % 100 != 0) || year % 400 == 0)
            System.out.println("yes");
        else
            System.out.println("no");
    }
}

??但其实还是有不小的优化空间，

??如合并判断分支，使得至多判断两个布尔表达式的值就能得到结果。

boolean isLeapYear(int year) { return year % 100 == 0 ? year % 400 == 0 : year % 4 == 0; }

??小压一个行。

??还有就是，对于 $\mathrm{n}$ 进制数 $\mathrm{N}$，$\mathrm{n}>1$，

??在其最低位后拼接 $\mathrm{k}$ 个 $0$，

??得到的数值为 $\mathrm{N}\times {\mathrm{n}}^{\mathrm{k}}$。

??我们自然可以知道，$4$ 的倍数在二进制下，最低两位一定是 $00$。

??将 $\mathrm{y}\mathrm{e}\mathrm{a}\mathrm{r}$ 与 $0\mathrm{b}11$ 做与运算，结果为 $0$ 则代表 $\mathrm{y}\mathrm{e}\mathrm{a}\mathrm{r}$ 为 $4$ 的倍数。

??运算速度稍微会快于取余。

boolean isLeapYear(int year) { return year % 100 == 0 ? year % 400 == 0 : (year & 0b11) == 0; }

??还有就是 $\mathrm{J}\mathrm{a}\mathrm{v}\mathrm{a}8$ 提供了新的工具类 IsoChronology，

??直接调用 INSTANCE 成员的 isLeapYear 方法，就能达到判断闰年的效果。

		IsoChronology.INSTANCE.isLeapYear(year);

BASIC 2? 01字串

??OJ：蓝桥

??这个题很适合做复杂度下界一个分类的讨论，

??一个程序从零个或多个输入经由有限个步骤到一个或多个输出，

??通常我们在计算复杂度时，只去关系中间执行的有限步骤与那些输入有光，而忽略了输入输出的规模。

??这个题就是让我们顺序输出所有长度为 $\mathrm{n}$ 的 $01$，无论你中间进由几步，最后都要输出 $O(n\log n)$ 个字符。

??也就是说，解决这个问题的程序最后都会首受限于输出的复杂程度，从而导致整个程序的复杂度不可能低于 $O(n\log n)$。

??因此没有什么花里胡哨，建议直接摆烂。

??拼接式：

public class Main {

    public static void main(String[] args) {
        for (int i = 0; i < 2; i++)
            for (int j = 0; j < 2; j++)
                for (int l = 0; l < 2; l++)
                    for (int x = 0; x < 2; x++)
                        for (int y = 0; y < 2; y++) System.out.println(i + "" + j + "" + l + "" + x + "" + y);

    }
}

??十到二进制横跳：

public class Main {

    public static void main(String[] args) {
        for (int i = 0; i < 0x20; i++)
            System.out.printf("%05d%n", Integer.parseInt(Integer.toBinaryString(i)));
    }
}

??手动进制转换：

public class Main {

    public static void main(String[] args) {
        for (int i = 0; i < 0x20; i++) {
            for (int j = 4; j >= 0; j--)
                System.out.print(i >> j & 1);
            System.out.print('\n');
        }
    }
}

慢慢更

BEGIN 1? A+B问题

??考察基本语法，

??引出平台的输入输出规范。

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int a = in.nextInt(), b = in.nextInt();
        System.out.println(a + b);
    }
}

BEGIN 2? 序列求和

??考察对输出范围的敏感度。

??当 $\mathrm{n}=1E9$ 时，结果显然超出 $\mathrm{i}\mathrm{n}\mathrm{t}$ 表示范围。

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextInt();
        System.out.println((n + 1) * n / 2);
    }
}

BEGIN 3? 圆的面积

??考察是否为数盲。

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int r = in.nextInt();
        System.out.printf("%.7f", r * r * Math.PI);
    }
}

BEGIN 4? Fibonacci数列

??先挂三种最基本的写法，

??迭代式：

import java.util.Scanner;

public class Main {

    static int MOD = 10007;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] fib = new int[n + 1];
        fib[1] = 1;
        for (int i = 2; i <= n; i++)
            fib[i] = (fib[i - 1] + fib[i - 2]) % MOD;
        System.out.println(fib[n]);
    }
}

??迭代式内存优化：

import java.util.Scanner;

public class Main {

    static int MOD = 10007;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int fib = 1, fib1 = 1, fib2 = 0;
        while (n-- > 1) {
            fib = (fib1 + fib2) % MOD;
            fib2 = fib1;
            fib1 = fib;
        }
        System.out.println(fib);
    }
}

??还可以压行：

		fib1 =  fib = (fib2 + (fib2 = fib1)) % MOD;

??递归式：

import java.util.Scanner;

public class Main {

    static int MOD = 10007;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        System.out.println(fib(n));
    }

    static int fib(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        return (fib(n - 1) + fib(n - 2)) % MOD;
    }
}

还有两种对数时间的写法，现在已经凌晨了太晚了，

有时间再写。