锐客网

  1. 首页 > it技术 > >

31日打卡|蓝桥杯真题31日冲刺国一 | 每日题解报告 第六天

算法c++蓝桥杯31日打卡学习数据结构

大家好，我是泡泡，今天题有点多，大家好好消化理解
目录
一、巧拼扑克牌
二、质数拆分
三、日志统计
四、递增三元组
五、外卖店优先级

一、巧拼扑克牌 题目链接：巧排扑克牌 - 蓝桥云课 (lanqiao.cn)
题目要求：
小明刚上小学，学会了第一个扑克牌“魔术”，到处给人表演。魔术的内容是这样的：
他手里握着一叠扑克牌：A，2，....J，Q，K一共 13 张。他先自己精心设计它们的顺序，然后正面朝下拿着，开始表演。
只见他先从最下面拿一张放到最上面，再从最下面拿一张翻开放桌子上，是 A；然后再从最下面拿一张放到最上面，再从最下面拿一张翻开放桌子上，是 2；......如此循环直到手中只有一张牌，翻开放桌子上，刚好是 K。
这时，桌上牌的顺序是：A,2,3,4,5,6,7,8,9,10,J,Q,K。
请你计算一下，小明最开始的时候手里牌的顺序是怎样的。
把结果写出来，逗号分割，小明“魔术”开始时，最下面的那张牌输出为第一个数据。
解题思路：手推题，直接模拟即可，不过我模拟了半天，恶心的水题，代码输出格式也卡。
先取出最下面一张放置上面，然后再翻开下面一张 最后得到一个升序排序的数字排列
?,A,?,2,?,3,?,4,?,5,?,6,? 后边大家也按照这个思路来就好，因为是手推的也讲不出太细了我（我太菜了）
//注意输出格式是，加空格 #include using namespace std; int main() { printf("7, A, Q, 2, 8, 3, J, 4, 9, 5, K, 6, 10"); return 0; }

二、质数拆分 题目链接：质数拆分 - 蓝桥云课 (lanqiao.cn)
题目要求：
将 2019 拆分为若干个两两不同的质数之和，一共有多少种不同的方法？
注意交换顺序视为同一种方法，例如 2 + 2017 = 2019 与 2017 + 2 = 2019 视为同一种方法。
解题思路：
01背包，从前 i 个物品中选，且总体积恰好为 j 的方案的数量。
? #include using namespace std; long long a[2020]; int p[2020]; bool pd(int x) { if(x==1) { return false; } for(int i=2; i<=sqrt(x); i++) { if(x%i==0) { return false; } } return true; } int main() { a[0]=1; int n=1; for(int i=1; i<2019; i++) { if(pd(i)) { p[n++]=i; } } for(int i=1; i<=n-1; i++) { for(int j=2019; j>=p[i]; j--) { a[j] += a[j-p[i]]; } } cout<

三、日志统计 题目链接：日志统计 - 蓝桥云课 (lanqiao.cn)
题目要求：
小明维护着一个程序员论坛。现在他收集了一份"点赞"日志，日志共有 N 行。其中每一行的格式是：
ts\ id
表示在 ts 时刻编号 id 的帖子收到一个"赞"。
现在小明想统计有哪些帖子曾经是"热帖"。如果一个帖子曾在任意一个长度为 D 的时间段内收到不少于 K 个赞，小明就认为这个帖子曾是"热帖"。
具体来说，如果存在某个时刻 T 满足该帖在 [T,T+D) 这段时间内(注意是左闭右开区间)收到不少于 K 个赞，该帖就曾是"热帖"。
给定日志，请你帮助小明统计出所有曾是"热帖"的帖子编号。
解题思路：
这是一个模拟题，定义一个结构体保存时间和id，然后排序，检查是否有赞，当前时间和上次时间是否超了区间，是否是热帖就好。
#include using namespace std; const int N = 100005; int num[N]; //赞 int flag[N]; //是否是热帖 struct post{ int id; int ts; }p[N]; int cmp(post x,post y) { return x.ts>n>>d>>k; for(int i=0; i>p[i].ts>>p[i].id; } sort(p,p+n,cmp); //结构体排序 for(int i=0,j=0; i=d)//当前时间如果与上次时间相差过了d { num[p[j].id]--; j++; //随着时间流逝，d之前的每个贴的次数都减1 } if(num[p[i].id]>=k) { flag[p[i].id] = 1; //如果这个帖子的点赞超过k } } for(int i=0; i

四、递增三元组 题目链接：“蓝桥杯”练习系统
题目要求：
给定三个整数数组
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
解题思路：
我们给每个数组排序，然后使用二分查找函数查找a和b，b和c，每次加这两个找到的值相乘就可。
lower_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。
upper_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。
#include using namespace std; long long n,aa,aaa,sum; int a[100005],b[100005],c[100005]; int main() { cin>>n; for(int i=0; i>a[i]; } for(int i=0; i>b[i]; } for(int i=0; i>c[i]; } sort(a,a+n); sort(b,b+n); sort(c,c+n); for(int i=0; i
五、外卖店优先级 题目链接：外卖店优先级 - 蓝桥云课 (lanqiao.cn)
题目要求：
"饱了么"外卖系统中维护着 N 家外卖店，编号 1 ～ N。每家外卖店都有 一个优先级，初始时 (0 时刻) 优先级都为 0。
每经过 1 个时间单位，如果外卖店没有订单，则优先级会减少 1，最低减 到 0；而如果外卖店有订单，则优先级不减反加，每有一单优先级加 2。
如果某家外卖店某时刻优先级大于 5，则会被系统加入优先缓存中；如果 优先级小于等于 3，则会被清除出优先缓存。
给定 TT 时刻以内的 M 条订单信息，请你计算 T 时刻时有多少外卖店在优 先缓存中?
解题思路：
【31日打卡|蓝桥杯真题31日冲刺国一 | 每日题解报告 第六天】模拟题，和第三题差不多，结构体排序，然后检查上一次订单与这一次的时间，判断优先缓存在不在加不加入。
#include using namespace std; struct node{ int ts,id; }a[100001]; int val[100001]; //得分 bool huan[100001]; //优先缓存 int shang[100001]; //上次订单时间 bool cmp(node a,node b) { if(a.id==b.id)//id从小到大排，时间也是 { return a.ts>m>>n>>t; for(int i=0; i>a[i].ts>>a[i].id; } sort(a,a+n,cmp); for(int i=0; i5)//如果得分大于5 { huan[id] = true; //加入优先缓存 } shang[id] = tt; //更新上次时间 } for(int i=0; i

    推荐阅读


    上一篇：剑指offer|统计回文oj

    下一篇：算法|蓝桥云课 含2天数