[蓝桥杯] 枚举、模拟和排列问题

逃离我推掉我的手 2023-09-26 18:22 82阅读 0赞

![ee8a034f0946470e89e17d7d93d6dd9a.gif][]

> **文章目录**
> 
> 一、连号区间数 
> 
> 1、1 题目描述
> 
> 1、2 题解关键思路与解答
> 
> 二、递增三元组
> 
> 2、1 题目描述
> 
> 2、2 题解关键思路与解答
> 
> 三、错误票据
> 
> 3、1 题目描述
> 
> 3、2 题解关键思路与解答
> 
> 四、回文日期
> 
> 4、1 题目描述
> 
> 4、2 题解关键思路与解答
> 
> 五、归并排序
> 
> --------------------
> 
> ## 标题：蓝桥杯——枚举、模拟和排列习题训练 ##
> 
> ## 作者：@Ggggggtm ##
> 
> ## 寄语：与其忙着诉苦，不如低头赶路，奋路前行，终将遇到一番好风景 ##
> 
> ![fafa6bb132e64a8b99b56704546601e7.png][]

## 一、连号区间数 ##

### 1、1 题目描述 ###

> **题目来源：**第四届蓝桥杯省赛C++B组,第四届蓝桥杯省赛JAVAB组
> 
> **题目难度：**简单
> 
> **题目描述：**
> 
> 小明这些天一直在思考这样一个奇怪而有趣的问题：
> 
> 在 1∼N 的某个排列中有多少个连号区间呢？
> 
> 这里所说的连号区间的定义是：
> 
> 如果区间 \[L,R\] 里的所有元素（即此排列的第 L 个到第 R 个元素）递增排序后能得到一个长度为 R−L+1 的“连续”数列，则称这个区间连号区间。
> 
> 当 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循环枚举区间，在对区间排序，判断是否为“连续”数列。这样时间复杂度显然是不能通过题中所有案例的。我们仔细观察，**区间数值不会重复，那么区间的最大值减去区间的最小值等于区间下标相减**。这样大大提高了效率，我们结合代码一起理解一下。

#include<iostream>
    #include<algorithm>
    #include<cstring>
    
    using namespace std;
    
    int n;
    
    const int N =10010;
    const int MAX=-1e8,MIN=1e8;
    
    int a[N];
    
    int main()
    {
        cin>>n;
        for(int i=0;i<n;i++)
            cin>>a[i];
        
        int res=0;
        for(int i=0;i<n;i++)
        {
            int maxc=MAX,minc=MIN;
            for(int j=i;j<n;j++)
            {
                maxc=max(maxc,a[j]);
                minc=min(minc,a[j]);
                if(maxc-minc==j-i)
                    res++;
            }
        }
        
        cout<<res<<endl;
        return 0;
    }

## 二、递增三元组 ##

### 2、1 题目描述 ###

> **题目来源：**第九届蓝桥杯省赛C++B组,第九届蓝桥杯省赛JAVAB组
> 
> **题目难度：**简单
> 
> **题目描述：**
> 
> 给定三个整数数组
> 
> 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。
> 
> 输出格式
> 
> 一个整数表示答案。
> 
> 数据范围
> 
> 1≤N≤1e5,  
> 0≤Ai,Bi,Ci≤1e5。
> 
> **输入样例：**
> 
>     3
>     1 1 1
>     2 2 2
>     3 3 3
> 
> **输出样例：**
> 
>     27

### 2、2 题解关键思路与解答 ###

> 这道题的暴力枚举的方法很容易想到，直接三层循环，进行比较。但是时间复杂度为O（N^3）,是不能全部通过测试用例的。我们仔细分析题目。**题目要求：Ai<Bj<Ck**。这里**A和C都需要与B进行比较，且A和C不产生直接联系**。所以**我们只需要枚举Bj，然后找所有Ai比Bj小的数，所有Ck比Bj大的数即可**。我们这里利用了前缀和来找值，优化了时间复杂度。最后将得到的两个数据直接相乘即为答案，我们看代码。

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    
    using namespace std;
    
    const int N=1e5+10;
    
    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()
    {
        cin>>n;
        
        for(int i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
            a[i]++;
        }
        
        for(int i=0;i<n;i++)
        {
            scanf("%d",&b[i]);
            b[i]++;
        }
        
        for(int i=0;i<n;i++)
        {
            scanf("%d",&c[i]);
            c[i]++;
        }
        
        //求as[]
        for(int i=0;i<n;i++)
            cnt[a[i]]++;
        for(int i=1;i<N;i++)
            s[i]=s[i-1]+cnt[i];
        for(int i=0;i<n;i++)
            as[i]=s[b[i]-1];
        
        memset(cnt,0,sizeof(cnt));
        memset(s,0,sizeof(s));
        //求cs[]
        for(int i=0;i<n;i++)
            cnt[c[i]]++;
        for(int i=1;i<N;i++)
            s[i]=s[i-1]+cnt[i];
        for(int i=0;i<n;i++)
            cs[i]=s[N-1]-s[b[i]];
        
        LL res=0;
        for(int i=0;i<n;i++)
            res+=(LL)as[i]*cs[i];
        
        cout<<res<<endl;
        return 0;
    }

## 三、错误票据 ##

### 3、1 题目描述 ###

> **题目来源：**第四届蓝桥杯省赛C++A/B组,第四届蓝桥杯省赛JAVAA/B组
> 
> **题目难度：**简单
> 
> **题目描述：**
> 
> 某涉密单位下发了某种票据，并要在年终全部收回。
> 
> 每张票据有唯一的ID号。
> 
> 全年所有票据的ID号是连续的，但ID的开始数码是随机选定的。
> 
> 因为工作人员疏忽，在录入ID号的时候发生了一处错误，造成了某个ID断号，另外一个ID重号。
> 
> 你的任务是通过编程，找出断号的ID和重号的ID。
> 
> 假设断号不可能发生在最大和最小号。
> 
> **输入格式：**
> 
> 第一行包含整数 N，表示后面共有 N 行数据。
> 
> 接下来 N 行，每行包含空格分开的若干个（不大于100个）正整数（不大于100000），每个整数代表一个ID号。
> 
> **输出格式：**
> 
> 要求程序输出1行，含两个整数 m,n，用空格分隔。
> 
> 其中，m表示断号ID，n表示重号ID。
> 
> **数据范围：**
> 
> 1≤N≤100，
> 
> **输入样例：**
> 
>     2
>     5 6 8 11 9 
>     10 12 9
> 
> **输出样例：**
> 
>     7 9

### 3、2 题解关键思路与解答 ###

> 我们先对所有数据进行排序。然后我们会发现连号和中间缺少一个都是有特点的。连号是连续两个相等，中间缺少一个的特点是后一个减去前面一个的值为2。本题的难点是在读入。每行的个数不相同，且有多行，这就给我们的读入造成了很大的困难。我们在这里可以用getline对每行进行读入，最后再用户sscanf进行格式化输入。这样我们就可以解决问了。注意，在使用getline时，我们要想清楚现在的输入缓冲区是否还有 '\\n'、空格之类的。我们结合代码理解一下。

#include<iostream>
    #include<algorithm>
    #include<sstream>
    #include<cstring>
    
    using namespace std;
    
    const int N=10010;
    
    int n;
    int a[N];
    
    int main()
    {
        int cnt;
        cin>>cnt;
        string line;
        
        getline(cin,line);
        
        while(cnt--)
        {
            getline(cin,line);
            stringstream ssin(line);
            
            while (ssin >> a[n]) n ++ ;
        }
        
        sort(a,a+n);
        
        int res1,res2;
        for(int i=1;i<n;i++)
            if(a[i]==a[i-1])
                res1=a[i];
            else if(a[i]==a[i-1]+2)
                res2=a[i]-1;
        cout<<res2<<' '<<res1<<endl;
        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，然后通过年份制造出一个回文串。再去判断该回文串是否为合法日期**。这样似乎做起来很简单。我们来看代码。

#include<iostream>
    #include<cstring>
    #include<algorithm>
    
    using namespace std;
    
    int days[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
    
    bool check_date(int date)
    {
        int year=date/10000;
        int month=date%10000/100;
        int day=date%100;
        
        if(month==0 || month>12)
            return false;
        
        if(day==0 || month != 2 && day>days[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 res=0;
        cin>>date1>>date2;
        for(int i=1000;i<10000;i++)
        {
            date=i;
            int x=i;
            for(int i=0;i<4;i++)
            {
                date=date*10+x%10;
                x/=10;
            }
            
            if(date1<=date && date<=date2 && check_date(date))
                res++;
        }
        
        cout<<res<<endl;
        return 0;
    }

## 五、归并排序 ##

> 归并排序在蓝桥杯中也是有考到的，所以我们也要重点掌握。此篇文章：[重点算法排序之快速排序、归并排序（上篇）][Link 1] 对归并排序做出了详解，可以参考学习。

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

[ee8a034f0946470e89e17d7d93d6dd9a.gif]: https://img-blog.csdnimg.cn/ee8a034f0946470e89e17d7d93d6dd9a.gif
[fafa6bb132e64a8b99b56704546601e7.png]: https://img-blog.csdnimg.cn/fafa6bb132e64a8b99b56704546601e7.png
[Link 1]: https://blog.csdn.net/weixin_67596609/article/details/128524405