题解 | #牛客小白月赛 1 #

补完一套月赛，此图为证

补完一套月赛

说明

题目链接
这套题其实没有特别难的，唯二两道难题是G和I。 G题是一道简单dp，式子很简单，难的地方在于怎么把图形存在数组里，而且还能利用这个数组动态规划。 I题是一道结论题，可能对科班出身的比较友好，考察的是出栈序列有多少种，如果知道卡特兰数，并且看出最想去的目的地不能首选的本质，就能秒杀此题。

A 简单题

知道e就是exp(1)，而且设置高位精度直接用C++的setprecision。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int T;cin>>T;
    while(T--){
        int a,b,y;
        cin>>a>>b>>y;
        cout<<fixed<<setprecision(y)<<b*exp(a)<<endl;
    }
    return 0;
}

B 简单题2

简化一下式子，注意式子精度要够。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int T;cin>>T;
    while(T--){
        int b,d,y;
        cin>>b>>d>>y;
        cout<<fixed<<setprecision(y)<<exp(exp(1)*log(b))/d<<endl;
    }
    return 0;
}

C 分元宵

注意快速幂里面的幂次不能取模，只能是底数取模，因为幂次取模是没有意义的。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll ksm(ll a, ll b, ll m){
    ll ans=1;
    while(b){
        if(b&1)ans=ans*a%m;
        a=(a%m)*(a%m)%m;
        b=b>>1;
    }
    return ans;
}
int main(){
    ll a,b,c,d,mod;
    cin>>a>>b>>c>>d>>mod;
    ll p=c*d;
    ll q=(a%mod)*(b%mod)%mod;
    ll ans=ksm(q,p,mod);
    if(a==0||b==0||c==0||d==0)ans=0;
    cout<<ans<<endl;
    return 0;
}

D 多项式乘法

看出来结构体排序，一遍过。

#include<bits/stdc++.h>
using namespace std;
struct node{
    int cishu;
    int xishu;
    bool friend operator < (const node &A, const node &B){
        return A.cishu<B.cishu;
    }
}F[505],L[505],ans[505*505];
int shuchu[505*505];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=0;i<=n;i++){
        int x;cin>>x;
        F[i].cishu=i,F[i].xishu=x;
    }
    for(int i=0;i<=m;i++){
        int x;cin>>x;
        L[i].cishu=i,L[i].xishu=x;
    }
    int cnt=0;
    for(int i=0;i<=n;i++){
        for(int j=0;j<=m;j++){
            ans[cnt].cishu=F[i].cishu+L[j].cishu;
            ans[cnt++].xishu=F[i].xishu*L[j].xishu;
        }
    }
    sort(ans,ans+cnt);
    //for(int i=0;i<cnt;i++)cout<<ans[i].xishu<<" ";
    int num=0,now=0;
    for(int i=0;i<cnt-1;i++){
        now+=ans[i].xishu;
        if(ans[i].cishu!=ans[i+1].cishu){
            shuchu[num]+=now;
            num++;
            now=0;
        }
    }
    if(ans[cnt-2].cishu!=ans[cnt-1].cishu)shuchu[num++]=ans[cnt-1].xishu;
    else shuchu[num]+=ans[cnt-1].xishu,num++;
    for(int i=0;i<num;i++){
        cout<<shuchu[i]<<" ";
    }
    return 0;
}

E 圆与三角形

输出流加fixed，就是四舍五入；不加fixed，就是保留几位小数。

#include<bits/stdc++.h>
using namespace std;
int main(){
    double r;
    cin>>r;
    cout<<fixed<<setprecision(2)<<r+1<<endl;
    return 0;
}

F 三视图

关键是怎么存坐标。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e3+5;
char fr[maxn][maxn],le[maxn][maxn],to[maxn][maxn];
int main(){
    int X,Y,Z,n;
    cin>>X>>Y>>Z>>n;
    for(int i=Y;i>=1;i--){
        for(int j=1;j<=X;j++){
            fr[j][i]='.';
        }
        for(int j=1;j<=Z;j++){
            le[j][i]='.';
        }
    }
    for(int i=1;i<=Z;i++){
        for(int j=1;j<=X;j++){
            to[i][j]='.';
        }
    }
    for(int i=1;i<=n;i++){
        int x,y,z;
        cin>>x>>y>>z;
        //for(int j=1;j<=y;j++)fr[x][j]='x';
        //for(int j=1;j<=y;j++)le[z][j]='x';
        fr[x][y]='x';
        le[z][y]='x';
        to[z][x]='x';
    }
    for(int i=Y;i>=1;i--){
        for(int j=1;j<=X;j++)cout<<fr[j][i];
        cout<<" ";
        for(int j=1;j<=Z;j++)cout<<le[j][i];
        cout<<endl;
    }
    cout<<endl;
    for(int i=1;i<=Z;i++){
        for(int j=1;j<=X;j++){
            cout<<to[i][j];
        }
        cout<<endl;
    }
    return 0;
}

G あなたの蛙は旅⽴っています

把六边形图压缩成正方形。压缩的过程纯模拟，一点一点写可以写出来，我用了一个多小时才写对。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 805;
int h[2*maxn][2*maxn];
int dp[2*maxn][2*maxn];
int main(){
    memset(h,0,sizeof(h));
    memset(dp,0,sizeof(dp));
    int n;cin>>n;
    int l=2*n-1;
    for(int i=1;i<=n;i++){
        for(int j=i;j>=1;j--)cin>>h[j][i-j+1];
    }
    for(int i=n+1,k=n+1;i<=3*n-2;i+=2,k++){
        for(int j=k-1;j>k-n;j--)cin>>h[j][i-j+1];
        for(int j=k;j>k-n;j--)cin>>h[j][i-j+2];
    }
    for(int i=1;i<=n-1;i++){
        for(int j=l;j>l-n+i;j--)cin>>h[j][n+i+l-j];
    }
    /*
    for(int i=1;i<=l;i++){
        for(int j=1;j<=l;j++){
            cout<<h[i][j]<<" ";
        }
        cout<<endl;
    }
    */
    for(int i=1;i<=l;i++){
        dp[i][1]=dp[i-1][1]+h[i][1];
        dp[1][i]=dp[1][i-1]+h[1][i];
    }
    for(int i=2;i<=l;i++){
        for(int j=2;j<=l;j++){
            dp[i][j]=max(dp[i-1][j-1],max(dp[i-1][j],dp[i][j-1]))+h[i][j];
        }
    }
    cout<<dp[l][l]<<endl;
    return 0;
}

H 写真がとどいています

没学过五线谱的做这个题极不友好，实际上只需要看出高低音循环。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 5005;
char a[10][maxn];
int main(){
    int N;
    cin>>N;
    for(int i=1;i<=9;i++){
        for(int j=1;j<=N;j++){
            scanf(" %c",&a[i][j]);
        }
    }
    /*
    for(int i=1;i<=9;i++){
        for(int j=1;j<=N;j++){
            printf("%c",a[i][j]);
        }
        cout<<endl;
    }
    */
    for(int i=1;i<=N;i++){
        bool f=false;
        for(int j=1;j<=9;j++){
            if(a[j][i]=='o'){
                switch(10-j){
                    case 1:cout<<"E";break;
                    case 2:cout<<"F";break;
                    case 3:cout<<"G";break;
                    case 4:cout<<"A";break;
                    case 5:cout<<"B";break;
                    case 6:cout<<"C";break;
                    case 7:cout<<"D";break;
                    case 8:cout<<"E";break;
                    case 9:cout<<"F";break;
                    default:break;
                }
                f=true;
            }
            else if(a[j][i]=='|'){
                cout<<"|";
                f=true;
                break;
            }
        }
        if(f==false)cout<<" ";
    }
    return 0;
}

I あなたの蛙が帰っています

逆向思维。一个长度为n的入栈序列的合法出栈序列数就是卡特兰数。如果第一个出栈的是A，那么合法出栈序列数就是长度为n-1时的卡特兰数。那么第一个出栈的不能是A的合法出栈序列数，就是长度为n时的卡特兰数-长度是n-1时的卡特兰数。卡特兰数： $Catalan(n)=\frac{1}{n+1}\dbinom{2n}{n}$

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 998244353;
const ll maxn = 1e5+5;
ll jc[2*maxn];
void get_jc(){
    jc[0]=jc[1]=1;
    for(ll i=2;i<=2e5;i++){
        jc[i]=(jc[i-1]%mod)*i%mod;
    }
}
ll ksm(ll a, ll b, ll mod){
    ll ans=1;
    while(b){
        if(b&1)ans=ans*a%mod;
        a=a*a%mod;
        b=b>>1;
    }
    return ans;
}
ll inv(ll a, ll mod){
    return ksm(a,mod-2,mod);
}
ll catalan(ll n){
    return (((jc[2*n]%mod)*inv(jc[n+1],mod))%mod)*inv(jc[n],mod)%mod;
}
int main(){
    get_jc();
    ll t;cin>>t;
    for(int i=1;i<=t;i++){
        ll n;cin>>n;
        ll ans=((catalan(n)%mod)+mod-(catalan(n-1)%mod))%mod;
        cout<<"Case #"<<i<<": "<<ans%mod<<endl;
    }
    return 0;
}

J おみやげをまらいました

开一个map映射。

#include<bits/stdc++.h>
using namespace std;
map<string,string> mp;
int main(){
    string s1,s2;
    for(int i=1;i<=3;i++){
        cin>>s1>>s2;
        mp[s2]=s1;
    }
    int N;cin>>N;
    for(int i=1;i<=N;i++){
        string s;cin>>s;
        if(mp[s]=="")puts("Fake");
        else{
            string ans=mp[s];
            cout<<ans<<endl;
        }
    }
    return 0;
}