C++第14屆藍橋杯b組學習筆記

1. 日期統計

小藍現在有一個長度為?100100?的數組，數組中的每個元素的值都在?00?到?99?的范圍之內。數組中的元素從左至右如下所示：

5 6 8 6 9 1 6 1 2 4 9 1 9 8 2 3 6 4 7 7 5 9 5 0 3 8 7 5 8 1 5 8 6 1 8 3 0 3 7 9 2
7 0 5 8 8 5 7 0 9 9 1 9 4 4 6 8 6 3 3 8 5 1 6 3 4 6 7 0 7 8 2 7 6 8 9 5 6 5 6 1 4 0 1
0 0 9 4 8 0 9 1 2 8 5 0 2 5 3 3

現在他想要從這個數組中尋找一些滿足以下條件的子序列：

子序列的長度為?88；
這個子序列可以按照下標順序組成一個?yyyymmddyyyymmdd?格式的日期，并且要求這個日期是?20232023?年中的某一天的日期，例如?2023090220230902，2023122320231223。yyyyyyyy?表示年份，mmmm?表示月份，dddd?表示天數，當月份或者天數的長度只有一位時需要一個前導零補充。

請你幫小藍計算下按上述條件一共能找到多少個不同的?20232023?年的日期。對于相同的日期你只需要統計一次即可。

#include <iostream>
using namespace std;
bool st[100000000];
int math[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int main()
{// 請在此輸入您的代碼int a[101]={5 ,6, 8, 6, 9, 1, 6, 1, 2, 4, 9, 1, 9, 8, 2, 3, 6, 4, 7, 7, 5, 9, 5, 0, 3, 8, 7, 5, 8, 1, 5, 8, 6, 1, 8, 3, 0, 3, 7, 9, 2,
7, 0, 5, 8, 8, 5, 7, 0, 9, 9, 1, 9, 4, 4, 6, 8, 6, 3, 3, 8, 5, 1, 6, 3, 4, 6, 7, 0, 7, 8, 2, 7 ,6, 8, 9, 5, 6, 5, 6, 1, 4, 0, 1,
0, 0, 9, 4, 8, 0, 9, 1, 2, 8, 5, 0, 2, 5, 3, 3};int len=8;int cnt=0;for(int i=0;i<100;i++){if(a[i]==2)for(int i2=i+1;i2<100;i2++){if(a[i2]==0)for(int i3=i2+1;i3<100;i3++){if(a[i3]==2)for(int i4=i3+1;i4<100;i4++){if(a[i4]==3){len=4;//年數完了for(int m1=i4+1;m1<100;m1++){if(a[m1]==1||a[m1]==0)//10位只能是1或0{for(int m2=m1+1;m2<100;m2++){if(a[m1]==1&&a[m2]<=2||a[m1]==0)//當m1是1 m2要小于等于1，反之都可以{for(int d1=m2+1;d1<100;d1++){int mymon=a[m1]*10+a[m2];//月if(math[mymon]/10>=a[d1])for(int d2=d1+1;d2<100;d2++){int day=a[d1]*10+a[d2];//日// cout<<mymon<<"  "<<day<<endl;if(day<=math[mymon]&&day!=0){int tmp=a[i]*1e7+a[i2]*1e6+a[i3]*1e5+a[i4]*1e4+a[m1]*1e3+a[m2]*100+a[d1]*10+a[d2];if(!st[tmp])//沒走過cnt++;// cout<<tmp<<endl;st[tmp]=true;// cout<<cnt<<"  cnt:"<<endl;}}}}}}}}}}}}printf("%d",cnt);return 0;
}

2. 冶煉金屬

小藍有一個神奇的爐子用于將普通金屬?O?冶煉成為一種特殊金屬?X。這個爐子有一個稱作轉換率的屬性?V，V?是一個正整數，這意味著消耗?V?個普通金屬?O?恰好可以冶煉出一個特殊金屬?X，當普通金屬?O?的數目不足?V?時，無法繼續冶煉。

現在給出了?N?條冶煉記錄，每條記錄中包含兩個整數?A?和?B，這表示本次投入了?A?個普通金屬 O，最終冶煉出了?B?個特殊金屬?X。每條記錄都是獨立的，這意味著上一次沒消耗完的普通金屬?O?不會累加到下一次的冶煉當中。

根據這?N?條冶煉記錄，請你推測出轉換率?V?的最小值和最大值分別可能是多少，題目保證評測數據不存在無解的情況。

解題思路

check函數來計算能完成構造b個的最大轉換率，然后求構造b+1個特殊金屬的最大轉換+1即b的最小轉換率

AC代碼

#include <iostream>
#include<cstdio>
#include<algorithm>
using namespace std;int n;//求最大
int check(int l, int r, int sum, int x)//求最大 r  sum是總共的金屬 x是特殊的金屬
{int mid = 0;// r=1e9;while (l < r){mid = ((l + r ) >> 1)+1;if (sum / mid >= x)//mid可以完成任務或者超額完成l = mid;elser = mid - 1;}return l;
}
int main()
{// 請在此輸入您的代碼scanf("%d", &n);int maxin = 0x3f3f3f3f;//最大值的最小值int minax = 0;//最小值的最大值// cout<<check(0,9248,9248,1)<<endl;// cout<<"test:  "<<check(0,75,75,3)<<endl;for (int i = 0; i < n; i++){int a, b;//a個普通金屬，冶煉出b個特殊金屬cin >> a >> b;//求最小值的最大值minax = max(minax, check(0, a, a, b + 1) + 1);//求造b+1個特殊金屬的最大轉換率+1就是最小轉換率//求最小值的最大值maxin = min(maxin, check(0, a, a, b));// cout<<maxin<<" "<<endl;}cout << minax << ' ' << maxin << endl;return 0;
}

3. 飛機降落

N?架飛機準備降落到某個只有一條跑道的機場。其中第?i?架飛機在?Ti??時刻到達機場上空，到達時它的剩余油料還可以繼續盤旋?Di??個單位時間，即它最早可以于?Ti??時刻開始降落，最晚可以于?Ti+Di時刻開始降落。降落過程需要?Li個單位時間。

一架飛機降落完畢時，另一架飛機可以立即在同一時刻開始降落，但是不能在前一架飛機完成降落前開始降落。

請你判斷?N?架飛機是否可以全部安全降落。

解題思路

一個結構體存儲，到達時間，可以盤旋時間，降落需要時間。dfs判斷是否可以全部降落。狀態數組st記得重置

AC代碼

#include <iostream>
#include<algorithm>
#include<cstring>
using namespace std;int n;
// pair<int,int> td[11];
struct til
{int t;//到達時間int d;//可以盤旋的時間int l;//降落所需時間bool operator <(struct til& tmp){if(t<tmp.t)return true;else if(t==tmp.t){if(d<tmp.d)return true;else if(d==tmp.d)return l<tmp.l;}return false;}
}til[15];bool st[15];//檢測第i架飛機是否降落bool dfs(int cnt,int tim)//cur第幾架飛機
{if(cnt==n)return true;for(int i=0;i<n;i++)//枚舉所有飛機{if(!st[i])//飛機沒走{if(tim>til[i].t+til[i].d)//這架飛機還沒走并且超時了return false;int tmp=tim;//當前時間if(tmp<til[i].t)//下一個飛機降落的時間大于當前時間tmp=til[i].t;st[i]=true;if(dfs(cnt+1,tmp+til[i].l))//當前時間加降落所需時間，與下個飛機來到時間下落的時間return true;st[i]=false;//返回}}return false;
}// int l[11];
int main()
{// 請在此輸入您的代碼int t;scanf("%d",&t);while(t--){memset(st,false,sizeof st);scanf("%d",&n);for(int i=0;i<n;i++){scanf("%d%d%d",&til[i].t,&til[i].d,&til[i].l);}sort(til,til+n);if(dfs(0,0))cout<<"YES"<<endl;elsecout<<"NO"<<endl;}return 0;
}

4. 接龍數列

對于一個長度為?KK?的整數數列：A1,A2,…,AK，我們稱之為接龍數列當且僅當?Ai??的首位數字恰好等于?Ai?1Ai?1??的末位數字?(2≤i≤K)(2≤i≤K)。例如 12,23,35,56,61,11?是接龍數列；12,23,34,56不是接龍數列，因為?56?的首位數字不等于?34?的末位數字。所有長度為?1?的整數數列都是接龍數列。

現在給定一個長度為?N?的數列?A1,A2,…,AN，請你計算最少從中刪除多少個數，可以使剩下的序列是接龍序列？

解題思路

線性DP，最長公共子序列一樣的模型。以第i個數字為結尾的接龍子序列的集合

?暴力過一半測試用例

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<string>
using namespace std;
int f[10010];int a[10010];
int b[10010];int main()
{   int n;scanf("%d",&n);for(int i=0;i<n;i++){string s;cin>>s;a[i]=s[0]-'0';b[i]=s[s.size()-1]-'0';}for(int i=0;i<n;i++){f[i]=1;for(int j=0;j<i;j++){if(a[i]==b[j]){f[i]=max(f[i],f[j]+1);}}}int res=0;for(int i=0;i<n;i++){// cout<<f[i]<<"  ";if(f[i]>res)res=f[i];}cout<<n-res;return 0;
}

5. 島嶼個數

小藍得到了一副大小為 M×N?的格子地圖，可以將其視作一個只包含字符 '0'（代表海水）和 '1'（代表陸地）的二維數組，地圖之外可以視作全部是海水，每個島嶼由在上/下/左/右四個方向上相鄰的 '1' 相連接而形成。

在島嶼?AA?所占據的格子中，如果可以從中選出?k?個不同的格子，使得他們的坐標能夠組成一個這樣的排列：(x0,y0),(x1,y1),…,(xk?1,yk?1)，其中 (xi+1modk?,yi+1modk?)?是由(xi?,yi?)?通過上/下/左/右移動一次得來的?(0≤i≤k?1)(0≤i≤k?1)，此時這?k?個格子就構成了一個“環”。如果另一個島嶼 B?所占據的格子全部位于這個“環”內部，此時我們將島嶼?B?視作是島嶼?A?的子島嶼。若B?是?A?的子島嶼，C?又是?B?的子島嶼，那?C?也是?A?的子島嶼。

請問這個地圖上共有多少個島嶼？在進行統計時不需要統計子島嶼的數目。

解題思路

正難則反，我們仔細想一下怎么才能知道一個島是子島嶼呢，就是這個島所臨的海只要有外海就說明這個島能聯通外界不是子島嶼，而只聯通內海呢，就說明它被一個島嶼所包含了。至于判斷是外海還是內海，只要遍歷邊界的海(因為地圖外的海一定是外海，與邊界的海相連的海就是外海，不聯通的就是內海)。遍歷所有的沒走過的陸地，臨著外海就是一個獨立的島嶼

AC代碼

#include <iostream>
#include<queue>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;char map[55][55];
int n, m;int dxx[8] = { 0,0,1,-1,1,1,-1,-1 };//看海是否是內陸海
int dyy[8] = { 1,-1,0,0,1,-1,1,-1 };int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
bool sth[55][55];//標記海洋是否流到
bool stl[55][55];//標記所有陸地
void bfs1(int x, int y)
{queue<pair<int, int>> q;q.push({ x,y });sth[x][y] = true;//while (!q.empty()){int x1 = q.front().first;int y1 = q.front().second;q.pop();for (int i = 0; i < 8; i++){int x2 = dxx[i] + x1;int y2 = dyy[i] + y1;if (x2 >= n || x2 < 0 || y2 < 0 || y2 >= m)//越界continue;if (sth[x2][y2] || map[x2][y2] != '0')//走過了或不是海洋continue;sth[x2][y2] = true;q.push({ x2,y2 });}}
}bool bfs(int x, int y)
{queue<pair<int, int>> q;q.push({ x,y });stl[x][y] = true;//int f = false;//標記是否通往外海while (!q.empty()){int x1 = q.front().first;int y1 = q.front().second;q.pop();for (int i = 0; i < 4; i++){int x2 = dx[i] + x1;int y2 = dy[i] + y1;if (x2 >= n || x2 < 0 || y2 < 0 || y2 >= m)//越界continue;//四周的海只要有外海if (map[x2][y2] == '0' && sth[x2][y2])//是海并且這個海通往外海f = true;if (stl[x2][y2] || map[x2][y2] != '1')//走過了或不是陸地continue;stl[x2][y2] = true;q.push({ x2,y2 });}}return f;//說明是否通往外海，不連接外海的一定是環內的
}int main()
{// 請在此輸入您的代碼int t;scanf("%d", &t);while (t--){scanf("%d %d", &n, &m);memset(sth, false, sizeof sth);memset(stl, false, sizeof stl);//memset(map, '0', sizeof map);//cout << n << m << endl;for (int i = 0; i < n; i++){cin >> map[i];}bool f = true;for (int i = 0; i < n; i++){if (!sth[i][0] && map[i][0] == '0')//沒走過并且是海洋{bfs1(i, 0);f = false;//表示地圖周圍有海}if (!sth[i][m - 1] && map[i][m - 1] == '0')bfs1(i, m - 1), f = false;}for (int j = 0; j < m; j++){if (!sth[0][j] && map[0][j] == '0')bfs1(0, j), f = false;if (!sth[n - 1][j] && map[n - 1][j] == '0')bfs1(n - 1, j), f = false;}//max(0,n-1)if (f)//四周全是陸地就輸出1即可cout << 1 << endl;else{int cnt = 0;for (int i = 0; i < n; i++){for (int j = 0; j < m; j++){if (!stl[i][j] && map[i][j] == '1')//沒走過并且是陸地if (bfs(i, j))cnt++;}}cout << cnt << endl;}//將所有最外層的海進行bfs，八個方向能流到的地方，肯定就不是內海}return 0;
}

6. 子串簡寫

程序猿圈子里正在流行一種很新的簡寫方法：對于一個字符串，只保留首尾字符，將首尾字符之間的所有字符用這部分的長度代替。例如 internation-alization 簡寫成 i18n，Kubernetes （注意連字符不是字符串的一部分）簡寫成 K8s, Lanqiao 簡寫成 L5o 等。

在本題中，我們規定長度大于等于?KK?的字符串都可以采用這種簡寫方法（長度小于?K?的字符串不配使用這種簡寫）。

給定一個字符串?S?和兩個字符?c1??和?c2??，請你計算?S?有多少個以?c1??開頭?c2??結尾的子串可以采用這種簡寫？

解題思路

這題可以運用雙指針來遍歷區間，但是這樣還不夠，還可以用前綴和的思想來優化，我們來從后往前維護一段長度為k的區間來預處理b的數量，遇到b就統計下來b的數量，遇到a就統一結算之前b的數量。

AC代碼

注釋掉的為暴力代碼

#include <iostream>
#include<string>
#include<cstdio>
using namespace std;// pair<char,char> fe[500010];
int k;
string s;
char c1,c2;
int main()
{// 請在此輸入您的代碼scanf("%d",&k);cin>>s>>c1>>c2;long long cnt=0;long long res=0;//前綴和思想for(int r=s.size()-1,l=s.size()-k;l>=0;r--,l--){if(s[r]==c2) cnt++;//統計可以當結尾的數量if(s[l]==c1) res+=cnt;//遇到一個可以當頭的，加上所有可以當結尾的，字符數量}// for(int l=0;l+k-1<s.size();l++)// {//   if(s[l]==c1)//以c1開頭//   {//       int r=l+k-1;//       while(r<s.size())//       {//         if(s[r]==c2)//         cnt++;//         r++;//       }//   }// }cout<<res<<endl;return 0;
}

7. 景區導游

某景區一共有?N?個景點，編號?1?到?N。景點之間共有?N?1?條雙向的擺渡車線路相連，形成一棵樹狀結構。在景點之間往返只能通過這些擺渡車進行，需要花費一定的時間。

小明是這個景區的資深導游，他每天都要按固定順序帶客人游覽其中?K?個景點：A1?,A2?,…,AK?。今天由于時間原因，小明決定跳過其中一個景點，只帶游客按順序游覽其中?K?1?個景點。具體來說，如果小明選擇跳過?Ai?，那么他會按順序帶游客游覽 A1?,A2?,…,Ai?1?,Ai+1?,…,AK?，(1≤i≤K)。

請你對任意一個?Ai?，計算如果跳過這個景點，小明需要花費多少時間在景點之間的擺渡車上？

暴力思路

構建鄰接表，通過dfs計算出所需游覽所有景點的總長度。

再依次枚舉要游覽的景點，將其刪除，此時有三種情況

1. 刪除的景點是a[0],即第一次去的景點，此時第一次就不去a[0]了，直接去a[1]所以直接減去a[0]到a[1]的距離即可

2. 刪除的景點是a[k-1],即最后一次要去的景點，此時a[k-2]就是終點，減去a[k-2]到a[k-1]的距離即可

3. 減去的景點不是第一個與最后一個，那就減去當前景點去上一個景點的距離，與去下一個景點的距離

?暴力過一半數據

#include <iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<vector>
using namespace std;vector<pair<int,int>> edge[100010];
map<pair<int,int >,long long> len;//記錄a到b需要走多少 
int n,k;
int a[100010];//其實位置，當前位置，上個位置，終點，走的距離
bool dfs(int st,int u,int father,int end,int sum)
{if(u==end){len[{st,end}]=sum;len[{end,st}]=sum;//兩個都記錄一下return true;}for(auto c:edge[u]){if(c.first!=father)//下一個位置不是自己的父親節點{if(dfs(st,c.first,u,end,sum+c.second)){return true;}}}return false;
}
int main()
{// 請在此輸入您的代碼scanf("%d%d",&n,&k);for(int i=0;i<n-1;i++){int u,v,t;scanf("%d%d%d",&u,&v,&t);edge[u].push_back({v,t});edge[v].push_back({u,t});  }for(int i=0;i<k;i++){scanf("%d",&a[i]);}long long res=0;//記錄路徑總長度for(int i=0;i<k-1;i++){dfs(a[i],a[i],-1,a[i+1],0);//計算a[i]到a[i+1]所需的長度res+=len[{a[i],a[i+1]}];//}for(int i=0;i<k;i++){long long tmp=res;if(i==0)//如果是跳過第一個景點{tmp-=len[{a[i],a[i+1]}];//就是直接從第二個景點開始}else if(i==k-1)//跳過最后一個景點{tmp-=len[{a[i-1],a[i]}];//刪除倒數第二個景點去第二個景點的距離}else//計算刪除景點的上一個景點去下一個景點的距離{tmp=tmp-len[{a[i],a[i+1]}]-len[{a[i-1],a[i]}];//dfs(a[i-1],a[i-1],-1,a[i+1],0);tmp+=len[{a[i-1],a[i+1]}];}cout<<tmp<<" ";}return 0;
}

?8.砍樹

給定一棵由?n?個結點組成的樹以及?m?個不重復的無序數對 (a1,b1),(a2,b2),...,(am,bm)，其中?ai?互不相同，bi?互不相同，ai≠bj(1≤i,j≤m)。

小明想知道是否能夠選擇一條樹上的邊砍斷，使得對于每個(ai,bi)?滿足?ai?和?bi?不連通，如果可以則輸出應該斷掉的邊的編號（編號按輸入順序從?1開始），否則輸出??1。

暴力思路

記錄下來所有的邊與所有不能聯通的邊，雙重枚舉，使其不能聯通即可

暴力過30%數據代碼

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
using namespace std;int n,m;
vector<int> edge[100010];
pair<int,int> p[100010];//記錄所有的邊
pair<int,int> no[100010];//記錄所有不能聯通的邊
//st起始位置，end結束位置,u當前位置
bool dfs(int st,int end,int u,int father,int a,int b)//a和b表示被砍斷的邊
{// cout<<"當前在"<<u<<endl;if(u==end){return true;}for(auto c:edge[u]){if(c!=father)//a b不連通{if((u==a&&c==b)||(u==b&&c==a))//a與b不能互相聯通continue;// cout<<"可以往"<<c<<"走"<<endl;if(dfs(st,end,c,u,a,b))return true;}}return false;}int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=n-1;i++){int a,b;scanf("%d%d",&a,&b);edge[a].push_back(b);edge[b].push_back(a);p[i]={a,b};}for(int i=0;i<m;i++){int a,b;scanf("%d%d",&a,&b);no[i]={a,b};}bool f=true;// cout<< dfs(3,6,3,-1,6,5);for(int i=n-1;i>=1;i--){f=true;for(int j=0;j<m;j++){// cout<<"j=="<<j<<"  "<<dfs(no[j].first,no[j].second,no[j].first,-1,p[i].first,p[i].second)<<endl;if(dfs(no[j].first,no[j].second,no[j].first,-1,p[i].first,p[i].second)){f=false;//說明斷這條邊不可以使其不聯通// cout<<"斷的邊"<<p[i].first<<" "<<p[i].second<<endl;// cout<<"可以聯通的邊"<<no[j].first<<no[j].second<<endl;break;}}if(f){cout<<i<<endl;break;}}if(!f)cout<<-1<<endl;return 0;
}

這篇就到這里啦，(?′?‵?)Ｉ L???????