大悟县建设局网站,工业产品设计与创客实践项目,万网域名解析,wordpress网站标签logo文章目录 一、连号区间数 1、1 题目描述 1、2 题解关键思路与解答 二、递增三元组 2、1 题目描述 2、2 题解关键思路与解答 三、错误票据 3、1 题目描述 3、2 题解关键思路与解答 四、回文日期 4、1 题目描述 4、2 题解关键思路与解答 五、归并排序 标题#xff1a;蓝桥杯——… 文章目录 一、连号区间数 1、1 题目描述 1、2 题解关键思路与解答 二、递增三元组 2、1 题目描述 2、2 题解关键思路与解答 三、错误票据 3、1 题目描述 3、2 题解关键思路与解答 四、回文日期 4、1 题目描述 4、2 题解关键思路与解答 五、归并排序 标题蓝桥杯——枚举、模拟和排列习题训练 作者Ggggggtm 寄语与其忙着诉苦不如低头赶路奋路前行终将遇到一番好风景 一、连号区间数
1、1 题目描述 题目来源第四届蓝桥杯省赛CB组,第四届蓝桥杯省赛JAVAB组 题目难度简单 题目描述 小明这些天一直在思考这样一个奇怪而有趣的问题 在 1∼N 的某个排列中有多少个连号区间呢 这里所说的连号区间的定义是 如果区间 [L,R] 里的所有元素即此排列的第 L 个到第 R 个元素递增排序后能得到一个长度为 R−L1 的“连续”数列则称这个区间连号区间。 当 N 很小的时候小明可以很快地算出答案但是当 N 变大的时候问题就不是那么简单了现在小明需要你的帮助。 输入格式 第一行是一个正整数 N表示排列的规模。 第二行是 N 个不同的数字 Pi表示这 N 个数字的某一排列。 输出格式 输出一个整数表示不同连号区间的数目。 数据范围 1≤N≤10000, 1≤Pi≤N 输入样例1 4
3 2 4 1输出样例1 7输入样例2 5
3 4 2 5 1输出样例2 9样例解释 第一个用例中有 77 个连号区间分别是[1,1],[1,2],[1,3],[1,4],[2,2],[3,3],[4,4][1,1],[1,2],[1,3],[1,4],[2,2],[3,3],[4,4] 第二个用例中有 99 个连号区间分别是[1,1],[1,2],[1,3],[1,4],[1,5],[2,2],[3,3],[4,4],[5,5] 1、2 题解关键思路与解答 首先我们仔细阅读题目。题中提到了1∼N 的某个排列注意是排列所以是1∼N 中没有重复的数据且所有数据都会出现一次。题目大概意思是给我们一组数据是乱序的。然后我们需要在这组数据中任选一段连续区间看是否能组成“连续”数列。我们第一想到的是两层for循环枚举区间在对区间排序判断是否为“连续”数列。这样时间复杂度显然是不能通过题中所有案例的。我们仔细观察区间数值不会重复那么区间的最大值减去区间的最小值等于区间下标相减。这样大大提高了效率我们结合代码一起理解一下。 #includeiostream
#includealgorithm
#includecstringusing namespace std;int n;const int N 10010;
const int MAX-1e8,MIN1e8;int a[N];int main()
{cinn;for(int i0;in;i)cina[i];int res0;for(int i0;in;i){int maxcMAX,mincMIN;for(int ji;jn;j){maxcmax(maxc,a[j]);mincmin(minc,a[j]);if(maxc-mincj-i)res;}}coutresendl;return 0;
}
二、递增三元组
2、1 题目描述 题目来源第九届蓝桥杯省赛CB组,第九届蓝桥杯省赛JAVAB组 题目难度简单 题目描述 给定三个整数数组 A[A1,A2,…AN], B[B1,B2,…BN], C[C1,C2,…CN], 请你统计有多少个三元组 (i,j,k) 满足 1≤i,j,k≤NAiBjCk输入格式 第一行包含一个整数 N。 第二行包含 N 个整数 A1,A2,…AN。 第三行包含 N 个整数 B1,B2,…BN。 第四行包含 N 个整数 C1,C2,…CN。 输出格式 一个整数表示答案。 数据范围 1≤N≤1e5, 0≤Ai,Bi,Ci≤1e5。 输入样例 3
1 1 1
2 2 2
3 3 3输出样例 27 2、2 题解关键思路与解答 这道题的暴力枚举的方法很容易想到直接三层循环进行比较。但是时间复杂度为ON^3,是不能全部通过测试用例的。我们仔细分析题目。题目要求AiBjCk。这里A和C都需要与B进行比较且A和C不产生直接联系。所以我们只需要枚举Bj然后找所有Ai比Bj小的数所有Ck比Bj大的数即可。我们这里利用了前缀和来找值优化了时间复杂度。最后将得到的两个数据直接相乘即为答案我们看代码。 #includeiostream
#includecstdio
#includecstring
#includealgorithmusing namespace std;const int N1e510;typedef long long LL;int n;int a[N],b[N],c[N];int as[N],cs[N]; //分别表示的是比b[i]小的个数和比b[i]大的个数
int cnt[N],s[N];int main()
{cinn;for(int i0;in;i){scanf(%d,a[i]);a[i];}for(int i0;in;i){scanf(%d,b[i]);b[i];}for(int i0;in;i){scanf(%d,c[i]);c[i];}//求as[]for(int i0;in;i)cnt[a[i]];for(int i1;iN;i)s[i]s[i-1]cnt[i];for(int i0;in;i)as[i]s[b[i]-1];memset(cnt,0,sizeof(cnt));memset(s,0,sizeof(s));//求cs[]for(int i0;in;i)cnt[c[i]];for(int i1;iN;i)s[i]s[i-1]cnt[i];for(int i0;in;i)cs[i]s[N-1]-s[b[i]];LL res0;for(int i0;in;i)res(LL)as[i]*cs[i];coutresendl;return 0;
}
三、错误票据
3、1 题目描述 题目来源第四届蓝桥杯省赛CA/B组,第四届蓝桥杯省赛JAVAA/B组 题目难度简单 题目描述 某涉密单位下发了某种票据并要在年终全部收回。 每张票据有唯一的ID号。 全年所有票据的ID号是连续的但ID的开始数码是随机选定的。 因为工作人员疏忽在录入ID号的时候发生了一处错误造成了某个ID断号另外一个ID重号。 你的任务是通过编程找出断号的ID和重号的ID。 假设断号不可能发生在最大和最小号。 输入格式 第一行包含整数 N表示后面共有 N 行数据。 接下来 N 行每行包含空格分开的若干个不大于100个正整数不大于100000每个整数代表一个ID号。 输出格式 要求程序输出1行含两个整数 m,n用空格分隔。 其中m表示断号IDn表示重号ID。 数据范围 1≤N≤100 输入样例 2
5 6 8 11 9
10 12 9输出样例 7 9 3、2 题解关键思路与解答 我们先对所有数据进行排序。然后我们会发现连号和中间缺少一个都是有特点的。连号是连续两个相等中间缺少一个的特点是后一个减去前面一个的值为2。本题的难点是在读入。每行的个数不相同且有多行这就给我们的读入造成了很大的困难。我们在这里可以用getline对每行进行读入最后再用户sscanf进行格式化输入。这样我们就可以解决问了。注意在使用getline时我们要想清楚现在的输入缓冲区是否还有 \n、空格之类的。我们结合代码理解一下。 #includeiostream
#includealgorithm
#includesstream
#includecstringusing namespace std;const int N10010;int n;
int a[N];int main()
{int cnt;cincnt;string line;getline(cin,line);while(cnt--){getline(cin,line);stringstream ssin(line);while (ssin a[n]) n ;}sort(a,an);int res1,res2;for(int i1;in;i)if(a[i]a[i-1])res1a[i];else if(a[i]a[i-1]2)res2a[i]-1;coutres2 res1endl;return 0;
}
四、回文日期
4、1 题目描述 题目来源NOIP2016普及组 题目难度简单 题目描述 在日常生活中通过年、月、日这三个要素可以表示出一个唯一确定的日期。 牛牛习惯用 8 位数字表示一个日期其中前 4 位代表年份接下来 2 位代表月份最后 2 位代表日期。 显然一个日期只有一种表示方法而两个不同的日期的表示方法不会相同。 牛牛认为一个日期是回文的当且仅当表示这个日期的 88 位数字是回文的。 现在牛牛想知道在他指定的两个日期之间包含这两个日期本身有多少个真实存在的日期是回文的。 一个 8 位数字是回文的当且仅当对于所有的 i(1≤i≤8) 从左向右数的第 i 个数字和第 9−i 个数字即从右向左数的第 i 个数字是相同的。 例如 对于 2016 年 11 月 19 日用 8 位数字 20161119 表示它不是回文的。对于 2010 年 1 月 22日用8 位数字 20100102 表示它是回文的。对于 2010年 10 月 2 日用 8 位数字 20101002 表示它不是回文的。输入格式 输入包括两行每行包括一个 8 位数字。 第一行表示牛牛指定的起始日期 date1第二行表示牛牛指定的终止日期 date2。保证date1 和 date2 都是真实存在的日期且年份部分一定为 4 位数字且首位数字不为 00。 保证 date1 一定不晚于 date2。 输出格式 输出共一行包含一个整数表示在 date1 和 date2 之间有多少个日期是回文的。 输入样例 20110101
20111231输出样例 1 4、2 题解关键思路与解答 该题要求我们求一个年份区间的回文日期好像很麻烦。我们先想想题目中的日期统一为8位数字。前四位为年后四位分别为月和天。我们不如直接枚举年份从1000枚举到10000然后通过年份制造出一个回文串。再去判断该回文串是否为合法日期。这样似乎做起来很简单。我们来看代码。 #includeiostream
#includecstring
#includealgorithmusing namespace std;int days[13]{0,31,28,31,30,31,30,31,31,30,31,30,31};bool check_date(int date)
{int yeardate/10000;int monthdate%10000/100;int daydate%100;if(month0 || month12)return false;if(day0 || month ! 2 daydays[month])return false;if (month 2){int leap year % 100 year % 4 0 || year % 400 0;if (day 28 leap) return false;}return true;
}
int main()
{int date,date1,date2;int res0;cindate1date2;for(int i1000;i10000;i){datei;int xi;for(int i0;i4;i){datedate*10x%10;x/10;}if(date1date datedate2 check_date(date))res;}coutresendl;return 0;
}五、归并排序 归并排序在蓝桥杯中也是有考到的所以我们也要重点掌握。此篇文章重点算法排序之快速排序、归并排序上篇 对归并排序做出了详解可以参考学习。 今天的学习就到这里希望以上的例题和讲解希望对你有所帮助感谢阅读ovo~
