目录

试题A.空间

试题B.卡片

试题C.直线

试题D.货物摆放

试题E.路径

试题F.时间显示

试题G.砝码称重

试题H.杨辉三角形

试题I.双向排序 

试题J.括号序列 

总结：

试题A.空间

1 b=8 Byte （1位即为1Byte）

1Kb=1024b

1Mb=1024Kb

public class lanqiao {
    public static void main(String[] args) {
        long Mb=256;
        long Kb=1024;
        long b=1024;
        long Byte=8;
        System.out.println(Mb*Kb*b*Byte/32);
    }
}

答案：67108864

试题B.卡片

 比较简单，记得测试样例

import java.util.Arrays;

public class lanqiao {
    private int[] a;
    public static void main(String[] args) {
        int a[]=new int[10];
        Arrays.fill(a,2021);
        for(int i=1;;i++)
        {
            int t=i;
            while(t>0)
            {
                int temp=t%10;
                t=t/10;
                a[temp]--;
                if(a[temp]==0)
                {
                    System.out.println(i);
                    return ;
                }
            }
        }
    }
}

答案：3181

试题C.直线

import java.util.*;

public class lanqiao {

    public static void main(String[] args) {
        HashSet kb=new HashSet();
        int x=0;//横坐标
        int y=0;//纵坐标
        HashSet a1=new HashSet<>();
        for(x=0;x<20;x++)
        {
            for(y=0;y<21;y++)
            {
                a1.add(x*100+y);//  (x*100+y)/100即为横坐标 (x*100+y)%100即为纵坐标 想
            }                   //   x,y皆未小于100的数
        }
        List arr=new ArrayList<>(a1);
        for(int i=0;i 
1.利用  z=x*100+y 来存储x,y   x=z/100,y=z%100  
 
2.java中用double类型存小数不准确，此题用分数形式存储
 
3.将多个数据组合用String类型存储，再利用set去重。String类型进行比较时，只有每个字符都相同时，才会默认为相同，所以不用再考虑其中的分子分母是否相等等问题
 
4.注意要约分，利用最大公因数函数
 
答案：40257
 
试题D.货物摆放 
 
 
import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.*;

public class lanqiao {

    public static void main(String[] args) {
        long n=2021041820210418l;
        long a[]=new long[1000000];
        int ans=0;
        long temp=n;
        for(long i=1l;i 
1.题目中给的大数在java中用long即可存储，不必使用BigInteger
 
2.若直接使用暴力三重循环，计算量太大，算不出结果
 
正确思路为将因子保存下来，二重循环计算
 
3.在寻找因子时要进行优化 若x为n的因子，则n/x也为x的因子
 
答案：2430
 
试题E.路径 
 
import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.*;

public class lanqiao {

    public static void main(String[] args) {
        int n=2021;
        int g[][]=new int[2510][2510];
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(i!=j)
                {
                    if(Math.abs(i-j)<=21)
                    {
                        g[i][j]=lcm(i,j);
                        g[j][i]=lcm(i,j);
                    }
                    else
                    {
                        g[i][j]=g[j][i]=100000000;
                    }
                }
            }
        }
        System.out.println(dis(g));
    }
    static int gcd(int a,int b)
    {
        return b>0? gcd(b,a%b):a;
    }
    static int lcm(int a,int b)
    {
        return a*b/gcd(a,b);
    }
    static int dis(int g[][])
    {
        int N=2510;
        int dist[]=new int[N];
        int st[]=new int[N];
        int n=2021;
        Arrays.fill(dist,1000000000);
        dist[1]=0;
        for(int i=1;i<=n;i++)
        {
            int t=-1;
            for(int j=1;j<=n;j++)
            {
                if(st[j]==0&&(t==-1||dist[j](dist[t]+g[t][j]))
                {
                    dist[j]=dist[t]+g[t][j];
                }
            }
        }
        return dist[n];
    }
}
 
迪杰斯特拉模板题
 
 答案：10266837
 
试题F.时间显示 
 
 
 
【样例输入 1】
 46800999
 【样例输出 1】
 13:00:00
 【样例输入 2】
 1618708103123
 【样例输出 2】
 01:08:23
 【评测用例规模与约定】
 对于所有评测用例，给定的时间为不超过 1018 的正整数。 
 
 
 答案：
 
import java.math.BigDecimal;
import java.math.BigInteger;
import java.text.DecimalFormat;
import java.util.*;

public class lanqiao {

    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        long n=in.nextLong();
        n=(n/1000)%86400;
        int hour= (int) (n/3600);
        int minute= (int) ((n%3600)/60);
        int second= (int) (n-hour*3600-minute*60);
        DecimalFormat df=new DecimalFormat("00");
        System.out.println(df.format(hour)+":"+df.format(minute)+":"+df.format(second));
    }
}
 
java中long的范围为：-9223372036854775808到9223372036854775807
 
所以此题用long即可
 
试题G.砝码称重 
 
 
 
 
 
【样例输入】
 3
 1 4 6
 【样例输出】
 10
 【样例说明】
 能称出的 10 种重量是：1、2、3、4、5、6、7、9、10、11。
 1 = 1；
 2 = 6 6 4 (天平一边放 6，另一边放 4)；
 3 = 4 1；
 4 = 4；
 5 = 6 1；
 6 = 6；
 7 = 1 + 6；
 9 = 4 + 6 1；
 10 = 4 + 6；
 11 = 1 + 4 + 6。
 
 
【评测用例规模与约定】
 对于 50% 的评测用例，1 ≤ N ≤ 15。
 对于所有评测用例，1 ≤ N ≤ 100，N 个砝码总重不超过 100000。
 
 
闫氏dp分析法
 
 
答案： 
 
 
import java.math.BigDecimal;
import java.math.BigInteger;
import java.text.DecimalFormat;
import java.util.*;

public class lanqiao {

    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        int n=in.nextInt();
        //dp[i][j]表示前i个砝码，称出j的集合，值为bool值，能称出j就true
        boolean dp[][]=new boolean[110][1000000];
        int a[]=new int[101];
        int m=0;
        for(int i=1;i<=n;i++)
        {
            a[i]=in.nextInt();
            m+=a[i];
        }
        dp[0][0]=true;
        for(int i=1;i<=n;i++)//前i个
        {
            for(int j=0;j<=m;j++)//称出j
            {
                dp[i][j]=dp[i-1][j]||dp[i-1][j+a[i]]||dp[i-1][Math.abs(j-a[i])];
                //只要有一种情况为真，那么dp[i][j]就真
            }
        }
        int ans=0;
        for(int i=1;i<=m;i++)
        {
            if(dp[n][i])
            {
                ans++;
            }
        }
        System.out.println(ans);
    }
}
 
 试题H.杨辉三角形 
 
 
 
 【样例输入】
 6
 【样例输出】
 13
 【评测用例规模与约定】
 对于 20% 的评测用例，1 ≤ N ≤ 10；
 对于所有评测用例，1 ≤ N ≤ 1000000000。
 
 
 遍历：数据达不到，骗分来的，没找到好的解决办法~~~
 
节省时间的话，直接枚举1-10
 
import java.math.BigDecimal;
import java.math.BigInteger;
import java.text.DecimalFormat;
import java.util.*;

public class lanqiao {

    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        int n=in.nextInt();
        long arr[][]=new long[100000][100000];
        for(int i=0;i
 
试题I.双向排序  
 
 
 
【样例输入】
 3 3
 0 3
 1 2
 0 2
 【样例输出】
 3 1 2
 【样例说明】
 原数列为 (1, 2, 3)。 第 1 步后为 (3, 2, 1)。 第 2 步后为 (3, 1, 2)。 第 3 步后为 (3, 1, 2)。与第 2 步操作后相同，因为前两个数已经是降序了。 
 
 
【评测用例规模与约定】
 对于 30% 的评测用例，n, m ≤ 1000；
 对于 60% 的评测用例，n, m ≤ 5000；
 对于所有评测用例，1 ≤ n, m ≤ 100000，0 ≤ ai ≤ 1，1 ≤ bi ≤ n。
 
 
直接用sort函数排序可得到一部分分数。
 
完整实现可看y总的讲解 。
 
第十二届蓝桥杯C++ B组讲解_哔哩哔哩_bilibili
 
试题J.括号序列  
 
 
 
【样例输入】
 ((()
 【样例输出】
 5
 【评测用例规模与约定】
 对于 40% 的评测用例，|s| ≤ 200。
 对于所有评测用例，1 ≤ |s| ≤ 5000。 
 
 
 答案：
 
dfs暴力骗分版本：
 
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class J括号序列 {
    
    static Set set = new HashSet<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        int left = 0;
        int right = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                left++;
            } else {
                right++;
            }
        }
        //int count = Math.max(left, right);
        int count;//最多的括号数量
        int sub;//插入的括号不能超过sub个,也就是不一样的括号数量
        if (left > right) {
            count = left;
            sub = left - right;
        } else {
            count = right;
            sub = right - left;
        }

        String temp = "";
        for (int i = 0; i < count; i++) {
            temp += "()";
        }
        dfs(temp);
        System.out.println(set);

        int resCount = 0;

        for (String s1 : set) {
            int i = 0;
            int j = 0;
            boolean isMatch = true;
            while (i < s.length() && j < s1.length()) {
                int tempCount = sub;
                if (s.charAt(i) == s1.charAt(j)) {
                    i++;
                    j++;
                } else {
                    j++;
                    tempCount--;
                }
                if (tempCount < 0) {
                    isMatch = false;
                    break;
                }
            }
            if (isMatch) {
                resCount++;
            }
        }

        System.out.println(resCount);
    }

    private static void dfs(String temp) {
        set.add(temp);
        for (int i = 0; i < temp.length() - 1; i++) {
            if (temp.charAt(i) == ')' && temp.charAt(i + 1) == '(') {
                String temps = temp.substring(0, i) + "()" + temp.substring(i + 2, temp.length());
                dfs(temps);
            }
        }
    }
}
 
总结： 
这次比赛更加注重算法和细节了
 
前面程序填空的直线题，最开始想保存扩大倍数的k,b，实现起来很多坑，后来看到x*100+y的保存方式，最终结果用字符串保存十分巧妙。
 
闫式背包一开始就没想出来，还是积累不够
 
后面的杨辉三角形和双向排序都是数据量比较大，用的简单方法蹭了一部分分数~~~
 
总之，难度感觉要比往年的大一些，还是要继续努力呀