第十四届省赛C++B组
# 第十四届蓝桥杯大赛软件赛省赛 C/C++大学 B 组
# 1、日期统计
本题的意思就是 2023 年一整年，所有的日期，都用 yyyymmdd 表示，是否能从给出的数组中找到对应的数字。
已知 2023 不会再变，我们只需要枚举月份和天数即可。 因为是子序列所以我们也要按照顺序找对应数字。
代码分析：
#include<bits/stdc++.h>
using namespace std;
int a[105];
// 闰年是 29 天，平年是 28 天
int d[]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int sa[10];
int main(){
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
for(int i=0;i<100;i++)cin>>a[i];
int ans=0;
for(int i=1;i<=12;i++){
for(int j=1;j<=d[i];j++){
int date[8]={2,0,2,3,i/10,i%10,j/10,j%10};
int index=0;
for(int k=0;k<100;k++){
if(a[k]==date[index]){
index++;
if(index==8){
ans++;
break;
}
}
}
}
}
cout<<ans;
return 0;
}
# 2、01 串的熵
这一题要有数学思维，可以先表达式化简在进行计算。经过对对数的化简，我们求出 x 即可得到结果。
代码示例：
#include<bits/stdc++.h>
using namespace std;
double n=23333333;
int main(){
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
double res=-(11625907.5798);
for(int x=10;x<n+100000;x++){
double num=pow(x,2)*(log2(x)-log2(n))+pow(n-x,2)*(log2(n-x)-log2(n));
num/=n;
if(num<=res){
cout<<x;return 0;
}
}
return 0;
}
# 3、冶炼金属
对于 100%的数据，要满足到 1e9 所以我们要使用 long long 的数据类型。
示例代码：
#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;
using ll = long long;
int main(){
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
// A B V B <= A/V < B+1 咱们是为了找到maxv,minv
// 1/(B+1) < V/A <= 1/B
// A/(B+1) < V <= A/B
int n;cin>>n;
ll maxv=1e18,minv=0;
for(int i=0;i<n;i++){
ll a,b;cin>>a>>b;
maxv=min(maxv,a/b);// 最大值是偏小的哪个
minv=max(minv,a/(b+1)+1);
}
cout<<minv<<" "<<maxv;
return 0;
}
# 4、飞机降落
其实对于这一题，就是纯全排列问题，也就是说只要有一组方式满足题意即可。我们可以使用搜索来写，每一架飞机受到的影响都是前一架飞机降落的最晚时间。
示例代码：
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 15;
struct node{
int t,d,l;
}p[N];
int n;
bool vis[N];
bool dfs(int dep,int last){
if(dep==n)return true;
for(int i=0;i<n;i++){
int t,d,l;
t=p[i].t,d=p[i].d,l=p[i].l;
if(!vis[i]&&last<=t+d){
vis[i]=true;
if(dfs(dep+1,max(last,t)+l))return true;
vis[i]=false;
}
}
return false;
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int T;cin>>T;
while(T--){
cin>>n;
for(int i=0;i<n;i++){
int t,d,l;cin>>t>>d>>l;
p[i]={t,d,l};
}
memset(vis,0,sizeof(vis));
if(dfs(0,0))cout<<"YES\n";
else cout<<"NO\n";
}
return 0;
}
# 5、接龙数列
动态规划的问题，题中问的是最少删除几个，我们可以得到接龙数列？那么我们就可以逆向思维，不妨找到最长的接龙数列 ans，让 n-ans。
我们可以设置状态dp[i]表示以 i 结尾的最长接龙数列。
代码示例：
#include<iostream>
#include<vector>
using namespace std;
int dp[15];// 表示以i结尾的最长接龙数列
int n;
string s;
int main(){
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
cin>>n;
for(int i=0;i<n;i++){
cin>>s;
int l=s.size();
// 这里就感觉非常像lis那种类型一样都是这样的动态规划
dp[s[l-1]-'0']=max(dp[s[l-1]-'0'],dp[s[0]-'0']+1);
}
int maxn=0;
for(int i=0;i<10;i++)maxn=max(maxn,dp[i]);
cout<<n-maxn;
return 0;
}
# 6、岛屿个数
其实我们不需要遍历连通没有，我们要找的是岛屿的数量，只需要在外层加一层海洋，外层海洋可以涌入的地方，如果涌入的地方周围有陆地，那么这块陆地一定不在一个子岛屿中，反之，某个地方外层海洋无法涌入，一定是被某个环状岛屿包围所导致的，即位于某个子岛屿中。外层海洋无法涌入的地方，无需遍历。
从(0,0)处进行外层海洋的 bfs，由于岛屿是上下左右四个方向的，那么外层海洋往里面渗入时需要从八个方向进行遍历。在进行外层海洋 bfs 时，如果遇到陆地了，那么说明所在的岛屿连通块需要被统计，此时进行岛屿的 bfs。
代码示例：
#include<iostream>
#include<cstring>
#include<queue>
#define pii pair<int,int>
using namespace std;
int dx[8] = {1, -1, 0, 0, 1, -1, 1, -1};
int dy[8] = {0, 0, 1, -1, 1, -1, -1, 1};
const int N = 55;
char g[N][N];
bool vis[N][N];
int n, m, ans;
//岛屿BFS
void bfs(int sx, int sy){
queue<pii> q;
q.push({sx,sy});
vis[sx][sy]=true;
while(!q.empty()){
pii d=q.front();
q.pop();
for(int k=0;k<4;k++){
int nx=d.first+dx[k],ny=d.second+dy[k];
if(nx<1||nx>n||ny<1||ny>m)continue;
if(g[nx][ny]=='0'||vis[nx][ny])continue;
q.push({nx,ny});
vis[nx][ny]=true;
}
}
}
//外层海洋BFS
void bfs_sea(int sx, int sy){
queue<pii> q;
q.push({sx, sy});
vis[sx][sy] = true;
while(!q.empty()){
pii d = q.front();
q.pop();
for(int k=0;k<8;k++ ){
int nx=d.first+dx[k],ny=d.second+dy[k];
if(nx<0||nx>n+1||ny<0||ny>m+1||vis[nx][ny])continue;
if(g[nx][ny] == '1'){
bfs(nx, ny);
ans++; //如果遇到外层海水领近的陆地
}else{
q.push({nx,ny});
vis[nx][ny]=true;
}
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int t;cin>>t;
while(t--){
ans=0;
cin>>n>>m;
memset(vis,0,sizeof(vis));
memset(g,'0',sizeof(g));
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>g[i][j];
bfs_sea(0,0);
cout<<ans<<"\n";
}
return 0;
}
# 7、子串简写
我们可以看到数据规模是 5e5，如果我们使用双指针遍历寻找的话，肯定超时只能的一部分分，我们就需要考虑优化过程，不让其两次循环遍历，我们就可以想到前缀和数组，去记录答案。
在这道题上，我们应该使用后缀和数组，nexsum[i] 表示的是在 i 的右边有 nextsum[i] 个 c2 字符，那么我们就可以用 nextsum[i+k-1] 直接得到符合题意的数量了。
示例代码：
#include<iostream>
using namespace std;
using ll = long long;
const int N = 5e5+5;
ll nextsum[N];
char c1,c2;
string s;
int main(){
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
int K;cin>>K;// j - i >= K
cin>>s>>c1>>c2;
ll ans=0;
for(int i=s.size()-1;i>=0;i--){
nextsum[i]=nextsum[i+1];
if(s[i]==c2){
nextsum[i]++;
}
}
for(int i=0;i<s.size();i++){
if(s[i]==c1&&i+K-1<s.size()){
ans+=nextsum[i+K-1];
}
}
cout<<ans;
return 0;
}
# 8、整数删除
其实我看到选择最靠前的最小值时，我就想到的优先队列来写，但是我又考虑到这个数的两边的都要加上这个被删除的值，所以如果用优先队列的话会不会破坏数据的顺序所以就用了 vector 来写，结果就是过了 30%（O(n2)），其它的全部超时了。如果想要过掉全部数据就要使用优化的算法。
所以我们就要使用链表+优先队列去优化这个过程:
1、找出最小值（小根堆）{ a[pos] , pos } -> pair<int,int>
2、找到最小值相邻的未被删除的数字
//1.没有优化的代码，超时
//#include<iostream>
//#include<vector>
//using namespace std;
//using ll = long long;
//vector<ll> a;
//int n,k,t;
//int getmin_index(){
// int idx=0;
// for(int i=1;i<t;i++){
// if(a[i]<a[idx])idx=i;
// }
// return idx;//第一个最小值的下标
//}
//int main(){
// ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
// cin>>n>>k;
// for(int i=0;i<n;i++){
// ll num;cin>>num;
// a.push_back(num);
// }
// t=n;
// while(k--){
// int index=getmin_index();
// ll tmp=a[index];
// if(index-1>=0)a[index-1]+=tmp;
// if(index+1<=t)a[index+1]+=tmp;
// a.erase(a.begin()+index);
// t=a.size();
// }
// for(const auto& x:a)cout<<x<<" ";
// return 0;
//}
// 2.采用链表+堆优化这个过程
#include<iostream>
#include<queue>
using namespace std;
#define ll long long
#define pii pair<ll,ll>
const ll N = 5e5+10;
ll l[N],r[N],st[N];
// l[N] 表示i位置左边的位置
// r[N] 表示i位置右边的位置
int n,k;
int main(){
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
cin>>n>>k;
priority_queue<pii,vector<pii>,greater<pii>> q;
for(ll i=0;i<n;i++){
ll num;cin>>num;
q.push({num,i});
st[i]=num;
l[i]=i-1;
r[i]=i+1;
if(r[i]==n)r[i]=-1;
}
while(k){
pii p=q.top();
q.pop();
/*
为什么这里要判断一下p.first!=st[p.second]呢？
因为我们已经再下面将st[i]的值更新了，但是这个更新的值并没有重新应用到堆里面。
所以我们需要更新这个值，而且哪个在堆里面没有更新的值已经pop掉了。所以不用担心重复增加问题。
*/
if(p.first!=st[p.second]){
q.push({st[p.second],p.second});
continue;
}
k--;
ll pos = p.second;
// l[i] r[i] 这个双向链表要仔细理解
if(l[pos]>=0)st[l[pos]]+=p.first;
if(r[pos]>=0)st[r[pos]]+=p.first;
if(l[pos]>=0)r[l[pos]]=r[pos];
if(r[pos]>=0)l[r[pos]]=l[pos];
st[pos]=-1;
}
for(ll i=0;i<n;i++){
if(st[i]!=-1)cout<<st[i]<<' ';
}
return 0;
}
# 9、景区导游
看到路径的题，首先想到的就是最短路径算法 dijkstra 和 floyd，我不太会 dijkstra 所以我用的 floyd，对于此题，评测规模时 1e5 那么使用 floyd 必定超时或者空间不够，在此我只记录自己的写法。
我们可以先将所有的最短路径都预处理一下，此后我们就只需要进行枚举灭一个要走的景点即可。
暴力解法，只能通过 30%：
#include<iostream>
#include<vector>
#include<algorithm>
#define ll long long
using namespace std;
const ll N = 5e3+10,INF = 1e18;
ll d[N][N];
int n,m;
void floyd(){
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
if(d[i][k]!=INF&&d[k][j]!=INF){
d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
}
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
d[i][j]=INF;
cin>>n>>m;
for(int i=0;i<n-1;i++){
int u,v,w;cin>>u>>v>>w;
d[u][v]=d[v][u]=w;
}
vector<int> a;
for(int i=0;i<m;i++){
int nn;cin>>nn;
a.push_back(nn);
}
floyd();
for(int i=0;i<a.size();i++){
int ans=0;
vector<int> p(a.begin(),a.end());
p.erase(p.begin()+i);
for(int j=0;j<p.size()-1;j++){
int u=p[j],v=p[j+1];
ans+=d[u][v];
}
cout<<ans<<" ";
}
return 0;
}
# 10、砍树
根据题意我们可以知道，就是一个有 n-1 条边的树，现在要求的是剪短一条边，会让所有的数对都不在连通的结果，问这个边的最大的编号是什么？ 根据上面，我们知道剪短 2 和 4 都可以实现 3-5，4-6 不连通，但是 4>2 所以我们剪短 2。 所以说这道题就是考察图的连通性的，所以我们可以使用搜索从编号大的向小的遍历看那个符合要求就输出，否则输出-1。
暴力解法，只能通过 30%：
#include<iostream>
#include<vector>
#include<cstring>
#define ll long long
using namespace std;
const ll N = 1e5+10;
vector<pair<ll,ll>> g[N];// 前向星
bool vis[N];
ll n,m,s[N],t[N];// (s[i],t[t]) 数对
bool dfs(int s,int t,int id){
if(s==t)return true;
for(int i=0;i<g[s].size();i++){
ll nxt=g[s][i].first,edgeId=g[s][i].second;
if(edgeId==id)continue;//如果传进来的id等于要删除的边的编号则不走
if(vis[nxt])continue;
vis[nxt]=1;
if(dfs(nxt,t,id))return true;
}
return false;
}
int main(){
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
cin>>n>>m;
for(int i=1;i<n;i++){
int u,v;cin>>u>>v;
// 邻接表
g[u].push_back({v,i});//u - v,记录这条边编号为 i
g[v].push_back({u,i});
}
for(int i=1;i<=m;i++){
cin>>s[i]>>t[i];
}
// 从编号大的向小的搜索 g[i]
for(int i=n-1;i>=1;i--){
bool flag=true;
// 搜索每个数对 是否不连通 s[j] -> t[j] 如果搜不到即为成功
for(int j=1;j<=m;j++){
memset(vis,0,sizeof(vis));
vis[s[j]]=1;
if(dfs(s[j],t[j],i)){
flag=false;
break;
}
}
if(flag){
cout<<i;return 0;
}
}
cout<<"-1";
return 0;
}