算法刷题笔记——“蓝桥杯“819题：递增序列 (国赛)

╰半橙微兮° 2024-03-23 16:49 19阅读 0赞

#### 题目描述 [链接][Link 1] ####

**本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。**

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

例如，如下矩阵中

LANN
    QIAO

有**LN、LN、AN、AN、IO、AO、LQ、AI、NO、NO、AQ、IN、ANLN、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

#### 运行限制 ####

*  最大运行时间：1s
 *  最大运行内存: 128M

#### 解法： ####

①首先，把获取到的 30 行 50 列的矩阵存入**二维数组**中去。

②分析问题给出的案例，发现只有五种情况来比较的：**同行向右、同列向下、右下、右上、左下**。

③该题是问答题，我们再不优化的前提下，可以直接**暴力循环**求解。

**代码：**

public class IncreSequence{
    
        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            int n = 30, m = 50;
            char[][] matrix = new char[n][m];
            for (int i = 0; i < n; i++) {
                String line = scanner.next();
                for (int j = 0; j < m; j++) {
                    matrix[i][j] = line.charAt(j);
                }
            }
            int count = countIncreasingSequences(matrix);
            System.out.println(count);
        }
        public static int countIncreasingSequences(char[][] matrix) {
            int n = 30, m = 50;
            int res = 0;
            //只有 同行向右、同列向下、右下、右上、左下 五种情况
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    int temp = matrix[i][j];//这个很关键，是我们每次比较的“参考值”
                    //同一行
                    for (int k = j + 1; k < m; k++) {
                        if (temp < matrix[i][k]) {
                            res++;
                        }
                    }
                    //同一列
                    for (int k = i + 1; k < n; k++) {
                        if (temp < matrix[k][j])
                            res++;
                    }
                    //右下   l1表示x轴变化，l2表示y轴变化
                    for (int l1 = i + 1, l2 = j + 1; l1 < n && l2 < m; l1++, l2++) {
                        if (temp < matrix[l1][l2])
                            res++;
                    }
                    //左下
                    for (int l1 = i + 1, l2 = j - 1; l1 < n && l2 >= 0; l1++, l2--) {
                        if (temp < matrix[l1][l2])
                            res++;
                    }
                    //右上
                    for (int l1 = i - 1, l2 = j + 1; l1 >= 0 && l2 < m; l1--, l2++) {
                        if (temp < matrix[l1][l2])
                            res++;
                    }
                }
            }
            return res;
        }
    }

对于上述，将输入的**矩阵**转换成**二维数组**的方法，我发现如下代码，对其做**优化:**

public class IncreSequence {
        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            int m = 30, n = 50;
            char array[][] = new char[m][n];
            for (int i = 0; i < m; i++) {
                char st[] = scanner.nextLine().toCharArray();
                array[i] = st;
            }
            //打印一下 看一下“储存结果”
            for (int i = 0; i < 30; i++) {
                for (int j = 0; j < 50; j++) {
                    System.out.print(array[i][j]);
                }
                System.out.println();
            }
        }
    }

这道题解法就到这啦，最后答案是：**52800** （[参考解法和题目均来自蓝桥杯杯赛专区][Link 1]）

觉得不错的话，点个赞吧~

[Link 1]: https://www.lanqiao.cn/problems/819/learning/?page=1&first_category_id=1&sort=students_count&second_category_id=3