第十一届蓝桥杯模拟赛（一）

作者: 得力小泡泡 | 来源:发表于2020-03-27 15:15 被阅读0次

1、问题描述

1200000有多少个约数（只计算正约数）。
答案提交
　　这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

答案：96

算法分析

试除法求一个数的所有约数

时间复杂度 $O（ \sqrt n）$

Java代码

import java.util.ArrayList;
import java.util.List;

public class Main {
    public static List<Integer> get_divide(int x)
    {
        List<Integer> list = new ArrayList<Integer>();
        for(int i = 1;i <= x / i;i++)
        {
            if(x % i == 0) 
            {
                list.add(i);
                if(i != x / i) list.add(x / i);
            }
        }
        return list;
    }
    public static void main(String[] args) {
        int x = 1200000;
        List<Integer> ans = get_divide(x);
        System.out.println(ans.size());
    }
}

2、问题描述

在计算机存储中，15.125GB是多少MB？
答案提交
　　这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

答案：15488

算法分析

1GB = 1024 MB

时间复杂度 $O(1)$

Java代码

public class Main {
    public static void main(String[] args) {
        System.out.printf("%.0f",15.125 * 1024);
    }
}

3、问题描述

在1至2019中，有多少个数的数位中包含数字9？
　　注意，有的数中的数位中包含多个9，这个数只算一次。例如，1999这个数包含数字9，在计算只是算一个数。
答案提交
　　这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

答案：544

算法分析

枚举每个数的每位数是否有9

时间复杂度 $O(kn)$

Java 代码

public class Main {
    static boolean check(int x)
    {
        while(x != 0)
        {
            int t = x % 10;
            if(t == 9) return true;
            x /= 10;
        }
        return false;
    }
    public static void main(String[] args) {
        int ans = 0;
        for(int i = 1;i <= 2019;i ++)
        {
            if(check(i)) 
            {
                ans ++;
            }
        }
        System.out.println(ans);
    }
    
}

4、问题描述

一棵包含有2019个结点的树，最多包含多少个叶结点？
答案提交
　　这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

答案：2018

算法分析最多的情况是，一个父节点，其他都是子结点

5、问题描述

小明对类似于 hello 这种单词非常感兴趣，这种单词可以正好分为四段，第一段由一个或多个辅音字母组成，第二段由一个或多个元音字母组成，第三段由一个或多个辅音字母组成，第四段由一个或多个元音字母组成。
　　给定一个单词，请判断这个单词是否也是这种单词，如果是请输出yes，否则请输出no。
　　元音字母包括 a, e, i, o, u，共五个，其他均为辅音字母。
输入格式
　　输入一行，包含一个单词，单词中只包含小写英文字母。
输出格式
　　输出答案，或者为yes，或者为no。
样例输入
lanqiao
样例输出
yes
样例输入
world
样例输出
no
评测用例规模与约定
　　对于所有评测用例，单词中的字母个数不超过100。

算法分析

双指针
题目要求字符的区域顺序是：辅，元，辅，元
[i,j]区域维护的是同一片区域，找出同一块区域的个数，若区域个数是4个，则返回true，否则返回false
注意：需要对第一个字母进行特判，若第一个字母是元音，则直接返回false

时间复杂度 $O(n)$

Java 代码

//机器人判分系统要求必须如下规则：
// 1： 不能有package关键字
// 2： 必须类名必须是Main

import java.util.Scanner;

public class Main {
    static char[] temp;
    static int n ;
    //判断a和b是否是同一种类型的字母
    static boolean check2(char a,char b)
    {
        boolean flag1 = false;
        boolean flag2 = false;
        if(a == 'a' || a == 'e' || a == 'i' || a == 'o' || a == 'u') flag1 = true;
        if(b == 'a' || b == 'e' || b == 'i' || b == 'o' || b == 'u') flag2 = true;
        if((flag1 && flag2) || (!flag1 && !flag2)) return true;
        return false;
    }
    static boolean check()
    {
        if(temp[0] == 'a' || temp[0] == 'e' || temp[0] == 'i' || temp[0] == 'o' || temp[0] == 'u')
            return false;
        int cnt = 1;
        for(int i = 1,j = 0;i < n;i ++)
        {
            if(!check2(temp[i],temp[j]))
            {
                cnt ++;
                j = i;
            }
        }
        if(cnt == 4) return true;
        return false;
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        temp = scan.next().toCharArray();
        n = temp.length;
        if(check()) System.out.println("yes");
        else System.out.println("no");
    }
    
}

6、问题描述

在数列 a[1], a[2], ..., a[n] 中，如果对于下标 i, j, k 满足 0<i<j<k<n+1 且 a[i]<a[j]<a[k]，则称 a[i], a[j], a[k] 为一组递增三元组，a[j]为递增三元组的中心。
　　给定一个数列，请问数列中有多少个元素可能是递增三元组的中心。
输入格式
　　输入的第一行包含一个整数 n。
　　第二行包含 n 个整数 a[1], a[2], ..., a[n]，相邻的整数间用空格分隔，表示给定的数列。
输出格式
　　输出一行包含一个整数，表示答案。
样例输入
5
1 2 5 3 5
样例输出
2
样例说明
　　a[2] 和 a[4] 可能是三元组的中心。
评测用例规模与约定
　　对于 50% 的评测用例，2 <= n <= 100，0 <= 数列中的数 <= 1000。
　　对于所有评测用例，2 <= n <= 1000，0 <= 数列中的数 <= 10000。

算法分析

从左到右枚举所有元素，若当前元素的左边存在比该元素小且右边存在比该元素大，则表示该元素可能是递增三元组的中心

时间复杂度 $O(n^2)$

Java代码

//机器人判分系统要求必须如下规则：
// 1： 不能有package关键字
// 2： 必须类名必须是Main

import java.util.Scanner;

public class Main {
    static int N = 1010;
    static int[] a = new int[N];
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        for(int i = 0;i < n;i ++)
        {
            a[i] = scan.nextInt();
        }
        int res = 0;
        for(int i = 1;i < n - 1;i ++)
        {
            boolean flag1 = false;
            for(int j = 0;j < i;j ++)
            {
                if(a[j] < a[i]) 
                {
                    flag1 = true;
                    break;
                }
            }
            boolean flag2= false;
            for(int j = i + 1;j < n;j ++)
            {
                if(a[j] > a[i]) 
                {
                    flag2 = true;
                    break;
                }
            }
            if(flag1 && flag2) res ++;
        }
        System.out.println(res);
    }
    
}

7、问题描述

一个正整数如果任何一个数位不大于右边相邻的数位，则称为一个数位递增的数，例如1135是一个数位递增的数，而1024不是一个数位递增的数。
　　给定正整数 n，请问在整数 1 至 n 中有多少个数位递增的数？
输入格式
　　输入的第一行包含一个整数 n。
输出格式
　　输出一行包含一个整数，表示答案。
样例输入
30
样例输出
26
评测用例规模与约定
　　对于 40% 的评测用例，1 <= n <= 1000。
　　对于 80% 的评测用例，1 <= n <= 100000。
　　对于所有评测用例，1 <= n <= 1000000。

算法1

从1到n，暴力枚举每个数，判断该数是否符合任何一个数位不大于右边相邻的数位，

时间复杂度 $O(n * k)$

k表示最大的数的长度

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    static boolean check(int x)
    {
        List<Integer> nums = new ArrayList<Integer>();
        while(x != 0)
        {
            nums.add(x % 10);
            x /= 10;
        }
        boolean flag = true;//默认是符合的
        for(int i = nums.size() - 1;i >= 1;i --)
        {
            if(nums.get(i) > nums.get(i - 1))
            {
                flag = false;
                break;
            }
        }
        if(flag) return true;
        return false;
            
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int ans = 9;
        for(int i = 10;i <= n;i ++)
        {
            if(check(i)) ans ++;
        }
        System.out.println(ans);
    }
}

算法2

数位dp
f[i][j]表示一共有i位，且最高位填j的数的个数，先预处理f[][]数组，直接求出1到n有多少个递增的数

时间复杂度 $O(9 * k + 9 ^ 3)$

k表示最大的数的长度

Java代码


//机器人判分系统要求必须如下规则：
// 1： 不能有package关键字
// 2： 必须类名必须是Main

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    static int N  = 15;
    static int[][] f = new int[N][N];
    static void init()
    {
        //f[i][j]表示一共有i位，且最高位填j的数的个数
        for(int i = 0;i <= 9;i ++) f[1][i] = 1;
        
        for(int i = 2;i < N;i ++)
            for(int j = 0;j <= 9;j ++)
                for(int k = j;k <= 9;k ++)
                {
                    f[i][j] += f[i - 1][k];
                }
    }
    static int dp(int n)
    {
        if(n == 0) return 1;
        
        List<Integer> nums = new ArrayList<Integer>();
        while(n != 0)
        {
            nums.add(n % 10);
            n /= 10;
        }
        int res = 0;
        int last = 0;//记录前一个位的数
        for(int i = nums.size() - 1;i >= 0;i --)
        {
            int x = nums.get(i);
            for(int j = last;j < x;j ++) res += f[i + 1][j];
            
            if(x < last) break;
            
            last = x;
            
            if(i == 0) res ++;
            
        }
        return res;
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        init();
        int n = scan.nextInt();
        System.out.println(dp(n) - dp(0));
        
    }
}

8、问题描述

小明想知道，满足以下条件的正整数序列的数量：
　　1. 第一项为 n；
　　2. 第二项不超过 n；
　　3. 从第三项开始，每一项小于前两项的差的绝对值。
　　请计算，对于给定的 n，有多少种满足条件的序列。
输入格式
　　输入一行包含一个整数 n。
输出格式
　　输出一个整数，表示答案。答案可能很大，请输出答案除以10000的余数。
样例输入
4
样例输出
7
样例说明
　　以下是满足条件的序列：
　　4 1
　　4 1 1
　　4 1 2
　　4 2
　　4 2 1
　　4 3
　　4 4
评测用例规模与约定
　　对于 20% 的评测用例，1 <= n <= 5；
　　对于 50% 的评测用例，1 <= n <= 10；
　　对于 80% 的评测用例，1 <= n <= 100；
　　对于所有评测用例，1 <= n <= 1000。

算法1

暴力通过50%
1、第二项从1枚举到n，从第三项开始的每一项均小于前两项的差的绝对值
2、用全局变量记录总方案数，每dfs一遍方案数加1，dfs(pre,cur)表示的是前一个数是pre，当前数是cur的所有情况

时间复杂度（指数级别）

Java代码（暴力写法）

import java.util.Scanner;

public class Main {
    static int ans = 0;
    static int mod = 10000;
    //x表示前一项，y表示当前项
    static void dfs(int x,int y)
    {
        ans = (ans + 1) % mod;
        if(Math.abs(x - y) <= 1) return;
        for(int i = 1;i < Math.abs(x - y);i ++)
        {
            dfs(y,i);
        }
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        for(int i = 1;i <= n;i ++)
        {
            dfs(n,i);
        }
        System.out.println(ans);
    }
}

算法2

记忆化搜索通过80%

从算法1可以看到由于每次递归都会重复计算相同的值，导致时间复杂度爆炸。因为当某个数字数列的前面两个数字确定的情况下数字序列的方案数是一样且确定的，因此该问题是个无后效性问题，所以可以对算法1进行改进，用一个数组记录每次求得的结果,因为这题的状态定义比较特殊，所以采用记忆化搜索的方式来实现

时间复杂度 $O(n^3)$

Java代码

import java.util.Scanner;

public class Main {
    static int N = 1010;
    static int mod = 10000;
    static int[][] f = new int[N][N];
    static int dfs(int pre,int cur)
    {
        if(f[pre][cur] != 0) return f[pre][cur];
        
        f[pre][cur] = 1;
        for(int i = 1;i < Math.abs(pre - cur);i ++)
            f[pre][cur] = (f[pre][cur] + dfs(cur,i)) % mod;
        
        return f[pre][cur];
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int res = 0;
        for(int i = 1;i <= n;i ++) res = (res + dfs(n,i)) % mod;
        System.out.println(res);
    }
}

其实到这里，对于骗分选手来说已经可以开始骗到满分了，虽然说算法2记忆化搜索到1000的时候会超时，可通过打表的方式，把1到1000全部打出来，放在一个数组中，就可以实现骗分了

骗分的代码

import java.util.Scanner;

public class Main {
    static int N = 1010;
    static int[] ans = new int[] {0,1,2,4,7,14,26,53,106,220,452,946,1967,4128,8638,8144,8068,26,8127,3542,3277,3278,7643,5433,5774,8217,4846,687,3097,6887,3556,4840,3454,5378,722,2230,767,1447,1839,4776,7618,7831,6222,5236,7802,5696,1835,1102,9537,1605,1227,3034,2159,1613,6811,3941,6794,5960,4903,75,2158,349,4258,5189,4717,2894,4193,2890,258,2928,6125,2913,1482,8419,7244,1652,3440,2138,9272,4714,3333,3543,8834,6763,9180,1803,4631,6307,9056,3170,8339,6213,1176,3258,272,4257,1893,8020,3682,9531,6961,4145,3086,3455,9057,1346,5768,6907,247,2450,4732,8653,8229,842,3346,9671,7106,3561,4952,9539,1791,6208,6083,8838,7474,6854,198,7300,8219,5912,8884,3976,9650,4821,7317,9720,5572,3834,6326,2281,34,8409,28,445,8155,9846,9944,2504,3954,1639,7243,8502,6926,1609,7449,3769,5695,6683,7531,6275,5827,6184,1982,736,9718,2777,7688,6626,7456,961,5556,7573,6886,4543,3957,2859,4666,9795,305,9052,5350,9827,5445,6970,2599,7566,2848,2987,5179,1537,2392,6375,9621,7376,3301,1357,6545,7838,9390,4284,2631,1814,2566,7666,1110,5694,7595,5000,1290,4735,5994,9401,6475,9012,5877,2867,7912,3509,5505,885,7490,5622,4374,8721,5134,8788,5430,3869,9852,5762,75,5964,262,5565,1599,7525,5388,8612,1143,7938,7580,2953,7901,5629,1456,9852,5216,965,3739,7879,1212,9029,9263,9609,1926,8151,1997,6298,5125,5715,4864,3852,604,7652,313,6248,4077,3875,3816,7046,9525,3798,6959,9366,2216,4463,6546,6367,614,9477,3176,4098,7162,7535,4696,749,2686,8212,9050,255,1389,287,1086,9414,9897,2293,31,9121,4682,7084,8951,834,1051,2236,3712,6426,8642,185,785,8162,6015,658,8923,5741,2551,7629,2095,8882,7695,5629,8684,5116,6362,7701,9441,9403,1108,4395,5688,9466,953,9191,4967,7236,6020,3465,8165,872,4530,3353,7859,1422,1504,6366,126,1246,1530,1777,8970,4590,2195,6920,9086,689,2163,6035,4961,2055,7699,4121,3971,1824,3707,4405,854,6088,6971,1679,1779,7097,5696,2449,2104,3264,796,8595,6183,26,5597,7295,5926,9039,4550,9601,5959,3244,7451,5641,2343,6587,3755,4361,3890,446,8187,1979,7000,7094,8658,1647,6090,8332,4407,4570,2340,3057,5029,5424,2736,4844,2771,5782,5912,3745,2504,2782,7247,1393,5403,7175,9903,1723,7600,7021,4566,9778,5188,46,8542,7915,5043,4983,519,480,8199,1141,73,9316,6248,966,3218,6614,6974,5078,9775,7263,6263,7267,1947,5357,286,674,3876,1985,4731,1850,512,1493,5310,5443,4183,5963,8642,1389,6320,4264,9565,7348,4378,6192,1300,3393,4794,8323,6063,9651,9368,7899,9053,4933,5140,5604,9114,9299,7603,2485,884,7313,4139,9883,1405,9843,7419,1483,2031,8610,4150,3313,6257,3790,1688,994,1357,9660,583,5735,1548,7156,9678,8047,3617,9611,7966,7764,5177,7716,4206,7985,6989,6318,5854,8292,9639,687,370,3252,7104,5813,758,8219,3809,2506,3605,9340,3559,4118,4757,8229,4258,944,1596,4940,622,5832,1270,6948,1744,1125,7895,9348,7601,7426,1975,9611,3722,4143,4979,7904,3221,3817,5755,1798,6549,3463,3190,201,6894,6209,3488,670,7643,7020,6164,5583,5036,6309,8644,7961,3465,7795,1486,4535,3111,5252,4049,4253,7515,1517,6148,2438,1296,8826,7924,7761,9126,6951,7110,7549,1170,8533,793,1633,6451,6261,5887,8694,6447,8993,6398,1289,2925,2362,3935,6744,1358,1743,3937,9942,3696,1601,8295,3086,2595,9554,8566,1465,2109,3474,3950,9216,8948,2020,3536,943,4934,8377,6171,1243,3525,259,3001,4205,4548,4754,2365,8630,4690,7872,5131,3995,2672,728,6532,9785,9379,5865,4774,6660,3721,4451,9085,4771,8008,857,9737,5630,4040,3106,5997,4152,8542,3992,3294,5064,2656,5247,635,1521,3026,1502,9396,2171,7188,2425,9758,2640,8648,9454,274,9471,8972,9301,911,6023,4155,126,7802,2948,5675,6313,69,1374,9925,3685,6901,432,1884,4803,8173,9638,3626,695,4286,3836,8670,8834,1444,5187,6281,2482,8801,7656,9066,5138,5160,9857,906,5235,7243,5281,5103,5826,5023,3637,5607,1204,5697,3422,1192,8753,6087,2083,3256,8201,9853,1886,3953,4732,7351,6387,9148,2299,4843,3891,3572,874,9873,1235,7323,8860,3439,113,5132,6521,1234,7427,4062,1342,2480,641,8802,9788,5336,3649,1301,3268,749,1628,9202,2689,3284,9170,5252,1577,1705,5640,2185,2252,4943,271,5117,8699,2743,8221,2119,3851,701,2740,4247,7037,9764,4445,5848,6135,6166,5328,2584,1131,3005,8817,2783,7749,6112,5567,9688,2549,7929,8650,60,1896,3998,7345,3352,8990,1143,873,1191,5821,9485,5249,3086,8016,9319,4139,3566,8871,7528,7873,4117,1085,7064,8222,5947,4447,1326,5206,12,9703,5711,3951,219,6966,3168,2372,9603,9092,1904,1010,2704,2106,7568,3410,296,6825,9781,637,4465,7953,6861,2142,2035,9743,1921,3051,7424,7112,7676,5245,9531,2284,4498,6423,6977,3106,1367,5696,2003,1291,3025,76,3147,9094,4580,5097,7390,8637,5853,359,3153,4957,6635,5721,3353,2266,3481,7432,3020,7330,1172,5285,1525,2928,5331,8856,2163,5169,1465,4439,1876,7446,2192,5577,726,6599,352,3645,7733,8331,5447,8017,5017,7287,6602,7248,6323,4195,9617,2263,4013,450,4073,6131,3569,9019,1858,9827,8118,4972,7422,9666,5760,9213,2817,7952,3948,8683,3645,6402,3264,1919,9276,2519,190,766,8940,3413,2644,8048,83,9724,7009,3777,9663,2483,5752,4578,8951,5902,2170,9967,894,8556,6049,7254,2746,8962,8317,6848,767,7907,1028,9458,6881,4978,6717,8210,3835,1064,7434,746,9449
};
        public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        System.out.println(ans[n]);
    }
}

算法3

算法分析

在记忆化搜索的前提下进一步优化，把下面这行优化掉，每次都需要从小到到枚举，因此用利用前缀和的思想进一步优化

for(int i = 1;i < Math.abs(pre - cur);i ++)
            f[pre][cur] = (f[pre][cur] + dfs(cur,i)) % mod;

image.png

满分代码

import java.util.Scanner;

public class Main {
    static int N = 1010;
    static int mod = 10000;
    static int[][] f = new int[N][N];
    static int dfs(int pre,int cur)
    {
        if(cur <= 0) return 0;
        if(f[pre][cur] != 0) return f[pre][cur];
        return f[pre][cur] = (1 + dfs(pre,cur - 1) + dfs(cur,Math.abs(pre - cur) - 1)) % mod;
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        dfs(n,n);
        System.out.println(f[n][n]);
    }
}

9、问题描述

小明有一块空地，他将这块空地划分为 n 行 m 列的小块，每行和每列的长度都为 1。
　　小明选了其中的一些小块空地，种上了草，其他小块仍然保持是空地。
　　这些草长得很快，每个月，草都会向外长出一些，如果一个小块种了草，则它将向自己的上、下、左、右四小块空地扩展，这四小块空地都将变为有草的小块。
　　请告诉小明，k 个月后空地上哪些地方有草。
输入格式
　　输入的第一行包含两个整数 n, m。
　　接下来 n 行，每行包含 m 个字母，表示初始的空地状态，字母之间没有空格。如果为小数点，表示为空地，如果字母为 g，表示种了草。
　　接下来包含一个整数 k。
输出格式
　　输出 n 行，每行包含 m 个字母，表示 k 个月后空地的状态。如果为小数点，表示为空地，如果字母为 g，表示长了草。
样例输入
4 5
.g...
.....
..g..
.....
2
样例输出
gggg.
gggg.
ggggg
.ggg.
评测用例规模与约定
　　对于 30% 的评测用例，2 <= n, m <= 20。
　　对于 70% 的评测用例，2 <= n, m <= 100。
　　对于所有评测用例，2 <= n, m <= 1000，1 <= k <= 1000。

算法分析

bfs
初始把所有草的位置加到队列中，枚举k轮队列的所有的元素，通过bfs遍历，把四周的空地更新成草，更新了草的位置继续加到队列中，为下一轮更新准备

时间复杂度 $O(nm)$

Java代码

//机器人判分系统要求必须如下规则：
// 1： 不能有package关键字
// 2： 必须类名必须是Main

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static int N = 1010;
    static int n,m;
    static int k;
    static char[][] g = new char[N][N];
    static int[] dx = new int[] {0,-1,0,1};
    static int[] dy = new int[] {-1,0,1,0};
    static void bfs()
    {
        Queue<Pair> q = new LinkedList<Pair>();
        for(int i = 0;i < n;i ++)
            for(int j = 0;j < n;j ++)
            {
                if(g[i][j] == 'g') q.add(new Pair(i,j));
            }
        int cnt = 0;
        while(!q.isEmpty())
        {
            cnt ++;
            if(cnt > k) break;
            int num = q.size();
            for(int u = 0;u < num;u ++)
            {
                Pair t = q.poll();
                for(int i = 0;i < 4;i ++)
                {
                    int a = t.x + dx[i];
                    int b = t.y + dy[i];
                    if(a < 0 || a >= n || b < 0 || b >= m) continue;
                    if(g[a][b] == 'g') continue;
                    g[a][b] = 'g';
                    q.add(new Pair(a,b));
                }
            }
        }
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        m = scan.nextInt();
        for(int i = 0;i < n;i ++)
        {
            char[] temp = scan.next().toCharArray();
            for(int j = 0;j < m;j ++)
            {
                g[i][j] = temp[j];
            }
        }
        k = scan.nextInt();
        
        bfs();
        
        for(int i = 0;i < n;i ++)
        {
            for(int j = 0;j < m;j ++)
            {
                System.out.print(g[i][j]);
            }
            System.out.println();
        }
    }
}
class Pair
{
    int x,y;
    Pair(int x,int y)
    {
        this.x = x;
        this.y = y;
    }
}

10、问题描述

小明要组织一台晚会，总共准备了 n 个节目。然后晚会的时间有限，他只能最终选择其中的 m 个节目。
　　这 n 个节目是按照小明设想的顺序给定的，顺序不能改变。
　　小明发现，观众对于晚上的喜欢程度与前几个节目的好看程度有非常大的关系，他希望选出的第一个节目尽可能好看，在此前提下希望第二个节目尽可能好看，依次类推。
　　小明给每个节目定义了一个好看值，请你帮助小明选择出 m 个节目，满足他的要求。
输入格式
　　输入的第一行包含两个整数 n, m ，表示节目的数量和要选择的数量。
　　第二行包含 n 个整数，依次为每个节目的好看值。
输出格式
　　输出一行包含 m 个整数，为选出的节目的好看值。
样例输入
5 3
3 1 2 5 4
样例输出
3 5 4
样例说明
　　选择了第1, 4, 5个节目。
评测用例规模与约定
　　对于 30% 的评测用例，1 <= n <= 20；
　　对于 60% 的评测用例，1 <= n <= 100；
　　对于所有评测用例，1 <= n <= 100000，0 <= 节目的好看值 <= 100000。

算法分析

1、有两个数组，一个是a[]数组，表示初始的数组，一个是b[]数组，表示a[]数组排序后的数组
2、从b[]数组中找出前m大，扔到set中，再从前往后枚举a[]数组，若枚举的当前元素，set中有，则输出
注意：
1、set.contain的函数的复杂度是 $O(1)$ ，因此枚举的时候不会产生开销
2、不知道有没有可能存在多个相同的好看值，为了保险起见，设前m大最下的元素是x，需要记录x在前m大中有多少个

时间复杂度 $O(nlogn)$

Java 代码

//机器人判分系统要求必须如下规则：
// 1： 不能有package关键字
// 2： 必须类名必须是Main

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class Main {
    static int N = 100010;
    static int[] a = new int[N];
    static int[] b = new int[N];
    static Set<Integer> set = new HashSet<Integer>();
    static int[] ans = new int[N];
    static int k = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s1 = br.readLine().split(" ");
        int n = Integer.parseInt(s1[0]);
        int m = Integer.parseInt(s1[1]);
        String[] s2 = br.readLine().split(" ");
        for(int i = 1;i <= n;i ++)
        {
            a[i] = Integer.parseInt(s2[i - 1]);
            b[i] = a[i];
        }
        Arrays.sort(b,1,n + 1);
        for(int i = n;i >= n - m + 1;i --)
        {
            set.add(b[i]);
        }
        int last = b[n - m + 1];
        int cnt = 0;
        //判断最小的元素用到多少个
        for(int i = n - m + 1;i <= n;i ++)
        {
            if(b[i] == last) cnt ++;
        }
        
        for(int i = 1;i <= n;i ++)
        {
            if(set.contains(a[i]))
            {
                if(a[i] == last)
                {
                    if(cnt <= 0) continue;
                    cnt --;
                }
                ans[k ++] = a[i];
            }
        }
        for(int i = 0;i < k;i ++)
        {
            if(i != k - 1) System.out.print(ans[i] + " ");
            else System.out.println(ans[i]);
        }
        
    }
}

第十一届蓝桥杯模拟赛（一）

1、问题描述

答案：96

算法分析

时间复杂度

Java代码

2、问题描述

答案：15488

算法分析

时间复杂度

Java代码

3、问题描述

答案：544

算法分析

时间复杂度

Java 代码

4、问题描述

答案：2018

算法分析 最多的情况是，一个父节点，其他都是子结点

5、问题描述

算法分析

时间复杂度

Java 代码

6、问题描述

算法分析

时间复杂度

Java代码

7、问题描述

算法1

时间复杂度

算法2

时间复杂度

Java代码

8、问题描述

算法1

时间复杂度（指数级别）

Java代码（暴力写法）

算法2

时间复杂度

Java代码

其实到这里，对于骗分选手来说已经可以开始骗到满分了，虽然说算法2记忆化搜索到1000的时候会超时，可通过打表的方式，把1到1000全部打出来，放在一个数组中，就可以实现骗分了

骗分的代码

算法3

算法分析

满分代码

9、问题描述

算法分析

时间复杂度

Java代码

10、问题描述

算法分析

时间复杂度

Java 代码

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

时间复杂度 $O（ \sqrt n）$

时间复杂度 $O(1)$

时间复杂度 $O(kn)$

算法分析最多的情况是，一个父节点，其他都是子结点

时间复杂度 $O(n)$

时间复杂度 $O(n^2)$

时间复杂度 $O(n * k)$

时间复杂度 $O(9 * k + 9 ^ 3)$

时间复杂度 $O(n^3)$

时间复杂度 $O(nm)$

时间复杂度 $O(nlogn)$