第十届蓝桥杯国赛 Java--B组

试题 A: 递增序列(5分)

对于一个字母矩阵，我们称矩阵中的一个递增序列是指在矩阵中找到两个字母，它们在同一行，同一列，或者在同一 45 度的斜线上，这两个字母从左向右看、或者从上向下看是递增的。

例如，如下矩阵中

LANN
QIAO

有LN、LN、AN、AN、IO、AO、LQ、AI、NO、NO、AQ、IN、AN 等 13 个递增序列。注意当两个字母是从左下到右上排列时，从左向右看和从上向下看是不同的顺序。

对于下面的 30 行 50 列的矩阵，请问总共有多少个递增序列？

VLPWJVVNNZSWFGHSFRBCOIJTPYNEURPIGKQGPSXUGNELGRVZAG
SDLLOVGRTWEYZKKXNKIRWGZWXWRHKXFASATDWZAPZRNHTNNGQF
ZGUGXVQDQAEAHOQEADMWWXFBXECKAVIGPTKTTQFWSWPKRPSMGA
BDGMGYHAOPPRRHKYZCMFZEDELCALTBSWNTAODXYVHQNDASUFRL
YVYWQZUTEPFSFXLTZBMBQETXGXFUEBHGMJKBPNIHMYOELYZIKH
ZYZHSLTCGNANNXTUJGBYKUOJMGOGRDPKEUGVHNZJZHDUNRERBU
XFPTZKTPVQPJEMBHNTUBSMIYEGXNWQSBZMHMDRZZMJPZQTCWLR
ZNXOKBITTPSHEXWHZXFLWEMPZTBVNKNYSHCIQRIKQHFRAYWOPG
MHJKFYYBQSDPOVJICWWGGCOZSBGLSOXOFDAADZYEOBKDDTMQPA
VIDPIGELBYMEVQLASLQRUKMXSEWGHRSFVXOMHSJWWXHIBCGVIF
GWRFRFLHAMYWYZOIQODBIHHRIIMWJWJGYPFAHZZWJKRGOISUJC
EKQKKPNEYCBWOQHTYFHHQZRLFNDOVXTWASSQWXKBIVTKTUIASK
PEKNJFIVBKOZUEPPHIWLUBFUDWPIDRJKAZVJKPBRHCRMGNMFWW
CGZAXHXPDELTACGUWBXWNNZNDQYYCIQRJCULIEBQBLLMJEUSZP
RWHHQMBIJWTQPUFNAESPZHAQARNIDUCRYQAZMNVRVZUJOZUDGS
PFGAYBDEECHUXFUZIKAXYDFWJNSAOPJYWUIEJSCORRBVQHCHMR
JNVIPVEMQSHCCAXMWEFSYIGFPIXNIDXOTXTNBCHSHUZGKXFECL
YZBAIIOTWLREPZISBGJLQDALKZUKEQMKLDIPXJEPENEIPWFDLP
HBQKWJFLSEXVILKYPNSWUZLDCRTAYUUPEITQJEITZRQMMAQNLN
DQDJGOWMBFKAIGWEAJOISPFPLULIWVVALLIIHBGEZLGRHRCKGF
LXYPCVPNUKSWCCGXEYTEBAWRLWDWNHHNNNWQNIIBUCGUJYMRYW
CZDKISKUSBPFHVGSAVJBDMNPSDKFRXVVPLVAQUGVUJEXSZFGFQ
IYIJGISUANRAXTGQLAVFMQTICKQAHLEBGHAVOVVPEXIMLFWIYI
ZIIFSOPCMAWCBPKWZBUQPQLGSNIBFADUUJJHPAIUVVNWNWKDZB
HGTEEIISFGIUEUOWXVTPJDVACYQYFQUCXOXOSSMXLZDQESHXKP
FEBZHJAGIFGXSMRDKGONGELOALLSYDVILRWAPXXBPOOSWZNEAS
VJGMAOFLGYIFLJTEKDNIWHJAABCASFMAKIENSYIZZSLRSUIPCJ
BMQGMPDRCPGWKTPLOTAINXZAAJWCPUJHPOUYWNWHZAKCDMZDSR
RRARTVHZYYCEDXJQNQAINQVDJCZCZLCQWQQIKUYMYMOVMNCBVY
ABTCRRUXVGYLZILFLOFYVWFFBZNFWDZOADRDCLIRFKBFBHMAXX

答案提交

52800

分析

读不懂题，所以干脆把八个方向都遍历一下。
例如当前字符位于c[i][j] 那么遍历每个字符的同时，满足c[x][y] > c[i][j] 且 x > i 或 y > j （两个字母从左向右看、或者从上向下看是递增）即可

Code

public class Main {
    static int[][] move = new int[][]{{1, 0}, {0, 1}, {-1, 0}, {0, -1}, {1, 1}, {-1, -1}, {1, -1}, {-1, 1}};
    static int res = 0;

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        char[][] c = new char[60][60];
        for (int i = 1; i <= 30; i++) {
            String str = scan.next();
            for (int j = 1; j <= 50; j++) {
                c[i][j] = str.charAt(j - 1);
            }
        }

        for (int i = 1; i <= 30; i++) {
            for (int j = 1; j <= 50; j++) {
                char tmp = c[i][j];
                for (int[] ints : move) {
                    for (int x = i + ints[0], y = j + ints[1]; x >= 1 && x <= 30 && y >= 1 && y <= 50; x += ints[0], y += ints[1])
                        if (c[x][y] > tmp && (x > i || y > j))
                            res++;
                }
            }
        }
        System.out.println(res);
    }
}

试题 B: 平方拆分(5分)

将 2019 拆分为若干个两两不同的完全平方数之和，一共有多少种不同的方法？

注意交换顺序视为同一种方法，例如 132 + 252 + 352 = 2019 与 132 + 352 +252 = 2019 视为同一种方法。

答案提交

分析

跟回溯那篇文章的“组合总和”那道题有点像

回溯算法

https://cyborg2077.github.io/2022/03/20/BackTracking/

给你一个无重复元素的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的所有不同组合，并以列表形式返回。你可以按任意顺序返回这些组合。
candidates 中的同一个数字可以无限制重复被选取。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。

那么对于这道题，target 就是2019，又45 × 45 =2 025 > 2019，所以“无重复元素”的整数数组就是从0~45. 剩下的约束条件与本题也一致。

Code

public class Main {
    static LinkedList<List<Integer>> res = new LinkedList<>();
    static LinkedList<Integer> path = new LinkedList<>();

    public static void main(String[] args) {
        backTrack(0, 2019);
        System.out.println(res.size());
    }

    static void backTrack(int start, int target) {
        if (target < 0) return;
        if (target == 0) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = start; i < 45; i++) {
            path.add(i);
            backTrack(i + 1, target - i * i);
            path.removeLast();
        }
    }
}

如果按照“组合总和”那道题写，那么代码就是上面这个样子的，有很多冗余的信息，我们并不需要返回具体的方案，而是只要一个方案数，所以我们可以把代码改写成下面这样。

public class Main {
    static int res = 0;

    public static void main(String[] args) {
        backTrack(0, 2019);
        System.out.println(res);
    }

    static void backTrack(int start, int target) {
        if (target < 0) return;
        if (target == 0) {
            res++;
            return;
        }
        for (int i = start; i < 45; i++) 
            backTrack(i + 1, target - i * i);
    }
}