0


【蓝桥杯】每日一题冲刺国赛

今日学习📃

🎋1、巧拼扑克牌

🎃2、质数拆分

🖼️3、日志统计

🎄4、递增三元组

🎍5、外卖店优先级

🎋1、巧拼扑克牌

🎯题目描述

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

小明刚上小学,学会了第一个扑克牌“魔术”,到处给人表演。魔术的内容是这样的:

他手里握着一叠扑克牌:A,2,....J,Q,K一共 13 张。他先自己精心设计它们的顺序,然后正面朝下拿着,开始表演。

只见他先从最下面拿一张放到最上面,再从最下面拿一张翻开放桌子上,是 A;然后再从最下面拿一张放到最上面,再从最下面拿一张翻开放桌子上,是 2;......如此循环直到手中只有一张牌,翻开放桌子上,刚好是 K。

这时,桌上牌的顺序是:A,2,3,4,5,6,7,8,9,10,J,Q,K。

请你计算一下,小明最开始的时候手里牌的顺序是怎样的。

把结果写出来,逗号分割,小明“魔术”开始时,最下面的那张牌输出为第一个数据。

运行限制

  • 最大运行时间:1s
  • 最大运行内存: 128M
package Day_Day_work;

/**
 * @author yx
 * @date 2022-03-13 10:17
 */

public class 巧排扑克牌 {
// 1:输出是逗号+空格
        public static void main(String[] args) {
            System.out.print("7, A, Q, 2, 8, 3, J, 4, 9, 5, K, 6, 10");
    }
}

🎪题解分析:

💦1、第一题没啥好说的,自己花几分钟手撸一下,然后在花几分钟验证一下即可

💦2、实在不济,自己模拟一下题目,做个小手工,一张一张自己实现一下这个过程即可

🎃2、质数拆分

🎯题目描述

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

将 2019 拆分为若干个两两不同的质数之和,一共有多少种不同的方法?

注意交换顺序视为同一种方法,例如 2 + 2017 = 2019 与 2017 + 2 = 2019视为同一种方法。

运行限制

  • 最大运行时间:1s
  • 最大运行内存: 128M
package Day_Day_work.problem;
/**
 * @author yx
 * @date 2022-03-13 10:52
 */
public class 质数拆分__01背包问题 {
    static long[] a=new long[2020];
    static int[] p=new int[2020];
    public static void main(String[] args) {
            a[0]=1;
            int n=1;
            for(int i=1;i<2019;i++)
            {
                if(pd(i))
                {
                    p[n++]=i;
                }
            }
        /**
         * 下面是01动规核心代码
         */
        for(int i=1;i<=n-1;i++) {
                for(int j=2019;j>=p[i];j--) {
                    a[j] += a[j-p[i]];
                }
            }
            System.out.println(a[2019]);
    }

    static boolean pd(int x) {//质数判断
        if(x==1)
        {
            return false;
        }
        for(int i=2;i<=(int) Math.sqrt(x);i++)
        {
            if(x%i==0)
            {
                return false;
            }
        }
        return true;
    }
}

🎪题解分析:

💦1、这个题目很容易理解错误,是若干两两不同的组成,而不是两个组成(博主踩过的坑)

💦2、将题目拆分成两个部分:质数判断、背包组合

难点分析:

💦1、能看出题目背后的本质,其实就是背包问题

💦2、熟练01背包问题

💦3、能快速写出质数判断的方法(暴力方法就可)

🖼️3、日志统计

🎯题目描述

小明维护着一个程序员论坛。现在他收集了一份"点赞"日志,日志共有 N 行。其中每一行的格式是:ts id

表示在 ts 时刻编号 id 的帖子收到一个"赞"。

现在小明想统计有哪些帖子曾经是"热帖"。如果一个帖子曾在任意一个长度为 D 的时间段内收到不少于 K个赞,小明就认为这个帖子曾是"热帖"。

具体来说,如果存在某个时刻 T 满足该帖在 [T,T+D)这段时间内(注意是左闭右开区间)收到不少于 K 个赞,该帖就曾是"热帖"。

给定日志,请你帮助小明统计出所有曾是"热帖"的帖子编号。

输入描述

输入格式:

第一行包含三个整数 N,D,K

以下 N 行每行一条日志,包含两个整数 ts 和 id。

其中,10^51≤K≤N≤105,0≤ts≤105,0≤id≤105。

输出描述

按从小到大的顺序输出热帖 id。

每个 id 一行。

输入输出样例

示例

输入

7 10 2
0 1
0 10
10 10
10 1
9 1
100 3
100 3

输出

1
3

运行限制

  • 最大运行时间:1s
  • 最大运行内存: 256M
package Day_Day_work;

import java.util.*;

/**
 * @author yx
 * @date 2022-03-13 15:19
 */
public class 日志统计__尺取法 {
    static class R{
        int ts;//时刻
        int td;//id
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N=scanner.nextInt(),D=scanner.nextInt(),K=scanner.nextInt();
        R[] rs=new R[N];
        for (int i = 0; i < N; i++) {
            R r=new R();
            r.ts=scanner.nextInt();
            r.td=scanner.nextInt();
            rs[i]=r;
        }
        //匿名内部类定义排序器
        Arrays.sort(rs, new Comparator<R>() {
            @Override
            public int compare(R o1, R o2) {
                return o1.ts-o2.ts;//表示按时刻的升序来排列
            }
        });
        //用于给id计点赞数
        Map<Integer,Integer> cnt=new HashMap<>();
        //用于存储答案,TreeSet自动对集合中的元素进行升序排序
        SortedSet<Integer> answer=new TreeSet<Integer>();
        /*
          尺取法
         */
        int j=0;
        for (int i = 0; i < N; i++) {
            while (j<N&&rs[j].ts-rs[i].ts<D){//左闭右开,时间区间不能超过D
                int td=rs[j].td;
                Integer exist=cnt.get(td);
                if(exist!=null){//不为空的情况下
                    cnt.put(td,exist+1);//该id的点赞次数+1
                }else {//最开始的情况
                    cnt.put(td,1);//该id第一次出现,直接给赋值为1
                }
                if(cnt.get(td)>=K){//当点赞次数超过K时加入到answer集合中
                    answer.add(td);
                }
                j++;//往后继续取区间
            }
            //退出while循环后,i往后移动会+1,则当前的i的点赞数-1,因为后面的区间最小值为i+1
            //不包括i,将该id下的点赞数-1
            Integer c=cnt.get(rs[i].td);//获取该id下的点赞数
            if(c!=null){
                cnt.put(rs[i].td,c-1);//更新点赞数
            }
        }
        for (Integer i:answer) {
            System.out.println(i);
        }
    }
}

🎪题解分析:

💦1、该题采用尺取法,区间间隔移动,统计在D时间区间内每个id的获赞数

💦2、使用类绑定时刻和id

难点分析:

💦1、匿名内部类自定义排序器(定义了一个类来绑定时刻和id,所以要重写一下排序方法)

💦2、熟练使用HashMap和TreeSet

💦3、熟练使用尺取法

🎄4、递增三元组

🎯资源限制

时间限制:1.0s 内存限制:256.0MB

  给定三个整数数组
  A = [A1, A2, ... AN],
  B = [B1, B2, ... BN],
  C = [C1, C2, ... CN],
  请你统计有多少个三元组(i, j, k) 满足:
  1. 1 <= i, j, k <= N
  2. Ai < Bj < Ck

输入格式

  第一行包含一个整数N。
  第二行包含N个整数A1, A2, ... AN。
  第三行包含N个整数B1, B2, ... BN。
  第四行包含N个整数C1, C2, ... CN。

  对于30%的数据,1 <= N <= 100
  对于60%的数据,1 <= N <= 1000
  对于100%的数据,1 <= N <= 100000 0 <= Ai, Bi, Ci <= 100000

输出格式

  一个整数表示答案

样例输入

3
1 1 1
2 2 2
3 3 3

样例输出

27

package Day_Day_work;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author yx
 * @date 2022-03-13 16:02
 */
public class 递增三元组 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int A[] = new int[N];
        int B[] = new int[N];
        int C[] = new int[N];
        for (int i = 0; i < N; i++) {
            A[i] = scanner.nextInt();
        }
        for (int i = 0; i < N; i++) {
            B[i] = scanner.nextInt();
        }
        for (int i = 0; i < N; i++) {
            C[i] = scanner.nextInt();
        }
        //计数
        int a = 0;
        int b = 0;
        int c = 0;
        //升序排列
        Arrays.sort(A);
        Arrays.sort(B);
        Arrays.sort(C);
        int j = 0;
        int k = 0;
        long ans=0;
        for (int i = 0; i < N; i++) {
            while (j<N&&A[j]<B[i])j++;
            while (k<N&&C[k]<=B[i])k++;
            ans+=(long) (N-k)*j;
        }
        System.out.println(ans);
    }
}

🎪题解分析:

💦1、先将A、B、C三个数组进行升序排序

💦2、以B数组为突破点,从左往右遍历A数组定位小于B[i]的A元素有j个

💦3、以B数组为突破点,从左往右遍历C数组定位小于等于B[i]的C元素有k个

💦4、那么该轮一共有(j)*(n-k)个三元组

💦5、按照该思路从左往右遍历B数组,累加每一轮的三元组数量

🎍5、外卖店优先级

🎯题目描述

"饱了么"外卖系统中维护着 NN 家外卖店,编号 1 ∼ NN。每家外卖店都有 一个优先级,初始时 (0 时刻) 优先级都为 0。

每经过 1 个时间单位,如果外卖店没有订单,则优先级会减少 1,最低减 到 0;而如果外卖店有订单,则优先级不减反加,每有一单优先级加 2。

如果某家外卖店某时刻优先级大于 5,则会被系统加入优先缓存中;如果 优先级小于等于 3,则会被清除出优先缓存。

给定 TT 时刻以内的 MM 条订单信息,请你计算 TT 时刻时有多少外卖店在优 先缓存中?

输入描述

第一行包含 3 个整数 N,M,TN,M,T。

以下 MM 行每行包含两个整数 ts,idts,id,表示 tsts 时刻编号 idid 的外卖店收到一个订单。

其中,1 \leq N,M,T \leq 10^5,1 \leq ts \leq T,1 \leq id \leq N1≤N,M,T≤105,1≤ts≤T,1≤id≤N。

输出描述

输出一个整数代表答案。

输入输出样例

示例

输入

2 6 6
1 1
5 2
3 1
6 2
2 1
6 2

输出

1

样例解释:

6 时刻时,1 号店优先级降到 3,被移除出优先缓存;2 号店优先级升到 6, 加入优先缓存。所以是有 1 家店 (2 号) 在优先缓存中。

运行限制

  • 最大运行时间:2s
  • 最大运行内存: 256M
package Day_Day_work;
import java.util.Scanner;

/**
 * @author yx
 * @date 2022-03-13 19:42
 */
/*
仔细读题:
1、优先级最低减到 0
2、优先级大于 5,则会被系统加入优先缓存(进入优先缓存后还有可能被移除)

思路:
1、先模拟,再全部遍历
 */
public class 外卖店优先__暴力模拟 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N=scanner.nextInt();//M行数据输入
        int M=scanner.nextInt();//N家店
        int T=scanner.nextInt();//给定的一个时刻
        int A[][]=new int[N][T];
        int ans=0;//计数
        for (int i = 0; i < M; i++) {
            int ts=scanner.nextInt();//输入时刻
            int id=scanner.nextInt();//输入店的id
            A[id-1][ts-1]+=1;//表示这家店来了一个订单
        }
        for (int i = 0; i < N; i++) {//对每一家店做处理
            int level=0;//优先级
            boolean k=false;//是否能够加入优先缓存
            for (int i1=0;i1<T;i1++){
                if(A[i][i1]==0){//表示没有订单
                    level-=1;
                    if(level<0){
                        level=0;
                    }
                    if (level<=3){
                        k=false;
                    }
                }else {
                    level+=(2*A[i][i1]);
                    if(level>5){
                        k=true;
                    }
                }
            }
            if(k){
                ans++;
            }
        }
        System.out.println(ans);
    }
}

🎪题解分析:

💦1、本题解为暴力方法,性价比最高

💦2、定义一个二维数组,行数表示店的数量,列数表示一共有多少个时刻

💦3、先将所有数据存入二维数组

💦4、遍历每一家店

难点分析:

💦1、优先级最低减到 0,就不会再减了

💦2、优先级大于 5,则会被系统加入优先缓存(但是进入优先缓存后还有可能被移除)

💦3、先模拟,再全部遍历

💖写在最后

每日一题,我们一直在路上,这次的题目有点小难度,比较有挑战性

也充分认识到了自己的不足,比如说在动规背包问题上的薄弱,博主接下来将有针对性地加强训练

“心若有所向往,何惧道阻且长,各位有志青年,一起加油 !”

欢迎一起交流讨论!

标签: 蓝桥杯 java

本文转载自: https://blog.csdn.net/m0_55858611/article/details/123470753
版权归原作者 小羊不会飞 所有, 如有侵权,请联系我们删除。

“【蓝桥杯】每日一题冲刺国赛”的评论:

还没有评论