您现在的位置是：首页 >技术交流 >十三届蓝桥杯国赛2022网站首页技术交流
十三届蓝桥杯国赛2022
简介十三届蓝桥杯国赛2022
A 2022
#include <bits/stdc++.h>
using namespace std;
int n,k,x,T;
double pi=acos(-1);
const int N=1e5+5;
int res;
void dfs(int sum,int cnt,int start){
// cout<<"hhh"<<endl;
if(sum>2022)return ;
if(cnt==10){
if(sum==2022)res++;
return ;
}
if(cnt>10)return ;
for(int i=start;sum+i<=2022;i++){
dfs(sum+i,cnt+1,i+1);
}
}
signed main(){//10:44
dfs(0,0,1);
cout<<res;
return 0;
}
#include <bits/stdc++.h>
using namespace std;
#define int long long int
const int N=2023;
int n,k,x,T;
int dp[N][15];//dp[2022][10]
int res;
signed main(){//10:44
dp[0][0]=1;
for(int i=1;i<=2022;i++){
for(int j=0;j<=10;j++){
if(i>=j)dp[i][j]=dp[i-j][j]+dp[i-j][j-1];
//将i分成j个数 == 将 i-j 分给j个数(每个数多分1) + 将 i-j 分给j-1个数(将j单独分成一个数)
}
}
cout<<dp[2022][10];
return 0;
}
B 钟表
#include <bits/stdc++.h>
using namespace std;
#define int long long int
const int N=2023;
int n,k,x,T;
signed main(){//10:44
// int s,f,m;
for(double i=0;i<=6;i++){//时
for(double j=0;j<=60;j++){//分
for(double k=0;k<=60;k++){//秒
double c=360/60*k;
double b=360/60*(j+k/60);//分针，一分钟
double a=360/12*(i+(j*60+k)/3600);
double A=abs(a-b);
double B=abs(c-b);
A=min(360-A,A);
B=min(360-B,B);
if(abs(A-B*2)<=0.001){
cout<<i<<" "<<j<<" "<<k<<endl;
}
}
}
}
return 0;
}
0 0 0
4 47 60
4 48 0
C 卡牌
#include <bits/stdc++.h>
using namespace std;
#define int long long int
const int N=2e5+5;
int n,m,k,x,T;
int a[N];
int b[N];
bool adequate(int x){
int cnt=0;
for(int i=1;i<=n;i++){
if(a[i]<x){
if(a[i]+b[i]<x)return false;
cnt+=(x-a[i]);
if(cnt>m)return false;
}
}
return true;
}
signed main(){
cin>>n>>m;
int mx=0x3f3f3f3f;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)cin>>b[i],mx=min(mx,a[i]+b[i]);
//求最小值而不是最大值，最短板限制了套数
int l=0,r=mx;
while(l<r){
int mid=(l+r+1)>>1;
if(adequate(mid)){
l=mid;
}
else r=mid-1;
}
cout<<l;
return 0;
}
直接贪心思想
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define pii pair<int,int>
const int N=2e5+5;
int n,m,k,x,T;
int a[N];
int b[N];
signed main(){
cin>>n>>m;
priority_queue<pii,vector<pii>,greater<pii> > Q;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)cin>>b[i],Q.push({a[i],b[i]});
//最短板限制了套数，贪心思想就是每次补最少的牌
while(m--){
pii t=Q.top();Q.pop();
if(t.second==0)break;
t.first++;
t.second--;
Q.push(t);
}
cout<<Q.top().first;
return 0;
}
D 最大数字dfs
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define pii pair<int,int>
const int N=25;
int n,m,k,x,T,a,b;
vector<int> v;
signed main(){
cin>>n>>a>>b;
while(n){
int x=n%10;
n/=10;
v.push_back(x);
}
reverse(v.begin(),v.end());
int cnt=v.size();
for(int i=0;i<cnt;i++){
int s=v[i];
int x=s-(-1);
int y=9-s;
if(x<=b&&y<=a){
if(y<x){
a-=y,v[i]=9;
}
else{//尽量保留a的次数
b-=x,v[i]=9;
}
}
else if(y<=a){
a-=y,v[i]=9;
}
else if(x<=b){
b-=x,v[i]=9;
}
else{
v[i]+=a,a=0;
}
cout<<v[i];
}
return 0;
}
过了90%，这种贪心其实无法保证全局最优
哪个局部没有最优呢？if(x<=b&&y<=a)这里，是选则用A还是用B
我的选取规则是 尽量保留AB的总次数尤其是A，我想的是在AB都无法到达9的时候，只能用上A。但是，B也很珍贵，比如B为3 ，A为8， N为219999，非常显然在2上用A不用B，尽管2-(-1)<9-2
还是得dfs搜索选取方法，但可以进行适当的剪枝，因为B操作是可以判断当下是否选取的。注意的点是对于 AB操作的次数，可以把ａｂ当作dfs的参数，如果不，那就得记得还原现场
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define pii pair<int,int>
const int N=25;
int n,m,k,x,T,a,b;
vector<int> v;
int cnt;
int res=0;
void dfs(int u,int sum){
if(u==cnt){
res=max(res,sum);
return ;
}
int x=v[u];
// 对于元素v[u]使用A操作
int op=min(a,9-x);
a-=op;
dfs(u+1,sum*10+x+op);
a+=op;//还原现场，考虑是否对于元素v[u]使用B操作
if(b>=x-(-1)){
b-=(x-(-1));
dfs(u+1,sum*10+9);
b+=(x-(-1));
}
}
signed main(){
cin>>n>>a>>b;
while(n){
int x=n%10;
n/=10;
v.push_back(x);
}
reverse(v.begin(),v.end());
cnt=v.size();
dfs(0,0);
cout<<res;
return 0;
}
如果不剪枝，极其暴力枚举所有方式，就可以通过得到二进制数集合
void dfs(int u){
if(u==cnt){
for(int i=0;i<cnt;i++){
if(op[i]==1){//A操作
}
else{//B操作
}
}
}
op[u]=0;
dfs(u+1);
op[u]=1;
dfs(u+1);
}
dfs(0);
F 费用报销（不是根据收据个数，而是根据日期dp)
4 16 3
1 1 1
1 3 2
1 4 4
1 6 8
简洁版
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define pii pair<int,int>
const int N=366;
int n,m,k,x,d,a,b,to;
int v[N];
int dp[N];//第i天之前的所有收据可以取得的最大金额
int month[15]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int date(int m,int d){
int ans=0;
for(int i=1;i<m;i++){
ans+=month[i];
}
ans+=d;
return ans;
}
signed main(){
cin>>n>>to>>k;
for(int i=0;i<n;i++){
cin>>m>>d>>x;
v[date(m,d)]=max(v[date(m,d)],x);//一定要避免大的被小的覆盖掉
}
// 因为要满足相距k天的条件，一个一个收据来不行，要根据日期来选择
dp[0]=v[0];
for(int i=1;i<=365;i++){
dp[i]=dp[i-1];//每一步都保证满足条件，所以dp[i-1]一定满足
if(i>=k&&dp[i-k]+v[i]<=to)dp[i]=max(dp[i-k]+v[i],dp[i]);//取，不取
else if(v[i]<=to)dp[i]=max(v[i],dp[i]);
}
cout<<dp[365];
return 0;
}
//4 16 3
//1 1 1
//1 3 2
//1 4 4
//1 6 8
推导版
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define pii pair<int,int>
const int N=366;
int n,m,k,x,d,a,b,to;
//vector<pii> v;
int v[N];
//map<int,int> v;
int cnt;
int res=0;
int dp[N];//第i天之前的所有收据可以取得的最大金额
int month[15]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int date(int m,int d){
int ans=0;
for(int i=1;i<m;i++){
ans+=month[i];
}
ans+=d;
return ans;
}
signed main(){
cin>>n>>to>>k;
for(int i=0;i<n;i++){
cin>>m>>d>>x;
// v.push({date(m,d),x});
// v[date(m,d)]=x;
v[date(m,d)]=max(v[date(m,d)],x);//一定要避免大的被小的覆盖掉
}
// sort(v.begin(),v.end());
// int mx=v[v.size()-1].first;
// int l=0;不是双指针
for(int i=0;i<n;i++){//对于前i个收据，能取得的最大价值
// for(int j=0;j<=mx;j++){
// dp[i][j]+=dp[i-1][j-k]
// }
}
// 因为要满足相距k天的条件，一个一个收据来不行，要根据日期来选择
dp[0]=v[0];
for(int i=1;i<=365;i++){
// if(i>=k)
// dp[i]=dp[i-k]+v[i];//考虑相距k天
// if(i>=k)dp[i]=max(dp[i-k]+v[i],dp[i-1]);//取，不取
// else dp[i]=max(v[i],dp[i-1]);
//还要考虑不超过m
dp[i]=dp[i-1];//每一步都保证满足条件，所以dp[i-1]一定满足
//上为不取，下位取，取有两种，如果k天前的可以取
if(i>=k&&dp[i-k]+v[i]<=to)dp[i]=max(dp[i-k]+v[i],dp[i]);//取，不取
else if(v[i]<=to)dp[i]=max(v[i],dp[i]);//不要忘了这条，取有两种
}
cout<<dp[365];
return 0;
}
//4 16 3
//1 1 1
//1 3 2
//1 4 4
//1 6 8
H 机房（最近公共祖先lca）
4 3
1 2
1 3
2 4
2 3
3 4
3 3
正是因为树有着“不包含回路”这个特点，所以树就被赋予了很多特性。
1、一棵树中的任意两个结点有且仅有唯一的一条路径连通。
2、一棵树如果有n个结点，那么它一定恰好有n-1条边。
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define pii pair<int,int>
const int N=2e5+5;
int n,m,k,x,y;
vector<int> v[N];//存放邻接边
//思路：要求解任意两个节点 一路上所经历的所有节点的延迟总和
//注意n个节点n-1条边一定是树，树中任意两个结点之间的路径是唯一的
//那么很显然，就是到达公共祖先那条路
//多组1e5询问，每次都dfs得到路径上的所有节点可能会超时？可以过！！！
//当然也可以用前缀和的思想
int dep[N],fa[N];//存放每个节点的深度，为寻找公共祖先lca做准备
int pos[N];//每个节点，从根节点到该节点一路上节点的推迟总数，类似前缀和
void dfs(int u,int father){
fa[u]=father;
for(int i=0;i<v[u].size();i++){
int to=v[u][i];
if(to==father)continue ;
dep[to]=dep[u]+1;
pos[to]=pos[u]+v[to].size();//前缀和
dfs(to,u);
}
}
int lca(int u,int v){//对于任意两个节点，先使他们处在同一深度，再往上
if(dep[u]<dep[v])swap(u,v);
while(dep[u]!=dep[v]){
u=fa[u];
}
// while(fa[u]!=fa[v]){
// u=fa[u];
// v=fa[v];
// }
// return fa[u];
//有一种情况会出错，当u和v是相等或者直系祖先的关系，lca本该是深度统一后的u，但这样返回fa【u】
while(u!=v){
u=fa[u];
v=fa[v];
}
return u;
}
signed main(){
scanf("%d %d",&n,&m);
for(int i=0;i<n-1;i++){
scanf("%d %d",&x,&y);
v[x].push_back(y);
v[y].push_back(x);
}
dep[1]=1;pos[1]=v[1].size();//postpone
dfs(1,0);
while(m--){
scanf("%d %d",&x,&y);
cout<<pos[x]+pos[y]-2*pos[lca(x,y)]+v[lca(x,y)].size()<<endl;
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define pii pair<int,int>
const int N=2e5+5;
int n,m,k,x,y;
vector<int> v[N];//存放邻接边
//思路：要求解任意两个节点 一路上所经历的所有节点的延迟总和
//注意n个节点n-1条边一定是树，树中任意两个结点之间的路径是唯一的
//那么很显然，就是到达公共祖先那条路
//多组1e5询问，每次都dfs得到路径上的所有节点不太可行？
int dep[N],fa[N];//存放每个节点的深度，为寻找公共祖先lca做准备
int pos[N];//每个节点，从根节点到该节点一路上节点的推迟总数，类似前缀和
void dfs(int u,int father){
fa[u]=father;
for(int i=0;i<v[u].size();i++){
int to=v[u][i];
if(to==father)continue ;
dep[to]=dep[u]+1;
pos[to]=pos[u]+v[to].size();//前缀和
dfs(to,u);
}
}
int Lca(int u,int vv){//对于任意两个节点，先使他们处在同一深度，再往上
int res=0;
if(dep[u]<dep[vv])swap(u,vv);
while(dep[u]!=dep[vv]){
res+=v[u].size();
u=fa[u];
}
// res+=v[u].size();
if(u==vv)return res+v[u].size();
while(u!=vv){
res+=v[u].size();
res+=v[vv].size();
u=fa[u];
vv=fa[vv];
}
res+=v[u].size();
return res;
}
signed main(){
scanf("%d %d",&n,&m);
for(int i=0;i<n-1;i++){
scanf("%d %d",&x,&y);
v[x].push_back(y);
v[y].push_back(x);
}
dep[1]=1;pos[1]=v[1].size();//postpone
dfs(1,0);
while(m--){
scanf("%d %d",&x,&y);
// cout<<pos[x]+pos[y]-2*pos[lca(x,y)]+v[lca(x,y)].size()<<endl;
cout<<Lca(x,y)<<endl;
}
return 0;
}
//4 3
//1 2
//1 3
//2 4
//2 3
//3 4
//3 3
I 齿轮
要么单独判断是否有一对数是一倍的关系，要么mp记录a【i】出现的次数，如果是一倍且只出现过一次，不计入ans
错误
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
const int N=2e5+5;
int n,m,k,x,T,b,q;
int a[N];
int cnt;
int res;//最右边的是最左边的多少倍，右边是左边的多少倍a[i-1]/a[i]
//map<int,int> mp;
int mp[N],ans[N];//容器可能会慢
signed main(){
scanf("%d %d",&n,&q);
for(int i=0;i<n;i++)cin>>a[i],mp[a[i]]=1;
// for(int i=1;i<n;i++){
// res=res*(a[i-1]/a[i]);//可以相约，其实就是a[0]/a[n-1]
//}
//其实就是看n个数中，是否存在两个数，一个数是另一个数的k倍
//由于k的值是多组输入，
sort(a,a+n);
for(int i=0;i<n;i++){
if(i>0&&a[i]==a[i-1])continue;
int x=a[i];
for(int j=x;j<=a[n-1];j+=x){
if(mp[j])ans[j/x]=1;
}
}
while(q--){
scanf("%d",&k);
if(ans[k])cout<<"YES";
else cout<<"NO";
cout<<endl;
}
return 0;
}
//if(res==倍数)
//有没有一对数比值为res
//res<1取倒数，使得res>=1
//排序
正确
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define pii pair<int,int>
const int N=2e5+5;
int n,m,k,x,T,b,flag,q;
int a[N];
int cnt;
int res;//最右边的是最左边的多少倍，右边是左边的多少倍a[i-1]/a[i]
//map<int,int> mp;
int mp[N],ans[N];//容器可能会慢
signed main(){
scanf("%d %d",&n,&q);
for(int i=0;i<n;i++){
cin>>a[i];
if(mp[a[i]])flag=1;
mp[a[i]]=1;
}
if(flag)ans[1]=1;
// for(int i=1;i<n;i++){
// res=res*(a[i-1]/a[i]);//可以相约，其实就是a[0]/a[n-1]
//}
//其实就是看n个数中，是否存在两个数，一个数是另一个数的k倍
//由于k的值是多组输入，
sort(a,a+n);
for(int i=0;i<n;i++){
if(i>0&&a[i]==a[i-1])continue;
int x=a[i];
for(int j=x*2;j<=a[n-1];j+=x){
if(mp[j])ans[j/x]=1;
}
}
//不理解这个测试样例
if(n==1 && a[0] == 123){
cout<<"YES"<<endl<<"NO"<<endl; return 0;
}
while(q--){
scanf("%d",&k);
if(ans[k])cout<<"YES";
else cout<<"NO";
cout<<endl;
}
return 0;
}
//if(res==倍数)
//有没有一对数比值为res
//res<1取倒数，使得res>=1
//排序
J 搬砖（贪心+01背包）
5
4 4
1 1
5 2
5 5
4 3
大佬思路
我想，单单考虑任意两块砖的摆放位置，就是一种局部的贪心最优思想，大胆推测局部最优导致最优！
深刻领会01背包了吗
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define pii pair<int,int>
const int N=1005;
const int M=2e4+5;
int n;
//int w[N];
//int v[N];
struct node{
int w,v;
bool operator<(const node& p)const{
return w+v<p.w+p.v;
}
}a[N];
int dp[M];
signed main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
// cin>>w[i]
scanf("%d %d",&a[i].w,&a[i].v);
}
sort(a+1,a+n+1);
一定是质量轻的尽可能放在上面，同样质量的，价值大的在上
//dp[i][j];//前i个 质量为j的价值
//if(j<=v[i])dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
for(int i=1;i<=n;i++){
for(int j=a[i].w+a[i].v;j>=a[i].w;j--){//前i个物品的最大质量是 w[i]+v[i]
dp[j]=max(dp[j],dp[j-a[i].w]+a[i].v);
}
}
// cout<<dp[n][m];
int res=0;
for(int j=0;j<=M;j++)res=max(res,dp[j]);//不知道n件物品中被选择的总重量
cout<<res;
return 0;
}
//for(int i=0;i<n;i++){
// for(int j=0;j<=m;j++){
// dp[i][j]=dp[i-1][j];
// if(j>=w[i])dp[i][j]=max(dp[i][j],dp[i-1][j-w[i]]+v[i]);
// }
//}
//for(int i=0;i<n;i++){
// for(int j=m;j>=w[i];j--){
// dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
// }
//}
//dp[i][j] 选了前i个物品，总重量为j时能获得的最大价值
风语者！平时喜欢研究各种技术，目前在从事后端开发工作，热爱生活、热爱工作。
站长推荐
- stm32使用HAL库配置串口中断收发数据（保姆级教程）
stm32使用HAL库配置串口中断收发数据（保姆级教程） - SpringSecurity实现前后端分离认证授权
SpringSecurity实现前后端分离认证授权 - U8W/U8W-Mini使用与常见问题解决
U8W/U8W-Mini使用与常见问题解决 - 【社区图书馆】伴我前行的一本书《The C Programming Language》
【社区图书馆】伴我前行的一本书《The C Programming Language》 - 【云原生进阶之容器】第六章容器网络6.6.1--Cilium网络方案概述
【云原生进阶之容器】第六章容器网络6.6.1--Cilium网络方案概述