【冲刺蓝桥杯-真题训练】递增三元组、回文日期、01背包问题、 数组切分

这篇具有很好参考价值的文章主要介绍了【冲刺蓝桥杯-真题训练】递增三元组、回文日期、01背包问题、 数组切分。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

🍎 博客主页:🌙@披星戴月的贾维斯
🍎 欢迎关注:👍点赞🍃收藏🔥留言
🍇系列专栏:🌙 蓝桥杯
🌙请不要相信胜利就像山坡上的蒲公英一样唾手可得,但是请相信,世界上总有一些美好值得我们全力以赴,哪怕粉身碎骨!🌙
🍉一起加油,去追寻、去成为更好的自己!

蓝桥杯倒计时 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]

代码示例:

#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模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【蓝桥杯冲刺】蓝桥杯11届省赛C++b组真题-填空题

    目录 试题A:门牌制作 解题思路: 答案: 试题B:既约分数 解题思路: 答案: 试题C:蛇形填数 解题思路: 答案: 试题D:跑步训练 解题思路: 答案: 试题E:七段码 解题思路: 答案: 写在最后: 小蓝要为一条街的住户制作门牌号。 这条街一共有 2020 位住户,门牌号从

    2023年04月19日
    浏览(60)
  • 【蓝桥杯冲刺】蓝桥杯12届省赛C++b组真题-填空题

    目录 试题A:空间 解题思路 答案 试题B:卡片 解题思路 答案 试题C:直线 解题思路 答案 试题D:货物摆放 解题思路 答案 试题E:路径 解题思路 答案 ​编辑 写在最后: 小蓝准备用 256 MB 的内存空间开一个数组, 数组的每个元素都是 32 位二进制整数, 如果不考虑程序占用的

    2024年02月03日
    浏览(40)
  • 蓝桥杯回文日期判断

    思想: 对于回文数的判断方法,最快的就是取其中一半的字符串长度,为s,然后将其进行翻转为s’ ,再把两者进行拼接即可保证是回文数,这样子就解决了枚举所有回文数的问题。 注意点: 要求必须是有效日期 注意闰年的2月份问题 代码: (1)判断所给字符串是不是回

    2024年01月18日
    浏览(41)
  • 回文日期 (蓝桥云) JAVA

    2020 年春节期间,有一个特殊的日期引起了大家的注意:2020 年 2 月 2 日。因为如果将这个日期按 “yyyymmdd” 的格式写成一个 8 位数是 20200202,恰好是一个回文数。我们称这样的日期是回文日期。 有人表示 20200202 是 “千年一遇” 的特殊日子。对此小明很不认同,因为不到

    2023年04月08日
    浏览(49)
  • 蓝桥杯-回文日期[Java]

    学习目标: 学习内容: 学习时间: 题目: 题目描述: 输入描述: 输出描述: 输入输出样例: 示例 1: 运行限制: 题解: 思路: 刷蓝桥杯题库日记 编号498 题目回文日期 难度困难 2023/11/4 17:00 题目描述: 2020 年春节期间,有一个特殊的日期引起了大家的注意:2020 年 2 月 2 日。因为如

    2024年02月05日
    浏览(44)
  • 【蓝桥杯冲刺】蓝桥杯13届省赛C++b组真题-A~E题

    目录 试题A:九进制转十进制 解题思路 答案 试题B:顺子日期 解题思路 答案 试题C:刷题统计 题解思路 代码 试题D:修建灌木 解题思路 代码 试题E:X进制减法 解题思路 代码 写在最后: 九进制正整数 (2022)  转换成十进制等于多少? 直接转就完了。 小明特别喜欢顺子。

    2023年04月24日
    浏览(40)
  • 第十四届蓝桥杯三月真题刷题训练——第 21 天

    目录 第 1 题:灭鼠先锋 问题描述 运行限制 代码: 思路: 第 2 题:小蓝与钥匙 问题描述 答案提交 运行限制 代码: 思路 : 第 3 题:李白打酒加强版  第 4 题:机房  问题描述 本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结果输出即可。 灭鼠先锋是一个

    2023年04月08日
    浏览(100)
  • 第十四届蓝桥杯三月真题刷题训练——第 1 天

    目录 题目1:数列求值 代码: 题目2:质数 代码: 题目3:饮料换购 代码: 题目描述 本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结果输出即可。 给定数列 1,1,1,3,5,9,17,⋯1,1,1,3,5,9,17,⋯,从第 44 项开始,每项都是前 33 项的和。 求第 2019032420190324 项的最后

    2023年04月09日
    浏览(56)
  • 递增的三元子序列

    递增的三元子序列 1 = nums.length = 500000 子序列的三个元素在原数组中可以不是连续的 实现时间复杂度为 O(n) ,空间复杂度为 O(1) 的解决方案 使用贪心算法,在遍历数组时,要记录当前数组中的最小值minVal (方便找第二小的值)以及递增二元组中的较大值tupleMaxVal (方便找递

    2024年01月23日
    浏览(35)
  • 334. 递增的三元子序列

    首先想到的方法是维护左最小值和右最大值数组,然后判断是否当前值为中间值。 看了题解后发现了一个很棒的法,时间复杂度O(N),空间复杂度O(1). 首先,维护第一第二个数两个变量,如果当前数大于第二数则存在三元组,如果大于第一数则更新第二数,否则更新第一数。

    2024年02月15日
    浏览(32)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包