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

现在他想要从这个数组中寻找一些满足以下条件的子序列：

1. 子序列的长度为 88；
2. 这个子序列可以按照下标顺序组成一个 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ᵒᵛᵉᵧₒᵤ❤