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

• 算法结构

🍎 博客主页：🌙@披星戴月的贾维斯

🍎 欢迎关注：👍点赞🍃收藏🔥留言

🍇系列专栏：🌙 蓝桥杯

🌙请不要相信胜利就像山坡上的蒲公英一样唾手可得，但是请相信，世界上总有一些美好值得我们全力以赴，哪怕粉身碎骨！🌙

🍉一起加油，去追寻、去成为更好的自己！

蓝桥杯倒计时 19天

在这里插入图片描述

文章目录

  • 🍎1、递增三元组
  • 🍎2、回文日期
  • 🍎3、01背包问题
  • 🍎4、 数组切分
  • 🍎5、总结

提示：以下是本篇文章正文内容，下面案例可供参考

🍎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 
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 > a[i];

  for(int i = 0; i > b[i];
  for(int i = 0; i > 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 
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
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
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 > v[i] >> w[i];
    f[0][0] = 0;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 0; 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
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 > v[i] >> w[i];
    f[0] = 0;
    for(int i = 1; i = 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
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>a[i];
    f[0]=1;//每一个数单独都是一种方案
    for(int i=1;i=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.net2asp.com/2d97bf9101.html

赞 (0)
« 上一篇 1天前
下一篇 » 1天前

相关推荐