牛客月赛47题解（补题）

提示：排版狗屎，前排提醒

文章目录

• 一、牛牛的装球游戏
• • 1.题目
  • 2.思路
  • 3.代码
  • 4.拓展
• 二、牛牛的数字集合
• • 1.题目
  • 2.思路
  • 3.代码
• 三、小猫排队
• • 1.题目
  • 2.思路
  • 3.代码
  • 4.拓展（简单数据结构解法）
• 四.造桥
• • 1.题目
  • 2.思路
  • 3.代码
• 总结

---

一、牛牛的装球游戏 1.题目

2.思路

简单模拟题
因为球的半径与圆柱的半径时相同的，所以只用考虑高度就好了
至于保留三位小数，可以直接使用setpreclass="superseo">cision()
属于签到题，直接看代码

3.代码

void solve(){
    cout<<setiosflags(ios::fixed)<<setprecision(3);
    long double r,h;
    int num;//能容纳的最大数量
    scanf("%lld", &n);
    long double ans[n];
    for(int i=0;i<n;i++){
        r=0;
        h=0;
        cin>>r>>h;
        num=h/2/r;
        ans[i]=r*pi*r*h-num*pi*r*r*r*4/3;
    }
    for(int i=0;i<n;i++){
        cout<<ans[i]<<endl;
    }
}

4.拓展

因为这题给出了PI的取值，所以我们可以直接用
但如果题目没给的话，我们可以通过
const double pi=acos(-1.0);

二、牛牛的数字集合 1.题目

2.思路

这里是可以通过数学证明出来划分一个集合的时候，值最小.
因为当我们划分成m(m>1)个组合时，我们记最大的那一组为max
然后我们可以很清楚地看出max^(m-1)肯定比剩下的几组大
（不理解的话可以举例子自己理解下）
所以只能划分成1个集合最小

3.代码

int n;
int div=1e9+7;

void solve(){
    long long ans=1,t;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>t;
        ans=ans*t%div;
    }
    cout<<ans<<endl;
}

三、小猫排队 1.题目

2.思路

基本模拟题：模拟小猫的移动过程
但如果直接模拟的话，时间复杂度有o(n^2)
所以我们通过对题目分析可以看到小猫不会后移，且与最前面的一个是不断递减
即可以当作左指针也在移动
所以我们可以考虑用双指针模型
注意：答案可以为n+1

3.代码

int n,cute;
int a[N],p[N];
void solve(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    cin>>cute
    int pre=0;
    for(int i=0;i<n;i++){
        p[i]=pre;
        if(a[i]>cute){
            pre=i;
        }
    }
    int l=0,r=n;
    while(l < r) {
        if(p[r]>= l) r = p[r];
        //先交换后出队，所以这里可以等于
        if(l == r) break;
        l++;
    }
    l++;
    cout<<l;
}

4.拓展（简单数据结构解法）

用栈和队列都可以，无所谓
这里用栈来写

int n,cute,ans=0;
int a[200009];
void solve(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    cin>>cute;
    stack<int> st;
    for(int i=1;i<=n;i++){
        if(a[i]>cute) st.push(i);
    }
    int l=1,r=n+1;
    do{
        if(!st.empty()&&st.top()>=l){
            r=st.top();
            st.pop();
        }
        l++;
        ans++;
    }while(l<=r);
    cout<<ans<<endl;
}

四.造桥 1.题目

2.思路

一眼dp
然后公式dp[s.back()-‘a’]=max(dp[s.back()-‘a’],dp[s[0]+len])
len为字符串长度

3.代码

signed main(){
    cin>>k>>n;
    int ans[26],res;
    for(int j=0;j<k;j++){
        memset(ans,0,sizeof(ans));
        //记得清零
        for(int i=0;i<n;i++){
            string temp;
            cin>>temp;
            int len=temp.length();
            int End=temp[len-1]-'a';
            int Beg=temp[0]-'a';
            ans[End]=max(ans[End],ans[Beg]+len);
        }
        for(int i=0;i<26;i++){
            res=max(res,ans[i]);
        }
        cout<<res<<endl;
    }
    return 0;
}

总结

晚上继续