前言
✨本博客讲解 蓝桥杯C/C++ 备赛所涉及算法知识，此博客为第八讲：枚举与模拟【例题】
本篇博客所包含习题有：
👊连号区间数
👊递增三元组
👊特别数的和
👊错误票据
👊回文日期
枚举与模拟【习题】见博客：蓝桥杯第八讲–枚举与模拟【习题】
博客内容以题代讲，通过讲解题目的做法来帮助读者快速理解算法内容，需要注意：学习算法不能光过脑，更要实践，请读者务必自己敲写一遍本博客相关代码！！！
连号区间数
来源： 第四届蓝桥杯省赛C++B组,第四届蓝桥杯省赛JAVAB组
题目要求
题目描述：
输入格式：
第一行是一个正整数 N ，表示排列的规模。
第二行是 N 个不同的数字Pi，表示这 N 个数字的某一排列。
输出格式：
输出一个整数，表示不同连号区间的数目。
数据范围：
输入样例1：
4
3 2 4 1
输出样例1：
7
输入样例2：
5
3 4 2 5 1
输出样例2：
9
样例解释：
第一个用例中，有 7 个连号区间分别是：[1,1],[1,2],[1,3],[1,4],[2,2],[3,3],[4,4]
第二个用例中，有 9 个连号区间分别是：[ 1 , 1 ] , [ 1 , 2 ] , [ 1 , 3 ] , [ 1 , 4 ] , [ 1 , 5 ] , [ 2 , 2 ] , [ 3 , 3 ] , [ 4 , 4 ] , [ 5 , 5 ]
思路分析
代码
#include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int N = 10010; int a[N]; int main() { int n; scanf("%d", &n); for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]); int res = 0; for (int i = 0; i < n; i ++ ) { int maxv = -N, minv = N; for (int j = i; j < n; j ++ ) { maxv = max(maxv, a[j]); minv = min(minv, a[j]); if (maxv - minv == j - i) res ++; } } printf("%d\n", res); return 0; }
递增三元组
来源： 第九届蓝桥杯省赛C++B组,第九届蓝桥杯省赛JAVAB组
题目要求
题目描述：
输入格式：
输出格式：
一个整数表示答案。
数据范围：
输入样例：
3
1 1 1
2 2 2
3 3 3
输出样例：
27
思路分析
本题有三种求法，对应三个不同的算法思维，分别为：
- 前缀和
- 二分
- 双指针
在本博客中，只介绍前两种代码，双指针的解法会在本蓝桥杯专栏的双指针一讲中进行讲解。双指针做法见博文：蓝桥杯第十一讲–双指针【例/习题】
前缀和
前缀和的具体知识概念讲解见博客：蓝桥杯第四讲–前缀和【例题】
前缀和【习题】详见博客：蓝桥杯第四讲–前缀和【习题】
前缀和算法模板详见博客：前缀和算法模板
下面来对前缀和进行讲解：
二分
二分的具体知识概念讲解见博客：蓝桥杯第三讲–二分【例题】
二分【习题】详见博客：蓝桥杯第三讲–二分【习题】
二分的模板详细见博客：二分算法模板
下面来对二分进行讲解：
代码（前缀和）
#include <cstdio> #include <algorithm> #include <cstring> using namespace std; typedef long long LL; const int N = 100010; int a[N], b[N], c[N]; int s[N], cnt[N]; int as[N]; // as[i]表示在a中有多少个元素小于b[i] int cs[N]; // cs[i]表示在c中有多少个元素大于b[i] int main() { int n; scanf("%d", &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]; printf("%lld\n", res); return 0; }
代码（二分）
#include <cstdio> #include <algorithm> #include <cstring> using namespace std; typedef long long LL; const int N = 100010; int n; int a[N], b[N], c[N]; int finda(int u) { int l = 0, r = n - 1; while (l < r) { int mid = l + r + 1 >> 1; if (a[mid] >= b[u]) r = mid - 1; else l = mid; } if (l == 0 && a[l] < b[u]) return 1; else if (l == 0 && a[l] >= b[u]) return 0; return l + 1; } int findc(int u) { int l = 0, r = n - 1; while (l < r) { int mid = l + r >> 1; if (c[mid] <= b[u]) l = mid + 1; else r = mid; } if (l == n - 1 && c[l] > b[u]) return 1; else if (l == n - 1 && c[l] <= b[u]) return 0; return (n - 1 - l + 1); } int main() { scanf("%d", &n); for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]); for (int i = 0; i < n; i ++ ) scanf("%d", &b[i]); for (int i = 0; i < n; i ++ ) scanf("%d", &c[i]); sort(a, a + n); sort(b, b + n); sort(c, c + n); LL res = 0; for (int i = 0; i < n; i ++ ) { int resa = finda(i); int resc = findc(i); res += (LL)resa * resc; } printf("%lld\n", res); return 0; }
