🍎 博客主页:🌙@披星戴月的贾维斯
🍎 欢迎关注:👍点赞🍃收藏🔥留言
🍇系列专栏:🌙 蓝桥杯
🌙请不要相信胜利就像山坡上的蒲公英一样唾手可得,但是请相信,世界上总有一些美好值得我们全力以赴,哪怕粉身碎骨!🌙
🍉一起加油,去追寻、去成为更好的自己!
蓝桥杯倒计时 19天
提示:以下是本篇文章正文内容,下面案例可供参考
🍎1、递增三元组
🔥1.1题目链接🔥递增三元组
🔥1.2题目描述🔥
给定三个整数数组
A=[A1,A2,…AN]
B=[B1,B2,…BN]
C=[C1,C2,…CN]
请你统计有多少个三元组 (i,j,k)满足:
- 1≤i,j,k≤N
- Ai<Bj<Ck
输入格式:
第一行包含一个整数 N。
第二行包含 N 个整数A1,A2,…AN.
第三行包含 N 个整数 B1,B2,…BN。
第四行包含 N 个整数 C1,C2,…CN。
输出格式
一个整数表示答案。
数据范围
1≤N≤10^5,
0≤Ai,Bi,Ci≤10^5
输入样例:
3
1 1 1
2 2 2
3 3 3
输出样例:
27
🔥1.3分析题意🔥
首先我们先理解题意,有三个数组分别是a[], b[], c[],我们从三个数组中找出a[i] < b[j] < c[k] 的一组数据,这就是递增的三元组。我们自然会想到用for循环暴力枚举i, j, k, 三个值,这样子时间复杂度就是O(n^3),能过6个测试点,在蓝桥杯考式中如果没别的办法,暴力也是不错的。方法1:以i为枚举点,枚举当前b[i]有多少个a[]内的值会小于b[i],c[]内有多上个值会大于b[i].
枚举a数组和c数组是等级的,时间复杂度是o(n * log n)左右。
方法2:哈希加前缀和。
🔥1.4C++代码示例🔥
方法1:
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
typedef long long LL;
int a[N], b[N], c[N];
int main()
{
int n;
cin >> n;
for(int i = 0; i < n; i++) cin >> a[i];
for(int i = 0; i < n; i++) cin >> b[i];
for(int i = 0; i < n; i++) cin >> c[i];
sort(a, a + n), sort(b, b + n), sort(c, c + n);
LL ans = 0, s1 = 0, s2 = 0;//main函数内的值还是要初始化一下,不然会出错
for(int i = 0; i < n; i++)
{
while(s1 < n && a[s1] < b[i]) s1 ++;
while(s2 < n && c[s2] <= b[i]) s2++;
ans += ((LL)s1 *(n - s2));
}
cout << ans << endl;
return 0;
}
方法2:记录用as作为a[]数组的前缀和,
cnt[i]表示以i结尾的a[i]数组出现了多少次
s[i] = cnt[0] + cnt[1] + …cnt[i];
= 在a中, 0 …i 出现多少次
在a[]中有多少数小于b[j] == s[b[j] - 1]
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
typedef long long LL;
int a[N], b[N], c[N];
int as[N], cs[N];//as[i]表示有多少个数小于b[i]
int s[N], cnt[N];
int main()
{
int n;
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]]++; //看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];
//求cs[]
memset(s, 0, sizeof s), memset(cnt, 0, sizeof cnt);
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]];
//枚举每个b[i]
LL res = 0;
for(int i = 0; i < n; i++) res += (LL)as[i] * cs[i];
cout << res << endl;
return 0;
}
🍎2、回文日期
🔥2.1题目链接🔥回文日期
🔥2.2题目描述🔥
在日常生活中,通过年、月、日这三个要素可以表示出一个唯一确定的日期。
牛牛习惯用 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
输出样例:
1
🔥2.3分析题意🔥
首先题目给定data1和data2,我们要计算这个日期跨度内的回文日期,我们就要想到通常我们判断回文的方法和判断日期是否合法的代码,再将两者结合就能得出答案了。但是我们通常想到的可能是i直接从data1 枚举到data2,这样子可能用的时间会更多,代码也不太好写,我们i 从1000开始枚举,data = i; x = i;
data = i * 10 + x % 10, x /= 10; 就是利用i 和i的倒序来构造data.
🔥2.4代码示例🔥
通常我们计算/(判断)回文的方法:
bool huiwen(int n)
{
int i = n;
int m = 0;
while(i)
{
m = m * 10 + i % 10;
i /= 10;
}
if(m == n) return true;
else return false;
}
本题我们把年 + 年翻转过来,再判断日期合不合法就行了。
#include<bits/stdc++.h>
using namespace std;
int a[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30,31};
bool cheak(int n)
{
int y = n / 10000;
int m = n % 10000 / 100;
int d = n % 100;
if(m == 0 || d == 0 || m > 12) return false;
if(m != 2 && d > a[m]) return false;
int leap = y % 4 == 0 && y % 100 != 0 || y % 400 == 0;
if(m == 2)
{
if(d > a[2] + leap) return false;
}
return true;
}
int data1, data2;
int main ()
{
cin >> data1 >> data2;
int res = 0;
for(int i = 1000; i < 10000; i++)
{
int data = i, x = i;
for(int j = 0; j < 4; j++ ) data = data * 10 + x % 10 , x /= 10;
if(data1 <= data && data <= data2 && cheak(data)) res ++;
}
cout << res << endl;
return 0;
}
🍎3、01背包问题
🔥3.1题目链接🔥01背包问题
🔥3.2题目描述🔥
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi,价值是 wi。
求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。
输出最大价值。
输入格式:
第一行两个整数,N,V,用空格隔开,分别表示物品数量和背包容积。
接下来有 N 行,每行两个整数 vi,wi,用空格隔开,分别表示第 i 件物品的体积和价值。
输出格式:
输出一个整数,表示最大价值。
数据范围:
0<N,V≤1000
0<vi,wi≤1000
输入样例:
4 5
1 2
2 4
3 4
4 5
输出样例:
8
🔥3.3分析题意🔥
首先,背包问题都需要我们列出状态转移方程,怎么设计状态转移方程又和每一道题具体相关。以本题为例:我们可以设置一个二维的状态数组f[i][j] : 表示前i个物品,总体积是j的情况下,总价值是多少。最后的结果result = max[f[n][0~v]],f[i][j]对应的两种状态,初始状态f[0][0] = 0;
时间复杂度:二维的数组两层for循环O(N*N),状态转移是O(1)的
所以总的时间复杂度是 O(N * N)。
🔥3.4代码示例🔥
#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
int f[N][N];//状态数组m
int v[N], w[N]; //定义在main函数外面的变量是在堆上,值默认是为0
int n, m;
int main ()
{
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];
f[0][0] = 0;
for(int i = 1; i <= n; i++)
{
for(int j = 0; j <= m; j++)
{
f[i][j] = f[i - 1][j];//表示第一种情况,就是不选择
if(j >= v[i])
f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
}
}
cout << f[n][m] << endl;
return 0;
}
优化代码:
因为当前状态只与上一个状态有关,所以我们可以优化掉一层数组
f[i] [j] = max(f[i] [j], f[i - 1] [j - v[i]] + w[i]);
如果我们去掉一层数组,变成 f[j] = max(f[j], f[j - v[i]] + w[i])。
此时的i是相当于是i - 1的上一个,就是 i
所以我们要从大到小枚举
循环变成了for(f[j] = m; j >= v[i]; j --)
#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
int f[N];//状态数组m
int v[N], w[N]; //定义在main函数外面的变量是在堆上,值默认是为0
int n, m;
int main ()
{
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];
f[0] = 0;
for(int i = 1; i <= n; i++)
{
for(int j = m; j >= v[i]; j--)
{
f[j] = max(f[j], f[j - v[i]] + w[i]);
}
}
cout << f[m] << endl;
return 0;
}
🍎4、 数组切分
🔥4.1题目链接🔥数组切分
🔥4.2题目描述🔥
已知一个长度为 N 的数组:A1,A2,A3…An恰好是 1∼N 的一个排列。现 在要求你将 A 数组切分成若干个 (最少一个, 最多 N 个) 连续的子数组, 并且 每个子数组中包含的整数恰好可以组成一段连续的自然数。
例如对于 A=1,3,2,4, 一共有 5 种切分方法:
1324 : 每个单独的数显然是 (长度为 1 的) 一段连续的自然数。
{1}{3,2}{4}:{3,2} 包含 2 到 3 , 是 一段连续的自然数, 另外 {1} 和 {4} 显然 也是。
{1}{3,2,4}:{3,2,4} 包含 2 到 4 , 是一段连续的自然数, 另外 {1}显然也是。
{1,3,2}{4}:{1,3,2} 包含 1 到 3 , 是 一段连续的自然数, 另外 {4} 显然也是。
{1,3,2,4} : 只有一个子数组, 包含 1 到 4 , 是 一段连续的自然数。
输入格式:
第一行包含一个整数 N。第二行包含 N个整数, 代表 A 数组。
输出格式
输出一个整数表示答案。由于答案可能很大, 所以输出其对 1000000007 取 模后的值
样例输入:
4
1 3 2 4
样例输出
5
🔥4.3分析题意🔥
**首先,比较难从题目中直接看出来这道题的算法是01背包的,知道本题的算法之后,我们遍历原数组的每一个数,判断这个数是否可以划分出多少子数组符合条件,因为本题是一段连续的自然数,1 - N,所以区间最大值 - 区间最小值 = 区间长度,就说明区间数值连续,我们可以设置一个f[]状态数组,其中f[0]=1;表示每一个数单独都是一种方案。状态转移方程: f[i]=(f[i]+f[j-1]) % mod; f[i]考虑前i个排列的情况,如果[j, i]区间满足,则f[i] = f[i] + f[j - 1]
代码示例:文章来源:https://www.toymoban.com/news/detail-796645.html
#include<bits/stdc++.h>
using namespace std;
const int mod = 1000000007;
const int N=10010;
int n;
int a[N];
int f[N];
void solve()
{
cin>>n;
for(int i=1; i<=n; i++) cin>>a[i];
f[0]=1;//每一个数单独都是一种方案
for(int i=1;i<=n;i++)//遍历原数组的每一个数,判断这个数是否可以划分出多少队列
{
int mx=0 ,mi = n + 1;
for(int j=i; j>=1; j--)
{
mx= max(mx, a[j]);
mi= min(mi, a[j]);
if(mx-mi==i-j)//区间最大值 - 区间最小值 = 区间长度,就说明区间数值连续
{
f[i]=(f[i]+f[j-1]) % mod;//f[i]考虑前i个排列的情况,如果[j, i]区间满足,则f[i] = f[i] + f[j - 1]
}
}
}
cout<<f[n]<<endl;
}
int main()
{
solve();
return 0;
}
🍎5、总结
本文向大家介绍了递增三元组、回文日期、01背包问题、 数组切分等,涉及了前缀和,动态规划等算法希望大家读后也能有所收获!文章来源地址https://www.toymoban.com/news/detail-796645.html
到了这里,关于【冲刺蓝桥杯-真题训练】递增三元组、回文日期、01背包问题、 数组切分的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!