蓝桥杯 --- 枚举、模拟与排序

枚举
- 1210. 连号区间数（枚举 + 优化）
- 1236. 递增三元组（前缀和 + 枚举）
- 1245. 特别数的和（枚举）
模拟
- 1204. 错误票据（模拟 + 排序）
- 466. 回文日期（模拟 + 枚举）
排序
- 787. 归并排序（排序）

枚举

1210. 连号区间数（枚举 + 优化）

小明这些天一直在思考这样一个奇怪而有趣的问题：

在 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：

输入样例2：

5
3 4 2 5 1

输出样例2：

样例解释
第一个用例中，有 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]

题目分析

数据范围是 10000，直接暴力的会是 n² 的复杂度，一般会直接挂掉，所以时间复杂度一般要控制在 nlogn
优化点：1 ~ N，隐含这数字不重复
因此：[ l，r ] 如果是满足条件的区间在其中一定是有 r - l + 1 个数

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<stack>
#include<queue>
#include<sstream>

using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 100010;
const int MOD = 100000007;

int a[N];

int main()
{
	int n;
	cin >> n;
	int ans = 0;
	for(int i = 0; i < n; i ++ ) cin >> a[i];
	for(int i = 0; i < n; i ++ )
	{
		int maxx = -0x3f3f3f3f, minn = 0x3f3f3f3f; 
		for(int j = i; j < n; j ++ ) 
		{
			maxx = max(maxx, a[j]);
			minn = min(minn, a[j]);
			if(j - i == maxx - minn) ans ++ ;
		}
	}	
	cout << ans << endl;
	return 0;
}

1236. 递增三元组（前缀和 + 枚举）

给定三个整数数组

A=[A₁,A₂,…A_N],
B=[B₁,B₂,…B_N],
C=[C₁,C₂,…C_N],

请你统计有多少个三元组 (i,j,k) 满足：

1≤i,j,k≤N
A_i<B_j<C_k
输入格式
第一行包含一个整数 N。

第二行包含 N 个整数 A₁,A₂,…A_N。

第三行包含 N 个整数 B₁,B₂,…B_N。

第四行包含 N 个整数 C₁,C₂,…C_N。

输出格式
一个整数表示答案。

数据范围

1≤N≤10⁵,
0≤A_i,B_i,C_i≤105

输入样例：

输出样例：

题目分析

数据范围 10⁵
直接暴力的话，三次for循环，时间复杂度直接爆掉
时间复杂度反推可知，复杂度应该是 O(n) 或者 O(nlogn)
因此我们可以知道，最多只能枚举一次 for 循环
优化点：
三个数组是相互独立的，换句话说就是，如果我们要知道小于 B_i 大于 B_i 的三元组有多少个话，我们就只需要知道在 A 中小于 B_i 的个数，然后知道在 C 中大于 B_i 的个数，直接相乘就 OK 了，由此我们可以推断出，需要枚举的 for 应该就是 B 了
根据上面的分析我们可以用 sort + 二分求解
这里给出另外一种求解方法，前缀和
首先我们利用一个 cnt 数组来存储 a[ i ] 出现了多少次，然后 s 数组存储 cnt 数组的前缀和，那么当我们要得到小于 B_i 的数有多少时，就直接是 s[ B_i-1 ]
对于大于 B_i 的数同理可知

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<stack>
#include<queue>
#include<sstream>

using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 100010;
const int MOD = 1000000007;
const int INF = 0x3f3f3f3f;

int a[N], b[N], c[N];
int as[N], cs[N];
int cnt[N], s[N]; 

int main()
{
	int n;
	cin >> n;
	for(int i = 0; i < n; i ++ ) cin >> a[i], a[i] ++ ; 
	for(int i = 0; i < n; i ++ ) cin >> b[i], b[i] ++ ;
	for(int i = 0; i < n; i ++ ) cin >> c[i], c[i] ++ ;
	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);
	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;
}

1245. 特别数的和（枚举）

小明对数位中含有 2、0、1、9 的数字很感兴趣（不包括前导 0），在 1 到 40 中这样的数包括 1、2、9、10 至 32、39 和 40，共 28 个，他们的和是 574。

请问，在 1 到 n 中，所有这样的数的和是多少？

输入格式
共一行，包含一个整数 n。

输出格式
共一行，包含一个整数，表示满足条件的数的和。

数据范围

1≤n≤10000

输入样例：

输出样例：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<stack>
#include<queue>
#include<sstream>

using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 100010;
const int MOD = 1000000007;
const int INF = 0x3f3f3f3f;

int main()
{
	int n;
	cin >> n;
	int ans = 0;
	for(int i = 1; i <= n; i ++ )
	{
		int x = i;
		while(x)
		{
			int t = x % 10;
			x /= 10;
			if(t == 0 || t == 1 || t == 2 || t == 9)
			{
				ans += i ;
				break;
			}
		}
	}
	cout << ans << endl;
	return 0;
}

模拟

1204. 错误票据（模拟 + 排序）

某涉密单位下发了某种票据，并要在年终全部收回。

每张票据有唯一的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

题目分析

直接排序 + 模拟即可

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<stack>
#include<queue>
#include<sstream>

using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 10010;
const int MOD = 1000000007;
const int INF = 0x3f3f3f3f;

int idx;
int n, m;
int a[N];

int main()
{
	int cnt;
	cin >> cnt;
	string line;
	getchar();
	while(cnt -- )
	{
		getline(cin, line);
		stringstream ssin(line);
		while(ssin >> a[idx]) idx ++ ;
	}
	sort(a, a + idx);
	for(int i = 1; i < idx; i ++ )
		if(a[i] == a[i - 1]) n = a[i];
		else if(a[i] != a[i - 1] + 1) m = a[i] - 1;
	cout << m << ' ' << n << endl;
	return 0;
}

466. 回文日期（模拟 + 枚举）

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

牛牛习惯用 8 位数字表示一个日期，其中，前 4 位代表年份，接下来 2 位代表月份，最后 2 位代表日期。

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

牛牛认为，一个日期是回文的，当且仅当表示这个日期的 8 位数字是回文的。

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

一个 8 位数字是回文的，当且仅当对于所有的 i(1≤i≤8) 从左向右数的第 i 个数字和第 9−i 个数字（即从右向左数的第 i 个数字）是相同的。

例如：

对于 2016 年 11 月 19 日，用 8 位数字 20161119 表示，它不是回文的。
对于 2010 年 1 月 2 日，用 8 位数字 20100102 表示，它是回文的。
对于 2010 年 10 月 2 日，用 8 位数字 20101002 表示，它不是回文的。

输入格式
输入包括两行，每行包括一个 8 位数字。

第一行表示牛牛指定的起始日期 date1，第二行表示牛牛指定的终止日期 date2。保证 date1 和 date2 都是真实存在的日期，且年份部分一定为 4 位数字，且首位数字不为 0。

保证 date1 一定不晚于 date2。

输出格式
输出共一行，包含一个整数，表示在 date1 和 date2 之间，有多少个日期是回文的。

输入样例：

20110101
20111231

输出样例：

题目分析

如果我们直接枚举给定的两个时间的所有时间，肯定是十分复杂的
我们可以稍微转化一下思路，如果某个时间是回文数的话，那么它前四个数字和后四个数字构成回文
因此我们可以仅仅枚举前面四个数字，后面的四个数字就是前面四个数字的倒数，我们对于这样构成的一个时间来进行判断，是否是符合要求的时间

时间是在给定的时间范围之内
月份的日期都是符合要求的
符合闰年和平年对应的月份和日期限制

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<stack>
#include<queue>
#include<sstream>

using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 100010;
const int MOD = 1000000007;
const int INF = 0x3f3f3f3f;

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

bool check(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 date1, date2;
	cin >> date1 >> date2;
	int res = 0;
	for(int i = 1000; i < 10000; i ++ )
	{
		int date = i, x = i;
		for(int j = 0; j < 4; j ++ ) date = date * 10 + x % 10, x /= 10;
		if(date1 <= date && date <= date2 && check(date)) res ++ ;
	}
	cout << res << endl;
	return 0;
}

排序

787. 归并排序（排序）

给定你一个长度为 n 的整数数列。

请你使用归并排序对这个数列按照从小到大进行排序。

并将排好序的数列按顺序输出。

输入格式
输入共两行，第一行包含整数 n。

第二行包含 n 个整数（所有整数均在 1∼10⁹ 范围内），表示整个数列。

输出格式
输出共一行，包含 n 个整数，表示排好序的数列。

数据范围

1≤n≤100000

输入样例：

5
3 1 2 4 5

输出样例：

1 2 3 4 5

题目分析

在算法中，对于需要排序的题目，我们 99.99% 都不需要自己写排序算法，直接调用 sort 快速排序即可
啊哈哈哈哈哈

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<stack>
#include<queue>
#include<sstream>

using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 100010;
const int MOD = 1000000007;
const int INF = 0x3f3f3f3f;

int a[N];

int main()
{
	int n;
	cin >> n;
	for(int i = 0; i < n; i ++ ) cin >> a[i];
	sort(a, a + n);
	for(int i = 0; i < n; i ++ ) cout << a[i] << ' ';
	return 0;
}

蓝桥杯 --- 枚举、模拟与排序

蓝桥杯 --- 枚举、模拟与排序

枚举

1210. 连号区间数（枚举 + 优化）

1236. 递增三元组（前缀和 + 枚举）

1245. 特别数的和（枚举）

模拟

1204. 错误票据（模拟 + 排序）

466. 回文日期（模拟 + 枚举）

排序

787. 归并排序（排序）

相关文章

mysql5.6 多实例_centos7环境下创建mysql5.6多实例的方法详解

跨专业学计算机应用好学吗,我是学计算机软件工程的，想跨专业考金融的研 – 手机爱问...

JVM, JRE 和JDK

java 根据圆心计算圆弧上点的经纬度_图文教你怎样用折弯机折出圆弧？

1231. 航班时间（模拟）

sqlserver锁大全

sysbench磁mysql压力测试_使用Sysbench对MySQL进行压力测试

奥鹏2018秋计算机应用基础答案,奥鹏东师2018年春季《计算机应用基础》期末考核参考答案(可直接上传)...