前言

大家好！我是 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;
}

題解分析

本題是一道二維前綴和模板題。

• 二維前綴和是基于容斥定理實現。