C/C++教程

第十三届蓝桥杯国赛C/C++ B组

本文主要是介绍第十三届蓝桥杯国赛C/C++ B组，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

@

目录
  • A 2022
  • B 钟表
  • C 卡牌
  • D 最大数字
  • E 出差
  • F费用报销
  • G 故障
  • H机房
  • I齿轮
  • J搬砖

不是正解！！！！
个人题解，可能会有错误

A 2022

算的答案是379187662194355221

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
#define int long long
int f[2050][11];
signed main()
{
    f[0][0]=1;
    for(int i=1;i<=2022;i++)
    {
        for(int j=2022;j>=i;j--)
        {
            for(int k=1;k<=10;k++)
            {
                f[j][k]+=f[j-i][k-1];
            }
        }
    }
    cout<<f[2022][10]<<endl;
    return 0;
}

B 钟表


这题补充了一下除了0 0 0以外的答案
算的答案是4 48 0

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
signed main()
{
    for(int i=0;i<12;i++)
    {
        int m=0,s=0;
        int a,b=0,c=0;
        a=3600*i;
        do
        {
            int x=abs(a-b),y=abs(b-c);
            if(x>43200/2)x=43200-x;
            if(y>43200/2)y=43200-y;
            if(x==2*y)cout<<i<<" "<<m<<" "<<s<<endl;

            a+=1;
            b=(b+12);
            c=c+720;
            c%=43200;

            s++;
            m+=s/60;
            s%=60;
        }while(m<60);

    }
    return 0;
}

C 卡牌


一眼二分题

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
#define int long long
const int N=2e5+10;
int a[N],b[N],c[N];
int n,m;
bool check(int x)//构成x套牌
{
    int res=0;
    for(int i=1;i<=n;i++)
    {
        if(a[i]+b[i]<x)return 0;
        if(x>=a[i])
            res+=x-a[i];
    }
    return res<=m;
}
signed main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)cin>>b[i];
    int l=0,r=1e9;
    while(l<r)
    {
        int mid=l+r+1>>1;
        if(check(mid))
            l=mid;
        else
            r=mid-1;
    }
    cout<<l<<endl;
    return 0;
}

D 最大数字


我写的搜索 复杂度O(2^17)

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
#define int long long
int res=0;
vector<int> q;
int m;
void dfs(int i,int ans,int a,int b)
{
    if(i==-1)
    {
        res=max(res,ans);
        return;
    }
    //都用加
    int x=q[i];
    if(a>=(9-x))
    {
        dfs(i-1,ans*10+9,a-(9-x),b);
    }
    else
    {
        int p=x+a;
        dfs(i-1,ans*10+p,0,b);
    }
    //都用减
    if(b>=(x+1))
    {
        dfs(i-1,ans*10+9,a,b-(x+1));
    }
    else
    {
        dfs(i-1,ans*10+x,a,b);//不变
    }
}
signed main()
{
    int n,a,b;
    cin>>n>>a>>b;
    while(n)
    {
        q.push_back(n%10);
        n/=10;
    }
    m=q.size()-1;
    dfs(m,0,a,b);
    cout<<res<<endl;
    return 0;
}

E 出差


最短路的板子

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
#define int long long
const int N=1e4+10,M=1e3+10;
int e[N],ne[N],h[N],idx,w[N];
int dist[M];
int t[M];
int n,m;
bool vis[N];
void add(int a,int b,int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
int dij()
{
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    priority_queue<PII,vector<PII>,greater<PII>> q;
    q.push({0,1});
    while(!q.empty())
    {
        auto p=q.top();q.pop();
        int x=p.second,y=p.first;
        if(vis[x])continue;
        vis[x]=1;
        for(int i=h[x];~i;i=ne[i])
        {
            int j=e[i];
            if(dist[j]>dist[x]+w[i]+t[j])
            {
                dist[j]=dist[x]+w[i]+t[j];
                q.push({dist[j],j});
            }
        }
    }
    return dist[n];
}
signed main()
{
    memset(h,-1,sizeof h);
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>t[i];
    t[n]=0;
    while(m--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }
    cout<<dij()<<endl;
    return 0;
}

F费用报销

在这里插入图片描述

排序+线性dp(有点像状态机)

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
#define int long long
const int N=1e3+10,M=5e3+10;
struct xx
{
    int x,w;//x代表今年的第几天
}a[N];
int p[13]={0,31,59,90,120,151,181,212,243,273,304,334,365};
int f[N];//f[i]表示取了第i天
signed main()
{
    int n,m,k;
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
    {
        int m,d,v;
        cin>>m>>d>>v;
        a[i]={p[m-1]+d,v};
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        f[i]=a[i].w;
        for(int j=1;j<i;j++)
        {
            if(abs(a[i].x-a[j].x>=k))
            {
                f[i]=max(f[i],f[j]+a[i].w);
            }
        }
        ans=max(ans,f[i]);
    }
    cout<<ans<<endl;
    return 0;
}

G 故障

在这里插入图片描述
在这里插入图片描述

概率论里的全概率与贝叶斯公式
不知道会不会卡精度...

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
typedef pair<double,int> PDI;
#define int long long
const double eps=1e-6;
const int N=50,M=25;
int q[N],p[N][M];
bool vis[N];
struct xx
{
    double x;
    int i;
    bool operator<(xx a)
    {
        if(x-a.x<0)return i<a.i;
        return x>a.x;
    }
};
signed main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>q[i];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>p[i][j];
    int k;
    cin>>k;
    for(int i=1;i<=k;i++)
    {
        int x;
        cin>>x;
        vis[x]=1;
    }
    double fm=0;
    for(int i=1;i<=n;i++)
    {
        double res=q[i];
        for(int j=1;j<=m;j++)
        {
            if(vis[j])
                res*=p[i][j]/100.0;
            else
                res*=1-p[i][j]/100.0;
        }
        fm+=res;
    }
    vector<xx> qq;
    for(int i=1;i<=n;i++)
    {
        double res=q[i];
        for(int j=1;j<=m;j++)
        {
            if(vis[j])
                res*=p[i][j]/100.0;
            else
                res*=1-p[i][j]/100.0;
        }
        qq.push_back({res/fm*100,i});
    }
    sort(qq.begin(),qq.end());
    for(auto i:qq)
        printf("%lld %.2lf\n",i.i,i.x);
    return 0;
}

H机房


最近公共祖先
由于不能查文档 因此这题写的暴力就不放了....

I齿轮


所有齿轮的线速度相同，因此只需要考虑首尾两个齿轮即可
问题的答案就转化成了这个序列中是否存在两个数的商为x
做法就是枚举倍数
时间复杂度O(n*log n)

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
#define int long long
const int N=2e5+10;
int a[N];
bool vis[N];
bool st[N];
void solve()
{
    int n=2e5;
    for(int i=1;i<=n;i++)
    {
        if(!vis[i])continue;
        for(int j=2;j*i<=n;j++)
        {
            if(vis[i*j])
            {
                st[j]=1;
            }
        }
    }
}
signed main()
{
    int n,q;
    cin>>n>>q;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        if(vis[a[i]])st[1]=1;
        vis[a[i]]=1;
    }
    solve();
    while(q--)
    {
        int x;
        cin>>x;
        if(st[x])cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}

J搬砖


GGGGGG 看成了 所有砖的重量和不能超过它自身的重量(属实是眼瞎了)

这篇关于第十三届蓝桥杯国赛C/C++ B组的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航