牛客练习赛114 | Crystal’s Blog

type

Post

status

Published

date

Aug 26, 2023

slug

牛客练习赛114

summary

A

从大到小输出数字。

c++代码


#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
int a[20];
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];
sort(a,a+n);
if(a[0]!=0)
cout<<-1<<endl;
else{
for(int i=n-1;i>=0;i--)
cout<<a[i];
}
return 0;
}

B

算出平局的概率，从而得出不是平局的概率，再取倒数。

c++代码


#include<bits/stdc++.h>
using namespace std;
int main(){
    int T;
    cin>>T;
    while(T--){
        int a,b,c,a1,b1,c1;
        cin>>a>>b>>c>>a1>>b1>>c1;
        int t=100-a*a1-b*b1-c*c1;
        if(t==0){
            cout<<"Sorry,NoBruteForce"<<endl;
        }else{
            double ans=100.0/t;
            cout<<setprecision(8)<<ans<<endl;
        }
        
    }
}

C

题意

给出长度为n的序列，要求从中选出最少的序列字段使得重新排序后的序列字段变成[1,2,…m]。

比如：n=10,m=7,序列为[2,1,4,5,6,7,3,4,1,2]。答案是选中3段：[5,6,7],[3,4],[1,2]。再找不出更少的字段块数满足条件。

题解

动态规划。转移方程比较难想

g[m]表示：在以值m结尾的连续递增字段中,最小的开头值-1。比如在[2 1 4 5 6 7 3 4 1 2], g[2]=1-1=0,g[1]=1-1=0,g[4]=3-1=2, g[5]=4-1=3,g[6]=4-1=3,g[7]=4-1=3,g[3]=3-1=2

dp[m]表示：在整个序列中，凑成[1,2,..m]需要的最少字段块数

转移方程：dp[m]=dp[g[m]]+1

c++代码


#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
int main(){
    int T;
    cin>>T;
    while(T--){
        int n,m;
        cin>>n>>m;
        vector<int>a(n);
        for(auto&x:a){
            cin>>x;
        }
        /*
        g[m]表示：在以值m结尾的连续递增字段中,最小的开头值-1。
        比如在[2 1 4 5 6 7 3 4 1 2],
        g[2]=1-1=0,g[1]=1-1=0,g[4]=3-1=2,
        g[5]=4-1=3,g[6]=4-1=3,g[7]=4-1=3,g[3]=3-1=2
        dp[m]表示：在整个序列中，凑成[1,2,..m]需要的最少字段块数。
        转移方程：dp[m]=dp[g[m]]+1
        */
        vector<int>g(m+1,m+1),dp(m+1,m+1);
        int i=0,j=0;
        while(i<n){
            if(i!=0&&a[i]!=a[i-1]+1){
                j=i;
            }
            if(a[i]<=m){
                g[a[i]]=min(g[a[i]],a[j]-1);
            }
            i+=1;
        }
        dp[0]=0;
        for(int i=1;i<=m;i++){
            if(g[i]<=m){
                dp[i]=dp[g[i]]+1;
            }
        }
        if(dp[m]>m){
            cout<<"-1"<<endl;
        }else{
            cout<<dp[m]<<endl;
        }
        
    }
    return 0;
}

D

题意

给定n张牌，判断能否一直出顺子，直到牌出完为止。至少5张连续的牌才叫顺子。

题解

统计牌x的张数，记作a[x]。

对于牌x，它首先必须满足前4张牌的顺子要求。

例如，统计牌[1,2,3,4,5]的张数依次为：1 1 1 1 2 ，对于牌5，它必须拿1张出来与前面4张牌构成顺子，否则前面4张牌就不能构成顺子了。

再例如，统计牌[1,2,3,4,5,6,7]的张数依次为：1 1 2 2 2 1 1，对于牌5，它必须拿出1张来满足以牌1开头构成的顺子，以及拿出1张来满足以牌3开头构成的顺子。也就是，need[0]=1,need[1]=0,need[2]=1,need[3]=0。

除去2中必须拿出的张数，其余的张数还可以有两个作用：

尽可能承接之前牌数≥5的顺子。

例如，统计牌[1,2,3,4,5,6]的张数依次为：1 1 1 1 2 2。牌6拿出1张来满足牌5的need[3]需求，还剩1张牌可以继续承接牌[1,2,3,4,5]构成的顺子，使得成为[1,2,3,4,5,6]。

如果牌x还剩有张数的话，就不得不开始以牌x开头的新顺子了。

依次遍历所有牌，如果牌x不满足2中条件则退出输出NO。遍历完后再判断need[0]+need[1]+need[2]+need[3]是否等于0。

c++代码


#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
void solve(){
    int n;
    cin>>n;
    vector<int>a(n+1,0);//a[i]存储牌i的个数
    rep(i,n){
        int x;
        cin>>x;
        a[x]++;
    }
    vector<int>need(4,0);

    vector<int>dp(n+1,0);//dp[i]表示：牌i承接之前的牌数
    int flag=true;
    for(int i=1;i<=n;i++){//从牌1遍历到牌n
        int totalneed=need[0]+need[1]+need[2]+need[3];
        if(totalneed>a[i]){
            flag=false;
            break;
        }
        a[i]-=totalneed;
        dp[i]=need[0];
        if(a[i]>dp[i-1]){//承接dp[i-1]
            a[i]-=dp[i-1]; 
            dp[i]+=dp[i-1];
        }else{//a[i]全部承接
            dp[i]+=a[i]; 
            a[i]=0; 
        }    
//         cout<<dp[i-1]<<" "<<dp[i]<<endl;
        need[0]=need[1];
        need[1]=need[2];
        need[2]=need[3];
        need[3]=a[i];
//         cout<<i<<" "<<need[0]<<" "<<need[1]<<" "<<need[2]<<" "<<need[3]<<endl;
    }
    if(need[0]+need[1]+need[2]+need[3]!=0)
        flag=false;
    if(flag)
        cout<<"YES"<<endl;
    else
        cout<<"NO"<<endl;
    
}
int main(){
    int T;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}