第15届蓝桥杯题解

目录

A题

B题

C题

D题

E题

---

选手感言

发表一下陪跑感言，去年国二选手今年感觉省二了，只跑满了两道填空一道大题，第三题我不知道如何结束程序直接放弃了，第四题我用的自以为的最优分配但在另一个网站上只能跑过两个案例，第六题（想骂人）看着很简单即使图图的深搜，我也做了各种优化，但是它时间复杂度还是太高了如果是小数据案例可以过，但是数据大了会超时，用错算法解题了。

反思一下，也是得了国二飘了也就没有怎么练习竞赛类算法，只看了代码随想录类的模板数据结构型算法（这种对于找工作有用，比赛差点意思），加上去年是学了算法设计与分析这门数，对时间复杂度很敏感，今年就真废了哭死。

A题

结果：2429042904288

思路很简单

前20个数分别是

20 24 40 48 60 72 80 96 100 120 140 144 160 168 180 192 200 216 220 240

第2  4 6 8 12 ...n个数分别是24的 1倍 2倍 3倍 4倍 6倍 n/2倍

所以第202420242024 个数就是 24的 101210121012倍

B题

答案：7913837

以前经典的斐波那契函数是

初始数据 是 1 1

然后新的数等于前两个数相加

于是数列为 1 1 2 3 5 8......

本题的意思是 先给你一个数让你初始化数列数据

比如  197

初始化数据是 1 9 7

然后新的数等于前n个数相加（n为S的位数比如197n就为3）

于是数列为 1 9  7   17（1+9+7） 33（9+7+17） 57（7+17+33） 107（17+33+57）197（33+57+107）...

所以我们算法思路也是先根据数入的数S给数列初始化然后再和加上前n个数

 
import java.util.ArrayList;
import java.util.List;
 
public class Main {
    public static void main(String[] args) {
        List list = new ArrayList<>();
        for (int i=10000000;i>=1;i--){
            String s =""+ i;
            for (int j=0;j//初始化数列
                list.add(s.charAt(j)-'0');
            }
            int len = s.length();
            boolean ist = false;
            while (list.get(list.size()-1)
                int sum=0;
                for (int j=list.size()-1;j>=list.size()-len;j--){//求前n位数相加
                    sum+=list.get(j);
 
                }
                list.add(sum);
                if (sum==i){//如果得到的值等于S输出结果
                    System.out.println(sum);
                    ist = true;
                    break;
                }
            }
            if (ist){
                break;
            }
        }
    }
}

C题

C题并不知道如何结束输出先欠着吧 有人说用hasnext()来判断结束

D题

上我的我觉得无懈可击但就是跑不过的代码

 
import java.util.Scanner;
 
public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int q = sc.nextInt();
 
        while (q-->0) {
        int  sum=0;
            int a2 = sc.nextInt();
            int a3 = sc.nextInt();
            int a4 = sc.nextInt();
            int b4 = sc.nextInt();
            int b6 = sc.nextInt();
            for (int i=1;i<=b6;i++){//一张一张6人桌分配  3+3 4+2 2*3 3+2 4 2+2 3
                  if (a3/2>=1){
                      sum+=6;
                      a3-=2;
                  }else if (a4!=0&&a2!=0){
                      sum+=6;
                      a4--;
                      a2--;
                  }else if (a2/3>=1){
                      sum+=6;
                      a2-=3;
                  }else if (a2!=0&&a3!=0){
                      sum+=5;
                      a2--;
                      a3--;
                  }else if (a4!=0){
                      sum+=4;
                      a4--;
 
                  }else if (a3!=0){
                      a3--;
                      sum+=3;
                  }else if (a2!=0){
                      a2--;
                      sum+=2;
                  }
            }
            for (int i=1;i<=b4;i++){// 一张一张分配四人桌 4 2+2 3 2
                if (a4!=0){
                    sum+=4;
                    a4--;
                }else if (a2/2>=1){
                    sum+=4;
                    a2-=2;
                }else if (a3!=0){
                    sum+=3;
                    a3--;
                }else if (a2!=0){
                    sum+=2;
                    a2--;
                }
            }
            System.out.println(sum);
        }
 
    }
}

E题

作者废话 ：

这道题对于经历新冠肺炎的我们简直不要太友好。2020年新冠大家进制出门，21年轻了，但是大家出个门回个家都要做个核酸，刚开始是要求做单检一个人39￥，因为当时感染率高，一个一个测（虽然我们那就个位数感染），后来全国感染率低了就开始混检了可能20个人一个试剂盒10个人一个试剂盒价格也就4元或10元吧。毕竟一有阳性病例就要全校排查全校两万人，可能就有几十个感染的所以不不必一个一个排查 。

结合题目分析：

单纯举个例子讲是如何排查的比如感染率 P =0.01 宠物数  N= 100

首先我们都知道不分组也就是单独检测的情况（也可以理解为分组了一组的数量为N即100）

需要检测100次一共消耗100支试剂

如果分组，那么我们先理想化一下给的条件 P=0.01 N=100

那么感染的动物数量为1

我们把10个宠物分为1组

那么100个宠物分10组，其中一组会被检测出阳性

步骤是：（1）10组会用10支试剂检测 然后检测出一组阳性

然后将这组阳的所有宠物再都做单检，又会消耗10支试剂

一共需要消耗20支试剂（也是案例的最优分组）

然后计算一个分组所需要消耗试剂的通用公式为

设 一组内宠物数量为k，分了m组感染率为P 宠物总数为N

那么  N=k*m

消耗试剂为   sum =  m+  k*m（1-pow(1-p,k)）

解释说明

m为第一次要把所有组都检测一遍

1-pow（1-p，k）为一组内检测出阳性的概率，即pow（1-p，k）为一组都为阴性的概率

然后 检测出阳性把 这组的宠物都做单检 即 K*

然后共有m组 乘上m ，m*k（1-pow（1-p，k））

综上 sum =  m+  k*m（1-pow(1-p,k)）

上代码（这个是满分答案）

 
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        double p =sc.nextDouble();
        
        int t=1;//t记录最优分组内数量 初始我们让一组有一个宠物 
        double min=n;//min记录最少消耗试剂数量 初始为n
        for (int i=2;i//i为每组宠物数
 
            if (n%i==0){
            int  k=n/i;
            double num = k+k*i*(1-Math.pow(1-p,i));//计算消耗试剂的公式
            if (num//如果比以前的方案消耗的少
                min=num;
                t=i;//记录新的分组数量
 
            }
            }
 
        }
        //判断浮点数是否等于0不能用==要用<1e-6 float 用1e-6 double 可以用1e-12 本题不用那么精确
        if (p<1e-6){//这里是一个特殊情况如果p=0那么就没有要感染的宠物，把直接把所有宠物分为一组做一次试剂检测就好了直接输出N
            System.out.println(n);
 
        }else
        System.out.println(t);
    }
 
 
}

G题

直接上我的最优的暴力的深搜代码

 
 
import java.util.*;
 
public class Main {
 
    public static void main(String[] args) {
 
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int q  = sc.nextInt();
        Map> map = new HashMap<>();//用map存取传送门 已经很节省时间了
        int arr[][] = new int[n+1][n+1];
        for (int i=0;i
            int a = sc.nextInt();
            int b = sc.nextInt();
            if (map.containsKey(a)){
                List list = map.get(a);
                list.add(b);
                map.put(a,list);
            }else {
                List list = new ArrayList<>();
                list.add(b);
                map.put(a,list);
            }
            if (map.containsKey(b)){
                List list = map.get(b);
                list.add(a);
                map.put(b,list);
            }else {
                List list = new ArrayList<>();
                list.add(a);
                map.put(b,list);
            }
        }
 
 
        int t = q;
        int[] v =new int[n+1];
        double sum = 0;
        while (t-->0){
            int a = sc.nextInt();
            int b = sc.nextInt();
 
            Set set = new HashSet<>();
            set.add(a);
            v[a]=1;
            dfs(b,a,v,set,map);
            v[a]=0;
            sum+=set.size();
        }
        System.out.printf("%.2f",sum/q);
    }
    public  static void  dfs(int num ,int index,int []v,Set set,Map> map){
        for (int n : map.get(index)){
            if (num>0&&v[n]==0){
                v[n]=1;
                set.add(n);
                dfs(num-1,n,v,set,map);
                v[n]=0;
            }
        }
    }
    }