递增三元组

个连号区间分别是[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]

第二个用例中有

个连号区间分别是[1,1],[1,2],[1,3],[1,4],[1,5],[2,2],[3,3],[4,4],[5,5]

1、2

中没有重复的数据且所有数据都会出现一次。

题目大概意思是给我们一组数据是乱序的。

然后我们需要在这组数据中任选一段连续区间看是否能组成“连续”数列。

我们第一想到的是两层for循环枚举区间在对区间排序判断是否为“连续”数列。

这样时间复杂度显然是不能通过题中所有案例的。

我们仔细观察区间数值不会重复那么区间的最大值减去区间的最小值等于区间下标相减。

这样大大提高了效率我们结合代码一起理解一下。

#includeiostream

ji;jn;j){maxcmax(maxc,a[j]);mincmin(minc,a[j]);if(maxc-mincj-i)res;}}coutresendl;return

二、递增三元组

这道题的暴力枚举的方法很容易想到直接三层循环进行比较。

但是时间复杂度为ON^3,是不能全部通过测试用例的。

我们仔细分析题目。

题目要求AiBjCk。

这里A和C都需要与B进行比较且A和C不产生直接联系。

所以我们只需要枚举Bj然后找所有Ai比Bj小的数所有Ck比Bj大的数即可。

我们这里利用了前缀和来找值优化了时间复杂度。

最后将得到的两个数据直接相乘即为答案我们看代码。

#includeiostream

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

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

i1;iN;i)s[i]s[i-1]cnt[i];for(int

res0;for(int

i0;in;i)res(LL)as[i]*cs[i];coutresendl;return

三、错误票据

题目来源第四届蓝桥杯省赛CA/B组,第四届蓝桥杯省赛JAVAA/B组

题目难度简单

因为工作人员疏忽在录入ID号的时候发生了一处错误造成了某个ID断号另外一个ID重号。

输入格式

行每行包含空格分开的若干个不大于100个正整数不大于100000每个整数代表一个ID号。

输出格式

我们先对所有数据进行排序。

然后我们会发现连号和中间缺少一个都是有特点的。

连号是连续两个相等中间缺少一个的特点是后一个减去前面一个的值为2。

本题的难点是在读入。

每行的个数不相同且有多行这就给我们的读入造成了很大的困难。

我们在这里可以用getline对每行进行读入最后再用户sscanf进行格式化输入。

这样我们就可以解决问了。

注意在使用getline时我们要想清楚现在的输入缓冲区是否还有

#includeiostream

line;getline(cin,line);while(cnt--){getline(cin,line);stringstream

ssin(line);while

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

在日常生活中通过年、月、日这三个要素可以表示出一个唯一确定的日期。

牛牛习惯用

显然一个日期只有一种表示方法而两个不同的日期的表示方法不会相同。

现在牛牛想知道在他指定的两个日期之间包含这两个日期本身有多少个真实存在的日期是回文的。

i(1≤i≤8)

该题要求我们求一个年份区间的回文日期好像很麻烦。

我们先想想题目中的日期统一为8位数字。

前四位为年后四位分别为月和天。

我们不如直接枚举年份从1000枚举到10000然后通过年份制造出一个回文串。

再去判断该回文串是否为合法日期。

这样似乎做起来很简单。

我们来看代码。

#includeiostream

days[13]{0,31,28,31,30,31,30,31,31,30,31,30,31};bool

check_date(int

i0;i4;i){datedate*10x%10;x/10;}if(date1date

datedate2

check_date(date))res;}coutresendl;return

}五、归并排序

归并排序在蓝桥杯中也是有考到的所以我们也要重点掌握。

此篇文章重点算法排序之快速排序、归并排序上篇

今天的学习就到这里希望以上的例题和讲解希望对你有所帮助感谢阅读ovo~