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

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

算的答案是379187662194355221

#include 
using namespace std;
typedef pair 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< 
B 钟表 

 这题补充了一下除了0 0 0以外的答案
 算的答案是4 48 0
 
#include 
using namespace std;
typedef pair 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< 
C 卡牌 

 一眼二分题
 
#include 
using namespace std;
typedef pair 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]=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
        int mid=l+r+1>>1;
        if(check(mid))
            l=mid;
        else
            r=mid-1;
    }
    cout< 
D 最大数字 

 我写的搜索 复杂度O(2^17)
 
#include 
using namespace std;
typedef pair PII;
#define int long long
int res=0;
vector 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< 
E 出差 

 最短路的板子
 
#include 
using namespace std;
typedef pair 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,greater> 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< 
F费用报销 
 
排序+线性dp(有点像状态机)
 
#include 
using namespace std;
typedef pair PII;
#define int long long
const int N=1e3+10,M=5e3+10;
struct xx
{
    int x,w;//x代表今年的第几天
    bool operator<(xx a)
    {
        return x0,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};
    }
    sort(a+1,a+n+1);
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        f[i]=a[i].w;
        for(int j=1;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< 
G 故障 

 
 
概率论里的全概率与贝叶斯公式
 不知道会不会卡精度…
 
#include 
using namespace std;
typedef pair PII;
typedef pair 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 ia.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 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 %.2lfn",i.i,i.x);
    return 0;
}
 
H机房 

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

 所有齿轮的线速度相同，因此只需要考虑首尾两个齿轮即可
 问题的答案就转化成了这个序列中是否存在两个数的商为x
 做法就是枚举倍数
 时间复杂度O(n*log n)
 
#include 
using namespace std;
typedef pair 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"< 
J搬砖 
 
01背包dp题，不知道为什么放在了最后一题
 
#include 
using namespace std;
typedef pair 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"<