蓝桥杯刷题周计划（第三周）

前言

大家好！我是 EnigmaCoder。

• 本文是我蓝桥杯刷题计划的第三周。附：蓝桥杯刷题周计划（第二周)
• 本文含有10题，刷题内容涵盖暴力、日期、前缀和、差分等等，每道题分为题目、代码、题解分析三部分，且附有原题链接。
• 希望能帮助到大家！

题目一

原题链接：lanqiao3491

题目

问题描述
小蓝认为如果一个数含有偶数个数位，并且前面一半的数位之和等于后面一半的数位之和，则这个数是他的幸运数字。例如 2314 是一个幸运数字, 因为它有 4 个数位, 并且 2+3=1+4 。现在请你帮他计算从 1 至 100000000 之间共有多少个不同的幸运数字。

答案提交
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

代码

#include <iostream>
using namespace std;
const int N=20;
int a[N];
int main()
{
  int ans=0;
  for(int i=1;i<=100000000;i++){
    int e=0;int w=i;
      while(w>0){
        a[e++]=w%10;
        w/=10;
      }
      if(e%2!=0)continue;
      else{
      int l=0,r=e-1;
      int sum1=0,sum2=0;
      while(l<r){
        sum1+=a[l];
        sum2+=a[r];
        l++,r--;
      }
      if(sum1==sum2)ans++;
    }
 
  }
  cout<<ans;
  return 0;
}

题解分析

本题是一道填空题，直接暴力解题。

• 偶数个数位为重要条件，使用双指针进行分别相加，最后统计出答案。
• 注意：本题解为暴力解法，在蓝桥杯平台上会运行超时，所以要在本地编译器上运行。

题目二

原题链接：lanqiao19937

题目

问题描述

小蓝出生在一个艺术与运动并重的家庭中。

妈妈是位书法家，她希望小蓝能通过练习书法，继承她的艺术天赋，并练就一手好字。爸爸是一名篮球教练，他希望小蓝能通过篮球锻炼身体，培养运动的激情和团队合作的精神。

为了既满足妈妈的期望，又不辜负爸爸的心意，小蓝决定根据日期的笔画数来安排自己的练习。首先，他会将当天的日期按照 “YYYYMMDDYYYYMMDD” 的格式转换成一个 88 位数，然后将这 88 位数对应到汉字上，计算这些汉字的总笔画数。如果总笔画数超过 5050，他就去练习篮球；如果总笔画数不超过 5050，他就去练习书法。

例如，在 20242024 年 11 月 11 日这天，日期可表示为一个 88 位数字 2024010120240101，其转换为汉字是“二零二四零一零一”。日期的总笔画数为 2+13+2+5+13+1+13+1=502+13+2+5+13+1+13+1=50，因此在这天，小蓝会去练习书法。

现在，请你帮助小蓝统计一下，在 2000 年 1 月 1 日到2024 年 4月13 日这段时间内，小蓝有多少天是在练习篮球？

答案提交
这是一道结果填空题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

代码

#include <bits/stdc++.h>
using namespace std;
int month[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int hz[10]={13,1,2,3,5,4,4,2,2,2};
bool isleap(int y){
  return (y%400==0)||(y%4==0&&y%100!=0);
}
int main()
{
  int ans=0;
  for(int y=2000;y<=2024;y++){
    if(isleap(y))month[2]=29;
    else month[2]=28;
    for(int m=1;m<=12;m++){
      for(int d=1;d<=month[m];d++){
        int sum=0;
       if(y==2024&&m==4&&d==14){
            cout<<ans;
            return 0;
          }
          int sum1=y,sum2=m,sum3=d;
          for(int i=0;i<4;i++){sum+=hz[sum1%10];sum1/=10;}
          for(int i=0;i<2;i++){sum+=hz[sum2%10];sum2/=10;}
          for(int i=0;i<2;i++){sum+=hz[sum3%10];sum3/=10;}
          if(sum>50)ans++;
          
        }
    }
  }
  return 0;
}

题解分析

本题是一道日期相关的题，使用枚举即可解题。

• 日期遍历：通过三重循环遍历从2000年1月1日到2024年12月31日的每一天。
• 闰年处理：使用 isleap 函数判断是否为闰年，并根据结果调整2月的天数（28或29）。
• 权重计算：对每个日期的年、月、日进行数字拆分，并根据预定义的数组 hz进行权重累加。
• 条件判断：如果权重总和超过50，则计数加一。
• 结果输出：在2024年4月14日输出结果并结束运行。

题目三

原题链接：lanqiao3238

题目

问题描述
小蓝和小桥是游戏世界里的两个好友，他们正在玩一个有趣的挑战。他们手中有一个长度为
n 的神秘物品序列，每个物品都有一个数字 a i表示它的价值。他们可以执行以下操作：选择一个物品，并将其价值加 1。
小蓝和小桥希望通过若干次操作使得这个序列的价值之和与价值的积都不为 0。

请你帮他们计算，至少需要执行多少次操作才能完成这个挑战。

输入格式
第一行包含一个整数 t（1≤t≤100），表示测试用例的数量。

接下来 t 行，每行包含两行数据，第一行为一个整数 （1≤n≤1000），表示物品的数量。第二行为 n 个整数 a1,a2…,an（−1000≤a i ≤1000），表示初始的物品价值。

输出格式
对于每个测试用例，输出一行一个整数，表示至少需要执行的操作次数。

样例输入
2
2
0 0
3
-1 0 1

样例输出
2
1

代码

#include <iostream>
using namespace std;
const int N=2010;
int a[N];
int main()
{
  int t;cin>>t;
  while(t--){
    int ans=0,sum=0;
    int n;cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++){
      if(a[i]==0){
        ans++;
        a[i]=1;
      }
    }
    for(int i=1;i<=n;i++){
      sum+=a[i];
    }
    if(sum==0)ans++;
    cout<<ans<<endl;
  }
  return 0;
}

题解分析

本题是一道思维题。

• 我们先思考积为0的情况,也就是说所有为0的数都加1,最后算出和是否为0,为0就再加1

题目四

原题链接：lanqiao3904

题目

问题描述
在生物学中，DNA 序列的相似性常被用来研究物种间的亲缘关系。现在我们有两条 DNA 序列，每条序列由 A、C、G、T 四种字符组成，长度相同。但是现在我们记录的 DNA 序列存在错误，为了严格满足 DNA 序列的碱基互补配对即 A - T 和 C - G，我们需要依据第一条 DNA 序列对第二条 DNA 序列进行以下操作：

• 选择第二条 DNA 序列的任意两个位置，交换他们的字符。

• 选择第二条 DNA 序列任意一个位置，将其字符替换为 A、C、G、T 中的任何一个。

需要注意的是：每个位置上的碱基只能被操作一次！

你的任务是通过最小的操作次数，使第二条 DNA 序列和第一条 DNA 序列互补。并且已知初始两条 DNA 序列长度均为 N。

输入格式
第一行包含一个整数 N，(1≤N≤10 3 )，表示 DNA 序列的长度。

接下来的两行，每行包含一个长度为 N 的字符串，表示两条 DNA 序列。

输出格式
输出一个整数，表示让第二条 DNA 序列和第一条 DNA 序列互补所需的最小操作次数。

样例输入
5
ACGTG
ACGTC

样例输出
2
样例说明
将第二条 DNA 序列中的第一个和第四个碱基交换，将第二个和第三个碱基交换即可完成全部配对，共操作两次。

代码

#include <bits/stdc++.h>
using namespace std;
int main()
{
  int n;cin>>n;
  string s1,s2;cin>>s1>>s2;
  map<pair<char,char>,int>mp;
  for(int i=0;i<n;i++){
    mp[{s1[i],s2[i]}]++;
  }
  int ans=max(mp[{'A','A'}],mp[{'T','T'}])+
          max(mp[{'A','G'}],mp[{'C','T'}])+
          max(mp[{'A','C'}],mp[{'G','T'}])+
          max(mp[{'C','C'}],mp[{'G','G'}])+
          max(mp[{'G','A'}],mp[{'T','C'}])+
          max(mp[{'C','A'}],mp[{'T','G'}]);
  cout<<ans;
  return 0;
}

题解分析

本题使用了map容器来解题。

• 第一种操作明显比第二种操作更优，所以优先进行第一种操作。通过罗列出可以进行第一种操作的所有情况并取最大值相加，来得到最优解。
• 使用max是因为如果两者不相等，选择最大值相当于剩下的差值使用第二种操作补齐。

题目五

原题链接：lanqiao3260

题目

问题描述
小明是一名勇敢的冒险家，他在一次探险途中发现了一组神秘的宝石，这些宝石的价值都不同。但是，他发现这些宝石会随着时间的推移逐渐失去价值，因此他必须在规定的次数内对它们进行处理。

小明想要最大化这些宝石的总价值。他有两种处理方式：

选出两个最小的宝石，并将它们从宝石组中删除。
选出最大的宝石，并将其从宝石组中删除。

现在，给你小明手上的宝石组，请你告诉他在规定的次数内，最大化宝石的总价值是多少。

输入格式
第一行包含一个整数 t，表示数据组数。

对于每组数据，第一行包含两个整数 n 和 k，表示宝石的数量
6
5 1
2 5 1 10 6
5 2
2 5 1 10 6
3 1
1 2 3
6 1
15 22 12 10 13 11
6 2
15 22 12 10 13 11
5 1
999999996 999999999 999999997 999999998 999999995

样例输出
21
11
3
62
46
3999999986

样例说明
在第一个测试用例中，两个最小值是 1 和 2，去掉它们，数组为 [5，10，6]，和为 21。而最大值为 10，去掉它，则数组为 [2,5,1,6]，和为 14。最优的操作为执行一次操作一，得到最好的答案为 21。

在第二个测试用例中，最优的处理结果先删除两个最小值，然后再删除一个最大值。

评测数据规模
对于 100% 的评测数据，1≤t≤10,3≤n≤2⋅10⁵,1≤k≤99999,2k<n。

代码

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
int main()
{
  int t;cin>>t;
  while(t--){
    int n,k;cin>>n>>k;
    ll a[n+5],prefix[n+5];
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a+1,a+n+1);

    for(int i=1;i<=n;i++)prefix[i]=prefix[i-1]+a[i];

    ll ans=0;
    int pos=0;
    while(k>=0){
      ans=max(ans,prefix[n-k]-prefix[pos]);
      pos+=2;
      k--;
    }
    cout<<ans<<endl;
  }
  return 0;
}

题解分析

本题使用贪心和前缀和解题。

• 输入处理：读取多个测试用例，每个测试用例包含一个数组和两个整数n和k。
• 排序：将数组排序，以便后续选择最大的k个数。
• 前缀和计算：计算数组的前缀和，方便快速计算子数组的和。
• 贪心选择：通过贪心策略，选择最大的k个数，并尝试排除前面的数，找到最大子数组和。
• 输出结果：对每个测试用例输出最大子数组和。

题目六

原题链接：lanqiao3693

题目

问题描述
小羊肖恩最近喜欢上了投球游戏，具体来说，在他面前摆放了 n 个球筐，第 i 个框最开始有 a i个球。接下来小羊会进行
q 次操作，每次操作会给出三个整数 l,r,c，会将第 l 个框到第 r 个框，都投入 c 个球。请你输出操作完成之后每个框各有多少个球？

输入格式
第一行输入两个整数 n 和 q，表示球筐个数和操作次数。

第二行输入 n 个整数，表示每个球筐最开始的球数。

接下来 q 行，每次输入三个整数 l,r,c。

数据范围保证：
1≤n,q≤10⁵，1≤l≤r≤n，1≤ai,c≤10⁵ 。

输出格式
输出一行 n 个整数，表示每个框最终的球的个数，以空格分开。

样例输入
5 3
7 5 7 7 3
1 5 3
1 5 2
4 4 4
样例输出
12 10 12 16 8

代码

#include <bits/stdc++.h>
using namespace std;
const int N=100010;
int a[N],diff[N];

int main()
{
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int n,q;cin>>n>>q;
 for(int i=1;i<=n;i++)cin>>a[i];
 for(int i=1;i<=n;i++)diff[i]=a[i]-a[i-1];
 while(q--){
   int l,r,c;cin>>l>>r>>c;
   diff[l]+=c;
   diff[r+1]-=c;
 }
 for(int i=1;i<=n;i++)a[i]=a[i-1]+diff[i];
 for(int i=1;i<=n;i++)cout<<a[i]<<' ';
  return 0;
}

题解分析

本题使用差分数组进行区间修改即可。

题目七

原题链接：lanqiao18437

题目

问题描述
本题为一维前缀和模板。

给定一个长度为 n 的序列 a。

再给定 q 组查询，对于每次查询：

给定一对 l,r你需要输出 ∑i=lai 的结果。

输入格式
第一行输入两个正整数 n,q。（1≤n,q≤10⁵）第二行输入 n个正整数 ai。（1≤i≤n,1≤ai≤10⁴ ）。

接下来 q 行，每行输入 2 个正整数 l,r。（1≤≤r≤n）。

输出格式
对于每次查询，输出一行一个整数，表示该次查询的结果。

样例输入
5 3
2 1 3 6 4
1 2
1 3
2 4
样例输出
3
6
10

代码

#include <bits/stdc++.h>
using namespace std;
const int N=100100;
int a[N],prefix[N];
int main()
{
  int n,q;cin>>n>>q;
  for(int i=1;i<=n;i++){
    cin>>a[i];
    prefix[i]=prefix[i-1]+a[i];
  }
  while(q--){
    int l,r;cin>>l>>r;
    int sum=prefix[r]-prefix[l-1];
    cout<<sum<<endl;
  }
  return 0;
}

题解分析

本题使用前缀和模板解题即可。

题目八

原题链接：lanqiao18438

题目

问题描述
给定一个长度为 n 的序列 a。

再给定 m 组操作，每次操作给定 3 个正整数 l,r,d，表示对 a l∼r中的所有数增加 d。

最终输出操作结束后的序列 a。

输入格式
第一行输入两个正整数 n,m。（1≤n,m≤2×10⁵ ）

第二行输入 n 个正整数 a i。（1≤i≤n1≤ai≤141≤i≤n,1≤a i ≤10 4 ）。

接下来 m 行，每行输入 3 个正整数 l,r,d。（1≤l≤r≤n,−10 ⁴ ≤d≤10 ⁴）。

输出格式
输出 n 个整数，表示操作结束后的序列 a。

样例输入
6 3
1 2 2 1 2 1
1 3 1
3 5 1
1 6 1

样例输出
3 4 5 3 4 2

代码

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int a[N],diff[N];
int main()
{
  int n,m;cin>>n>>m;
  for(int i=1;i<=n;i++){
    cin>>a[i];
    diff[i]=a[i]-a[i-1];
  }
  while(m--){
    int l,r,d;cin>>l>>r>>d;
    diff[l]+=d;
    diff[r+1]-=d;
  }
  for(int i=1;i<=n;i++){
    a[i]=a[i-1]+diff[i];
    cout<<a[i]<<' ';
  }
  return 0;
}

题解分析

本题使用差分模板解题。

• 注意：差分数组修改后用进行前缀和，才算修改原来数组。

题目九

原题链接：lanqiao3250

题目

问题描述
给定 n 副卡牌，每张卡牌具有正反面，正面朝上数字为 a背面朝上数字为 bi。一副卡牌的价值为正面朝上数字之和。一开始所有卡牌都是正面朝上的。小蓝是蓝桥学院最优秀的魔法师，他知道所有卡牌的背面数字 bi，他最多可以进行 k次操作，每次可以将一副卡牌翻转，将正面朝上的数字变为背面朝上的数字，或将背面朝上的数字变为正面朝上的数字。请问，小蓝最多可以使卡牌的价值之和为多少？

输入格式
第一行输入两个整数 n 和 k ，表示卡牌的数量和小蓝可以操作的次数。

第二行输入 n 个整数 a i，表示所有卡牌正面的数字。

第三行输入 n 个整数 b i，表示所有卡牌反面的数字。

数据范围保证：
1≤n≤1×10⁵ ，1≤i,bi,k≤10⁹。

输出格式
输出一个整数，表示可以得到的卡牌的最大价值和。

样例输入
3 1
1 2 3
3 2 1

样例输出
8

说明
将第一张卡牌翻转，此时卡牌的总和为 3+2+3=8

代码

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e5+10;
ll a[N],b[N];
int main()
{
 ll n,k;cin>>n>>k;
  ll sum=0;
  for(int i=1;i<=n;i++){cin>>a[i];sum+=a[i];};
  for(int i=1;i<=n;i++){cin>>b[i];b[i]-=a[i];};
  sort(b+1,b+1+n,greater<ll>());
  for(int i=1;i<=n;i++){
    if(b[i]<=0||k==0)break;
    else{
      sum+=b[i];
      k--;
    }
  }
  cout<<sum;
  return 0;
}

题解分析

本题使用贪心解题。

• 先不翻牌，求所有正面牌数的总和。再算出背面的数减正面的数的差值，如果差值小于等于0，说明不翻牌价值最大，否则就加上差值。
• 注意，判断条件为b[i]<=0||k==0，k为可操作次数。

题目十

原题链接：lanqiao18439

题目

问题描述
给定一个 n×m 大小的矩阵 A。

给定 q 组查询，每次查询为给定 4 个正整数 x 1 ,y 1 ,x 2 ,y 2 ，你需要输出 ∑ i=x 1x 2 ∑ j=y y 2 A i, 的值。

输入格式
第一行输入 3 个正整数 n,m,q。（1≤n,m≤10 ³ ,1≤q≤10 ⁵ ）

接下来 n 行每行输入 m 个整数，表示 A i,j 。(−10 3 ≤A i,j≤10 3 ,1≤i≤n,1≤j≤m)

接下来 q 行，每行输入 4 个正整数 x 1,y ,x 2 ,y 2 。(1≤x 1 ≤x 2 ≤n,1≤y ≤y 2≤m)

输出格式
对于每次查询，输出一个整数，表示查询的子矩阵的和。

样例输入
3 4 3
1 7 2 4
3 6 2 8
2 1 2 3
1 1 2 2
2 1 3 4
1 3 3 4

样例输出
17
27
21

代码

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e3+10;
ll a[N][N], prefix[N][N];

int main() {
  ll n, m, q;cin >> n >> m >> q;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      cin >> a[i][j];
      }
  }

  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      prefix[i][j] = prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1] + a[i][j];
    }
  }
  while (q--) {
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    ll sum = prefix[x2][y2] - prefix[x2][y1 - 1] - prefix[x1 - 1][y2] + prefix[x1 - 1][y1 - 1];
    cout << sum << endl;
  }

    return 0;
}

题解分析

本题是一道二维前缀和模板题。

• 二维前缀和是基于容斥定理实现。