冲刺蓝桥杯-真题训练不同子串、特殊日期、左移右移、卡牌

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

---

🍎1、不同子串

🔥1.1题目链接🔥不同子串

🔥1.2题目描述🔥
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

一个字符串的非空子串是指字符串中长度至少为 11 的连续的一段字符组成的串。例如，字符串 aaabaaab 有非空子串 aa, bb, aaaa, abab, aaaaaa, aabaab, aaabaaab，一共 7 个。注意在计算时，只算本质不同的串的个数。

请问，字符串 01001100010100010100110001010001 有多少个不同的非空子串？

运行限制

• 最大运行时间：1s
• 最大运行内存: 256M

---

🔥1.3分析题意🔥
    首先，题目已经告诉了我们需要求解的字符串是0100110001010001 ，我们第一个想到的办法可能是for循环暴力，用两个指针来遍历，把每一种情况存到数组里，然后再去重，但是这种方法未免太过麻烦，我们想到，STL库函数有set，就是个天然的去重容器，我们f两层or循环遍历这个字符串，然后存入set容器，再计算set的size就ok了。

🔥1.4C 代码示例🔥

#include <bits/stdc  .h>
using namespace std;
string str = "0100110001010001";
string s;
set<string> p; 
int main()
{
  int n = str.length();
  for(int i = 1; i <= n; i  )
    for(int j = 0; j <= n - i; j  )
    {
      s = str.substr(j, i);
      p.insert(s);
    }
  cout << p.size() << endl;
  return 0;
}

🍎2、特殊日期

🔥2.1题目链接🔥特殊日期

🔥2.2题目描述🔥
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

对于一个日期，我们可以计算出年份的各个数位上的数字之和，也可以分别计算月和日的各位数字之和。请问从 1900 年 1 月 1 日至 9999 年 12 月 31 日，总共有多少天，年份的数位数字之和等于月的数位数字之和加日的数位数字之和。

例如，2022 年 11 月 13 日满足要求，因为 2 0 2 2=(1 1) (1 3)

请提交满足条件的日期的总数量。
运行限制

• 最大运行时间：1s
• 最大运行内存: 256M

---

🔥2.3分析题意🔥
    很显然，遇到这种日期类的问题，我们通常需要判断这个年份是不是闰年，以及通过题目，我们可知我们需要写一个计算一个数字各个数字组成的和，如果直接for循环的起始从19000101开始循环到99991231时间复杂度稍微有点高，而且代码设计上可能没那么简单，我们可以从年份1900年作为起始点。再计算年份、月和日的数字和。

🔥2.4C 代码示例🔥

#include <bits/stdc  .h>
using namespace std;
int  a[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30 ,31}; //月份数组
int func(int n)//计算各个数字位的和
{
  int sum = 0;
  while(n)
  {
    sum  = n % 10;
    n /= 10;
  }
  return sum;
}
int main()
{
  int sum = 0;
  for(int y = 1900; y <= 9999; y  )
  {
    if(y % 4==0 && y % 100 != 0 || y % 400 == 0)//判断是不是闰年
    a[2] = 29;
    else a[2] = 28;
    for(int m = 1; m <= 12; m  )
    {
      for(int d = 1; d <= a[m]; d   )
      {
        if(func(y) == func(m)   func(d)) sum  ;
      }
    }
  }
  cout << sum << endl;
  return 0;
}

---

🍎3、左移右移

🔥3.1题目链接🔥左移右移

🔥3.2题目描述🔥

小蓝有一个长度为 N 的数组, 初始时从左到右依次是 1,2,3…N。
之后小蓝对这个数组进行了 M 次操作, 每次操作可能是以下 2 种之一:
左移 x, 即把 x 移动到最左边。
右移 x, 即把 x 移动到最右边。

请你回答经过 M 次操作之后, 数组从左到右每个数是多少?
输入格式
第一行包含 2 个整数, N 和 M 。
以下 M 行每行一个操作, 其中 “L x "表示左移 x, "Rx "表示右移 x 。
样例输入
5 3
L 3
L 2
R 1
样例输出
2 3 4 5 1

样例说明
样例中的数组变化如下:
[1,2,3,4,5]→[3,1,2,4,5]→[2,3,1,4,5]→[2,3,4,5,1]

评测用例规模与约定
对于 50% 的评测用例. 1≤N,M≤10000.
对于100% 的评测用例, 1≤N,M≤200000,1≤x≤N.
🔥3.3分析题意🔥
    首先我们先理解一下题意，每一次操作，左移或者右移，都是把数组的中的x移动到最左或者最右端，如果我们频繁执行这个操作，原数组的值会改变变得非常频繁，要么是每次生成一个新数组来存储操作后的数组，但这样的空间复杂度会很高，代码也会比较复杂，那么我们可以记录下每次操作对应位置的操作值的变化，用pair数组来实现，比如说设置左移操作初始值为-1右移操作初始值设为1e6，如果这个位置的值要左移，那么对应的操作值= -1 再–；如果是右移操作那么就把对应的操作值 =1e6 再 ，最后再按照操作值sort一下就可以了。

🔥3.4C 代码示例🔥

#include <bits/stdc  .h>
using namespace std;
#define x first
#define y second
typedef pair<int, int> PII; //Pair像是一个结构体而已
const int N = 2e5   10;
PII a[N];
int n, m;
bool cmp(const PII a,const  PII b)//设置sort的排序指标
{
  return a.y < b.y;
}
int main()
{
  cin >> n >> m;
  for(int i = 1; i <= n; i  )
  {
     a[i].x = i;
     a[i].y = i;
  }
  int cnt = -1, res = 1e6  1;
  while(m --)
  {
    char op[2];
    int h;
    scanf("%s %d", op, &h);
    if(op[0] == 'L')
    {
      a[h].y = cnt --;
    }
    else
    {
      a[h].y = res  ;
    }
  }
  sort(a   1, a   n   1, cmp);
  for(int i =  1; i <= n; i  )
  {
    printf("%d ", a[i].x);
  }
  return 0;
}

---

🍎4、卡牌

🔥4.1题目链接🔥卡牌

🔥4.2题目描述🔥

这天, 小明在整理他的卡牌。
他一共有 n 种卡牌, 第 ii 种卡牌上印有正整数数i(i∈[1,n]), 且第 i 种卡牌现有ai张。
而如果有 n 张卡牌, 其中每种卡牌各一张, 那么这 n 张卡牌可以被称为一 套牌。小明为了凑出尽可能多套牌, 拿出了 m 张空白牌, 他可以在上面写上数 i, 将其当做第 i 种牌来凑出套牌。然而小明觉得手写的牌不太美观, 决定第 i 种牌最多手写bi 张。

请问小明最多能凑出多少套牌?

输入格式
输入共 3 行, 第一行为两个正整数 n, m。
第二行为 n 个正整数, a1,a2,a3…an；
第三行为 n 个正整数 b1, b2, b3…bn;
输出格式
一行, 一个整数表示答案。
4 5
1 2 3 4
5 5 5 5

样例输出
3

样例说明：
这 5 张空白牌中, 拿 2 张写 1 , 拿 1 张写 2 , 这样每种牌的牌数就变为了 3,3,3,4可以凑出 3 套牌, 剩下 2 张空白牌不能再帮助小明凑出一套。

评测用例规模与约定。
对于 30% 的数据, 保证 n≤2000;
对于 100% 的数据, 保证 n<=2e5, ai, bi <= 2n,m <= n * n;

🔥4.3分析题意🔥
    首先我们看样例的大小，知道要用longlong来存m，按照题目的要求，我们要求最大的卡牌套数，可以用二分算法，来求最大的值。设置一个flag = 1。 flag == 1,说明目前的所有牌都满足mid套,那么此时将mid调大,让l更大
flag == 0,说明有牌不能够满足mid套,此时将mid调小,让r=mid-1
if(a[i] b[i] < mid || mid - a[i] > buf)//条件1说明凑不够这么多套牌 条件2说明手写牌大于m张,此时退出循环.

🔥4.4C 代码示例🔥

#include <iostream>
using namespace std;
int n;
typedef long long LL;
LL m;
const int N = 2e5   10;
int a[N], b[N];
int main()
{
  cin >> n >> m;
  for(int i = 0; i< n; i   )
  {
    int x;
    cin >> x;
    a[i] = x;
  }
  for(int i = 0; i < n; i  )
  {
    int x;
    cin >> x;
    b[i] = x;
  }
  int l = 0, r = 6 *n ;
  while(l < r)
  {
    int flag = 1, mid = l   r   1 >> 1;
    LL buf = m;//说明buf是空白牌的
    for(int i = 0; i < n; i  )
    {
      if(a[i] >= mid)continue; //说明这个类别可以凑齐mid套所需的数量
      if(a[i]   b[i] < mid || mid - a[i] > buf)//条件1说明凑不够这么多套牌 条件2说明手写牌大于m张,此时退出循环
      {
        flag = 0;
        break;
      }
      buf -= mid - a[i];
    }
    if(flag) l = mid; else r = mid - 1;
     //flag==1,说明目前的所有牌都满足mid套,那么此时将mid调大,让l更大
     //flag==0,说明有牌不能够满足mid套,此时将mid调小,让r=mid-1
  } 
  printf("%d", l);
  return 0;
}

---

🍎5、总结

    本文向大家介绍了四题蓝桥杯真题，涉及到二分，日期类计算，pair数组的使用，STL中set库函数的应用等，希望大家读后也能有所收获！

这篇好文章是转载于：学新通技术网