「蓝桥·算法双周赛」第一场公开赛

本文主要是介绍「蓝桥·算法双周赛」第一场公开赛，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

三带一【算法赛】 - 蓝桥云课 (lanqiao.cn)

给定四个字符，判断是否其中有三个相同，另一个与他们不同

#include <bits/stdc++.h>
void solve()
{std::string s;std::cin>>s;char a=s[0],b=s[1],c=s[2],d=s[3];if(a==b&&a==c&&a!=d) std::cout<<"Yes"<<'\n';else if(a==b&&a==d&&a!=c) std::cout<<"Yes"<<'\n';else if(a==d&&a==c&&a!=b) std::cout<<"Yes"<<'\n';else if(d==b&&d==c&&a!=d) std::cout<<"Yes"<<'\n';else std::cout<<"No"<<'\n';
}
signed main()
{int t;std::cin>>t;while(t--){solve();}return 0;
}

数树数【算法赛】 - 蓝桥云课 (lanqiao.cn)

二叉树性质问题，不了解二叉树也完全可以做。

要注意的是每次都从第一行的第一个点开始走，给一个字符串按照它走，输出最后的结果就行。

往左走坐标就变成了2*pos-1，往右就变成了2*pos

画个树理解一下就好了。

#include <bits/stdc++.h>signed main()
{int n,q;std::cin>>n>>q;int pos=1;while(q--){pos=1;std::string s;std::cin>>s;int i=0;while(s[i]){if(s[i]=='L') {pos=2*pos-1;}else if(s[i]=='R'){pos*=2; }i++;}std::cout<<pos<<'\n';}return 0;
}

分组【算法赛】 - 蓝桥云课 (lanqiao.cn)

这题是二分。

二分极差，然后判断如果以该极差来分组，所分的组数能否小于k(如果小于k，那么k肯定能满足。因为一个数可以单独成一组，即极差为0），如果能就减小极差继续试探，否则增大极差。

#include<bits/stdc++.h>
const int N=1e5+10;
int a[N];
int n,k;bool check(int x)
{int last=1,cnt=1;for(int i=1;i<=n;i++){if(a[i]-a[last]>x)//如果当前这个不行就分组{last=i;cnt++;}}return cnt<=k;
}
signed main()
{std::cin>>n>>k;for(int i=1;i<=n;i++) std::cin>>a[i];std::sort(a+1,a+1+n);int l=0,r=2e9,res=0;//枚举极差while(l<=r){int mid=l+r>>1;if(check(mid)) {res=mid;r=mid-1;}else l=mid+1;}std::cout<<res;return 0;
}

健身【算法赛】 - 蓝桥云课 (lanqiao.cn)

十年OI一场空，不开longlong见祖宗。

这道题是一个完全背包问题，需要注意的是si范围是1e9，不开longlong会死。

首先dp预处理出对应连续天数能收获的最大分数。

然后对连续天数进行计算，每算出一个连续天数就加上对应的分数。

#include <bits/stdc++.h>
const int N=2e5+10;
#define int long long
int n,m,q;
int cantuse[N],k[N],s[N];
struct st{int k,s;
}a[N];
int res,cnt;
int f[N];
#define int long long
void solve()//有i天怎么用最大化 
{for(int i=1;i<=m;i++)//对物品遍历 {for(int j=a[i].k;j<=n;j++)//对容积遍历 {f[j]=std::max(f[j],f[j-a[i].k]+a[i].s);}}
}
signed main()
{std::cin>>n>>m>>q;	for(int i=1;i<=q;i++){int d;std::cin>>d;cantuse[d]=1;}for(int i=1;i<=m;i++){std::cin>>a[i].k>>a[i].s;a[i].k=pow(2,a[i].k);}solve();f[0]=0;for(int i=1;i<=n;i++){if(!cantuse[i]) cnt++;else{res+=f[cnt];cnt=0;}}if(cnt) res+=f[cnt];std::cout<<res;return 0;
}