牛客小白月赛92题解

A-获得木头_牛客小白月赛92 (nowcoder.com)

void solve()
{
    cin>>n;
    cout<<n*2*4<<endl;
}

B-采矿时间到！_牛客小白月赛92 (nowcoder.com)
思路：先把矿道两边的矿石挖走，在把里面的矿石挖走即可

void solve()
{
    cin>>n>>m;
    for(int i=1;i<=5;i++)
          for(int j=1;j<=n;j++)cin>>s[i][j];
    int res=0,ans=0;
    for(int i=1;i<=n;i++)
    {
        if(s[2][i]=='*')res++;
        if(s[4][i]=='*')res++;
    }
    if(res>=m)
    {
        cout<<min(res,m)<<endl;
        return;
    }
    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        if(s[2][i]=='*'&&s[1][i]=='*')cnt++;
        if(s[4][i]=='*'&&s[5][i]=='*')cnt++;
        if(s[2][i]=='#'&&s[1][i]=='*')ans++;
        if(s[4][i]=='#'&&s[5][i]=='*')ans++;
    }
    int t=m-res;
    if(t<=cnt)cout<<res+min(t,cnt)<<endl;
    else cout<<res+cnt+min(ans,(t-cnt)/2)<<endl;
}

C-耕种时间到！_牛客小白月赛92 (nowcoder.com)
思路：模拟，因为每次所有的种子都要操作所有种子的等级都会变成$\lfloor \frac{a_i}{3}\rfloor$所以只要看最大的$a_i$，发现最多模拟$lo{g}_{3}10^9$即可把所有情况枚举出来。

bool cmp(const pair<int, int> left,const pair<int,int> right){
	return left.x < right.x;
}

void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    cin>>x;
    map<int,int>mp;
    for(int i=1;i<=n;i++)
          mp[a[i]]++;
      auto t=max_element(mp.begin(),mp.end(),cmp);

    int res=max(0ll,mp[x]);
    for(int i=1;i<=40;i++)
    {
        map<int,int>cnt;
        for(auto x:mp)
            cnt[(x.first+2)/3]=cnt[(x.first+2)/3]+2*x.second;
   auto t=max_element(cnt.begin(),cnt.end(),cmp);
    if(t->first<x)break;
     res=max(res,cnt[x]);
        mp=cnt;
    }
    cout<<res<<endl;
}

D-探索的时光_牛客小白月赛92 (nowcoder.com)
思路：把题目给的公式$f(i)=(i-x{)}^2\ast a_i$拆开变成$f(i)=i^2\ast a_i+x^2\ast a_i-2\ast i\ast x\ast a_i$
然后就会变成${\sum }_{i=1}^{n}f(i)=x^2\ast {\sum }_{i=1}^n{a}_i+{\sum }_{i=1}^n{i}^2\ast a_i-2\ast x\ast {\sum }_{i=1}^{n}i\ast a_i$
然后对${\sum }_{i=1}^n{a}_i$,${\sum }_{i=1}^n{i}^2\ast a_i$,${\sum }_{i=1}^{n}i\ast a_i$预处理，之后只要枚举$x$的位置即可

void solve()
{
    cin>>n;
    int s=0,ss=0,tt=0;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        s+=a[i];
        ss+=i*i*a[i];
        tt+=2*i*a[i];
    }

    int res=0x3f3f3f3f3f3f3f3f;
    for(int i=1;i<=n;i++)
    {
        res=min(res,i*i*s+ss-i*tt);
    }
    cout<<res<<endl;
}