- 博客(101)
- 收藏
- 关注
RSS订阅原创 数星星 树状数组
输入样例51 15 17 13 35 5输出样例12110这里使用的是树状数组算法计算，核心函数有三个，因为输入是按照y相同x升序，其他的y升序方法输入，我们可以边输入边处理，（如果不按照这个方法输入，那么可以自己排序这样处理）因为在处理到这个坐标时比该坐标纵坐标y更大的星星还没有录入系统，那么我们并且比该坐标横坐标x更小的星星已经录入完毕，所以当这个星星录入时，它的等级其实就已经确定了，而且我们可以把已经录入的所有星星的按照x坐标树状数组的方式存储在各个数组，在这个星星录.
2022-03-29 15:01:57
212
原创 外卖店优先级 蓝桥杯
输入样例：2 6 61 15 23 16 22 16 2输出样例：1这个题就是纯纯的模拟，如果模拟每一个时间和每一个外卖店的话，时间复杂度是O(1010)，就会超时。grade数组代表外卖店的等级you数组代表外卖店是否在优先缓存last数组代表上一次这个外卖店有订单的时间、que是pair类型的数组，存储的是m条外卖信息，并且按照优先级进行升序排序。对于每一个订单，我们先计算有几个连续的相同的订单信息，我们先处理这个订单对应的商铺上一次收到订单的时间到现在的过程中减.
2022-03-25 19:28:55
731
原创 逆序对数量 Acwing 归并排序的模板题目
这个题目的解答代码就是归并排序的一个模板题。只是我们要理解归并排序的过程思想，才能使用归并排序解决题目中所给的逆序对问题。这里最精华的部分就是这行代码 while(i<=mid&&j<=r) { if(que[i]>que[j]) num[cnt++]=que[j++],ans+=(mid-i+1);//在这里 else num[cnt++]=que[i++]; } 在将两个左右两边的有序队列合并的时候，如果右边的队列最小值小于左边队列的最小值，则说明需.
2022-03-24 21:14:49
607
原创 航班时间 C++ 蓝桥杯
输入示例317:48:19 21:57:2411:05:18 15:14:2317:21:07 00:31:46 (+1)23:02:41 16:13:20 (+1)10:19:19 20:41:2422:19:04 16:41:09 (+1)输出示例04:09:0512:10:3914:22:05这个题经过推导，不管是先从时差早的地方先飞还是后飞，公式都不变。设q为飞行时间。则2*q=Y1-X1+Y2-X2就是说我们把得到的两个时间做差（注意是否要+1），然后求和除二即可.
2022-03-24 19:05:36
1128
1
原创 素数判断-----朴素判断、埃氏筛法、欧拉筛法
朴素判断时间复杂度O(n2)#include<bits/stdc++.h> //朴素判断的方法肯定会超时 using namespace std;const int N=1e3; bitset<N> prime; bool judge(int x){ for(int i=2;i<=x/i;i++){//这里判断范围要写成小于等于b/i,防止溢出int if(x%i==0) return false; } return true;}int main
2022-03-20 20:27:43
530
原创 棋盘游戏2 C++ 二分图最大匹配问题
输入样例13 3 41 21 32 12 23 3 41 21 32 13 2输出样例1Board 1 have 0 important blanks for 2 chessmen.Board 2 have 3 important blanks for 3 chessmen.二分图最大匹配问题，车在象棋里只能走直线，不能拐弯，所以为了不让车之间相互吃，得保证车不在同一行、同一列。行看作一个集合，列看作一个集合，最大匹配数就是能放的最大车的数量。根据题目要求的重要点定义，.
2022-03-17 21:04:22
4680
原创 最短路C++ 蓝桥杯
题目描述本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。如下图所示，G 是一个无向图，其中蓝色边的长度是 1、橘色边的长度是 2、绿色边的长度是 3。则从 AA 到 SS 的最短距离是多少？运行限制最大运行时间：1s最大运行内存: 128M最短路径模板题，初始化比较麻烦，一共36条路径。我初始化的时候A-S分别用1-19代替。初始化的时候保证从一个小的数字出发到一个大一点的数字。这样就不会重复了。#include<bits/stdc++.h>using
2022-03-13 14:11:54
994
原创 互质 计蒜客T1554
样例输入7120样例输出64首先这个题一开始，根据数据范围分析我们使用的方法，n<1e9，那么判断是所有和它互素的数字，用正常的方法去一一判断肯定会超时，而我们学习过数论的同学都知道有一个函数叫做欧拉函数，它的值代表小于这个数并且与该数互素的数字个数，前人告诉后人一个求欧拉函数的计算方法：-------------------------------------------------------------------------------------------------.
2022-03-12 17:08:04
424
原创 明码 C++ 蓝桥杯
4 0 4 0 4 0 4 32 -1 -16 4 32 4 32 4 32 4 32 4 32 8 32 8 32 16 34 16 34 32 30 -64 0 16 64 16 64 34 68 127 126 66 -124 67 4 66 4 66 -124 126 100 66 36 66 4 66 4 66 4 126 4 66 40 0 16 4 0 4 0 4 0 4 32 -1 -16 4 32 4 32 4 32 4 32 4 32 8 32 8 32 16 34 16 34 3.
2022-03-05 18:00:31
3420
原创 杨辉三角形C++ 蓝桥杯
这个题我去年比赛的时候用的就是最笨的方法，开一个二位数组，然后逐个判断。1、这个题我们到手先分析一波，这个数据范围是小于10的9次方，时间限制是1s，杨辉三角有一个特性是每个数字都等于肩上两个数字之和，开个10亿*10亿的二位数组不可能，而且1s最多操作1亿次，所以这个题目不能枚举，另有技巧。2、我们可以通过杨辉三角判断一下我们需要枚举的行数范围，第n+1行第一个数字一定是1，第二个数字是n，第三个数字n*(n-1)/2，也就是所每一个数字n一定可以从第n-1行的第二个数字里找到他的位置，但不一定是.
2022-03-04 20:53:11
6579
16
原创 七段码 蓝桥杯
初见此题没有思绪，我隐隐的感觉要用到并查集，但我又不知道怎么做，这个题比最简单的并查集要多一个难点，就是指定的方向才能将两个点链接，再一个就是这七个数码管亮和不亮的全排列怎么枚举。第一个是我们数码管的全排列，一共是128种情况（包括全不亮），所以对应数字的二进制位的0和1可以一一对应每个数码管的亮或者不亮，我们利用位运算可以解决这个问题。这个特定要求的并查集，我们可以设置二位数组，在判断两个发光管能否合并时可以使用，二位数组下标0-6分别代表a-g，如果这个数字是1则代表可以联通。最后值得关注的是这.
2022-02-25 21:55:06
1480
原创 蛇形填数 蓝桥杯
当年写题没写出来。记录一下这次的解题代码#include<bits/stdc++.h> using namespace std;int que[45][45];int main(){ que[1][1]=1; que[2][1]=3; que[1][2]=2; int i=3; int j=1; que[i][j]=4; int now=5; while(i<=40){//开始填数字 while(i!=1){//斜向上填数字 i--; j++;.
2022-02-20 21:19:28
1246
原创 迷宫 蓝桥杯
题目描述 本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。下图给出了一个迷宫的平面图，其中标记为 1的为障碍，标记为 0 的为可以通行的地方。010000000100001001110000迷宫的入口为左上角，出口为右下角，在迷宫中，只能从一个位置走到这 个它的上、下、左、右四个方向之一。对于上面的迷宫，从入口开始，可以按 DRRURRDDDR 的顺序通过迷宫， 一共 10 步。其中D、U、L、R分别表示向下、向上、向左、向右走。 对于下面这个更复杂的迷宫（3.
2022-02-15 18:48:18
125
原创 数的分解 蓝桥杯
题目链接1、最一开始的思路是这仨个数字各有特征，第一个数字i一定是小于等于2019的三分之一，而剩下两个数字组成2019-i，其中一个数字肯定小于等于2019-i的二分之一，这样我们两重循环找到了这三个数字，在保证三个数字不重复并且满足题目要求(不包含数字2和4)的情况下进行去重。2、去重开始，我在思考如何去重，我最早使用的方法是将排序好的三个数字组合成一个长数字，然后从头算有多少个不重复的数字，就有多少个不同的组合，结果是40779，答案错误。我开始去查其他人写的正确答案，是40785。也就说哪个环节
2022-02-14 20:23:36
1828
原创 等差数列 蓝桥杯
这个题说实话并不难，但是写的时候一个细节妹想到导致了运行错误，哎，还是得多修炼啊。输入输出样例输入52 6 4 10 20输出10样例说明： 包含 2、6、4、10、20 的最短的等差数列是 2、4、6、8、10、12、14、16、 18、20。运行限制最大运行时间：1s最大运行内存: 256M题目链接这里主要就是注意公差为0的情况就可以了代码如下：#include<bits/stdc++.h> using namespace std;const int N=
2022-02-10 22:23:14
1237
原创 年号字串 蓝桥杯
题目链接这个题的关键是认清楚这个是一个26进制的计数方式，并且没有数字0，对于题目中举的例子，我们可以这样理解A=1×260B=2×260Z=26*260AA=1×261 +1×260=27AB=1×261 +2×260=28AZ=1×261 +26×260=52LQ=12×261+17×260=329AAA=1×262+1×261+1×260=703由此可见，这是一种特殊的26进制计数法，我们平时使用的10进制计数法，是逢10进1，而题目中这个特殊的26六进制却不是逢26进1，并
2022-02-10 15:30:46
1227
原创 K倍区间 蓝桥杯
题目链接我这里写的sum[i]数组是下标0-i各个元素之和。cnt[dex]是指i之前的前缀和中对k取余为dex的数组个数，如果我遍历到这个数字了，我就计算这个数字之前和我前缀和模k数字相同的前缀和个数，累加即可。值得注意的是我们在计算的过程中要将cnt[0]设为1，因为如果到que[i]这里前缀和模k为0，则说明1到i的和就是符合要求的，我们要加1。#include<bits/stdc++.h> using namespace std;const int N=100005;long
2022-02-09 21:10:55
312
原创 等差素数列 蓝桥杯
题目链接这个题就是直接枚举。先把一定范围内的素数都存起来。然后以这些素数作为素数列的第一个数字去枚举方差判断其后连续九个数字是都是素数，如果是的话直接输出。可无语一开始妹想到。#include<bits/stdc++.h> //这个题就是直接枚举 using namespace std;bool prime(int x){ if(x==1) return false; for(int i=2;i*i<=x;i++){ if(x%i==0) return false; }
2022-02-09 18:30:09
680
原创 分巧克力 蓝桥杯
问题链接题目描述 儿童节那天有 K 位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。小明一共有 N块巧克力，其中第 i 块是 Hi×Wi 的方格组成的长方形。为了公平起见，小明需要从这 N 块巧克力中切出 K 块巧克力分给小朋友们。切出的巧克力需要满足：形状是正方形，边长是整数;大小相同;例如一块 6x5 的巧克力可以切出 6 块 2x2 的巧克力或者 2 块 3x3 的巧克力。当然小朋友们都希望得到的巧克力尽可能大，你能帮小明计算出最大的边长是多少么？输入输出样例 示例输入
2022-02-08 22:24:16
625
原创 包子凑数 蓝桥杯
题目链接题目描述小明几乎每天早晨都会在一家包子铺吃早餐。他发现这家包子铺有 NN 种蒸笼，其中第 ii 种蒸笼恰好能放 A_iA i 个包子。每种蒸笼都有非常多笼，可以认为是无限笼。每当有顾客想买 XX 个包子，卖包子的大叔就会迅速选出若干笼包子来，使得这若干笼中恰好一共有 XX 个包子。比如一共有 3 种蒸笼，分别能放3、4 和 5 个包子。当顾客想买 11 个包子时，大叔就会选 2 笼 3 个的再加 1 笼 5 个的（也可能选出 1 笼 3 个的再加 2笼 4 个的）。当然有时包子大
2022-02-08 01:15:13
116
原创 日期问题 蓝桥杯
题目描述小明正在整理一批历史文献。这些历史文献中出现了很多日期。小明知道这些日期都在 1960 年 1 月 1 日至 2059 年 12 月 31 日。令小明头疼的是，这些日期采用的格式非常不统一，有采用年/月/日的，有采用月/日/年的，还有采用日/月/年的。更加麻烦的是，年份也都省略了前两位，使得文献上的一个日期，存在很多可能的日期与其对应。比如 02/03/04，可能是 2002 年 03 月 04 日、2004 年 02 月 03 日或 2004 年 03 月 02 日。给出一个文献上的日期，
2022-02-06 21:01:03
363
原创 承压计算 蓝桥杯
题目描述本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。X 星球的高科技实验室中整齐地堆放着某批珍贵金属原料。每块金属原料的外形、尺寸完全一致，但重量不同。 金属材料被严格地堆放成金字塔形。 7 5 8 7 8 8 9 2 7 2
2022-02-05 23:09:46
87
原创 二分模板（整数二分和小数二分）
我们以下讨论都是对于有序数组整数二分确实比较难搞哈，我也是学了两边才差不多懂了y总的思路，写题的时候按照需求套模板就好了。对于整数二分，我们可将其按照我们要找的数字x分为两段。1. x是红色区间的右端点，将[L,R]分为[L,M-1]和[M,R]//这个是思路1while(L<R){ M=(L+R+1)/2; if(M是红色) L=mid; else R=mid-1;}//这个是模板1while(L<R){ M=(L+R+1)/2;//注意这里如果
2022-01-19 15:40:53
989
原创 学到点东西
之前求2的n次方方法还很传统，甚至想到了快速幂。结果这次写题居然爆了long long。所以从此学会了2的n次方计算方法是 int a=1<<n;//2的n次方然后自己花了好久的时间还在研究杨辉三角每个数字是不是组合排列数，每行之和是不是2的n次方。调试了几次代码。行吧，我就是今天写ACWing周赛学到的。只有考试遇到了才会永远记住！！！方块集数量#include<bits/stdc++.h>using namespace std;const int N=55;c
2021-09-18 21:31:27
68
原创 全排列函数
全排列函数next_permutation（que+x，que+y)//[x,y)之间进行全排列头文件#include <algorithm>产生该数组下一个字典序序列
2021-08-28 22:37:35
67
原创 快速排序的高速实现方法（二分法）
和传统快速排序比起来，这样的改动可以达到比sort更快，我愿称之为高速排序void quicksort(int begin,int end){ int left,right,mid; left=begin;right=end; mid=a[(begin+right)/2]; while(left<=right) { while(a[right]>mid) { right--; } while(a[left]<mid) { left++; }
2021-07-07 22:50:18
407
原创 [蓝桥杯][2013年第四届真题]错误票据
题目描述某涉密单位下发了某种票据，并要在年终全部收回。每张票据有唯一的ID号。全年所有票据的ID号是连续的，但ID的开始数码是随机选定的。因为工作人员疏忽，在录入ID号的时候发生了一处错误，造成了某个ID断号，另外一个ID重号。你的任务是通过编程，找出断号的ID和重号的ID。假设断号不可能发生在最大和最小号。输入要求程序首先输入一个整数N(N< 100)表示后面数据行数。接着读入N行数据。每行数据长度不等，是用空格分开的若干个（不大于100个）正整数（不大于100000），请注意行.
2021-04-16 16:05:38
107
原创 第十一届蓝桥杯 试题 D: 跑步锻炼
【问题描述】小蓝每天都锻炼身体。正常情况下，小蓝每天跑 1 千米。如果某天是周一或者月初（1 日），为了激励自己，小蓝要跑 2 千米。如果同时是周一或月初，小蓝也是跑 2 千米。小蓝跑步已经坚持了很长时间，从 2000 年 1 月 1 日周六（含）到 2020 年10 月 1 日周四（含）。请问这段时间小蓝总共跑步多少千米？这个题当时比赛的时候没有写出来，其实是模拟天数，但是写的过程一定要细心再细心，一定要注意细节，一个是模拟过程中对当前年份二月的更新，一个是循环跳出的判断，不要少加，更不要.
2021-04-15 21:52:17
471
原创 数的读法[蓝桥杯][基础练习VIP]
Tom教授正在给研究生讲授一门关于基因的课程，有一件事情让他颇为头疼：一条染色体上有成千上万个碱基对，它们从0开始编号，到几百万，几千万，甚至上亿。比如说，在对学生讲解第1234567009号位置上的碱基时，光看着数字是很难准确的念出来的。所以，他迫切地需要一个系统，然后当他输入12 3456 7009时，会给出相应的念法：十二亿三千四百五十六万七千零九用汉语拼音表示为shi er yi san qian si bai wu shi liu wan qi qian .
2021-04-14 18:46:24
81
原创 一个人的旅行(最短路算法Dijkstra) 多起点多重点问题-解决方法很妙 HDU--2006
题目链接这题是个标准的求最短路径的题目，不过并不是单一起点单一终点，我的解决方法就是再多加一个虚拟起点，将这个虚拟起点与各个起点的距离为0，然后再加一个虚拟终点，将这个虚拟终点到各个终点的距离设置为0，然后求虚拟起点到虚拟终点的最短路径就可以了，这样的处理就转换为单起点单终点的处理，就和畅通工程续问题一样了。写代码的时候要注意细节，否则很容易掉进循环出不来，注意这个站点是从0开始还是从1开始，注意站点数目的上限值，注意vis的更新，inf的定义，都非常重要，注意初始化imap初始化应该是lnf，di
2021-02-04 16:36:55
548
原创 畅通工程续(最短路算法Dijkstra) HDU--1874
这是一个最短路算法，并且单一起点单一终点，哈哈可以说是很模板的一个题了，用到的算法就是Dijkstra算法，这也是我最近在学校上数据结构课学到的算法，当时还不会实现，现在知道怎么实现了。这个算法的精华部分就是for(int i=0;i<n;i++) { if(imap[s][i]!=lnf) dis[i]=min(dis[i],dis[s]+imap[s][i]); if(vis[i]&&dis[i]<imin)//注意这里vis的判断一定要..
2021-02-04 16:27:17
164
原创 P1005(01背包问题)--C语言网1272
一开始以为这是一个贪心算法问题，后来贪心算法过不了才用动态规划做，这是背包问题里面的01背包问题，出题人很狡猾。题目不难，但是我很无语，这要是OI赛制咋办…当前物体对于第i个物品j个单位时间内有要和不要两种情况，此时的最大价值就是dp[i][j],如果时间j大于采取它的时间v，则动态转移方程是dp[i][j]=max(dp[i-1][j],dp[i-1][j-v]+w)，否则就不能采取，dp[i][j]=dp[i-1][j]#include<bits/stdc++.h>using nam.
2021-02-03 17:14:31
107
原创 丑数(动态规划) HDU
丑数，从1开始，各个丑数之间都是2、3、5、7的倍数关系，所以每个丑数其实都是前面某一个丑数2或3或5或7倍，我们求第n个丑数，那么就要保证不重复，并且是按照升序存储的。求第n个丑数，可以假设dui[n]=2a1×3a2×5a3×7a4每个丑数乘以2或3或5或7都会是丑数，所以我们用n1标记乘已经因为乘2而产生丑数的丑数下标，n2、n3、n4同理。min(dui[n1]*2,min(dui[n2]*3,min(dui[n3]*5,dui[n4]*7)))为动态转移方程，注意要取最小值。#inclu..
2021-02-03 15:49:15
303
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人