牛客小白月赛92 题解

A. 获得木头 签到

\((x\times4)/2\times 4 = x \times 8\)

#include<bits/stdc++.h>

using namespace std;

#define ff first
#define ss second
#define pb push_back
#define all(u) u.begin(), u.end()
#define endl '\n'
#define debug(x) cout<<#x<<":"<<x<<endl;

typedef pair<int, int> PII;
typedef long long LL;
const int inf = 0x3f3f3f3f;
const int N = 1e5 + 10, M = 105;
const int mod = 1e9 + 7;
const int cases = 0;

void Showball(){
  int x;
  cin>>x;
  cout<<x*8<<endl;    
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T=1;
    if(cases) cin>>T;
    while(T--)
    Showball();
    return 0;
}

B.采矿时间到！签到

优先拿能够消耗1体力的矿石，接着拿与之前拿过的矿石相连的矿石，这样也消耗1体力，最后再拿剩下的矿石，消耗2体力。

void Showball(){
   int n,h;
   cin>>n>>h;
   vector<string> s(5);
   for(int i=0;i<5;i++) cin>>s[i];
   int cnt=0,cnt2=0;
   for(int i=0;i<n;i++){
      if(s[0][i]=='*'){
        if(s[1][i]=='*') cnt+=2;
        else cnt2++;
      }else if(s[1][i]=='*') cnt++;

      if(s[4][i]=='*'){
        if(s[3][i]=='*') cnt+=2;
        else cnt2++;
      }else if(s[3][i]=='*') cnt++;
   }
   int ans=min(h,cnt)+min(max(h-cnt,0)/2,cnt2);
   cout<<ans<<endl;
}

C.耕种时间到！模拟

用\(pair\) 保存等级和数量，直接枚举，更新答案即可。

void Showball(){
  int n;
  cin>>n;
  vector<PII> a(n);   
  for(int i=0;i<n;i++){
    int x;
    cin>>x;
    a[i]={x,1};
  }
  int x;
  cin>>x;
  LL ans=0;
  LL maxn=(*max_element(all(a))).ff;
  while(maxn>=x){
    LL tmp=0;
    for(int i=0;i<n;i++){
       if(a[i].ff==x) tmp+=a[i].ss; 
    }
    for(int i=0;i<n;i++) a[i]={(a[i].ff+2)/3,a[i].ss*2};
    maxn=(maxn+2)/3;
    ans=max(ans,tmp);
  }
    cout<<ans<<endl;
}

D. 探索的时光 思维

题意：给你一个数组，请你找一个 \(x (1\le x \le n)\) 满足 \(\sum_{i=1}^n (x-i)^2*a_i\) 的值最小。

思路：展开式子

原式\(=\sum_{i=1}^n (x^2-2*x*i+i^2)*a_i\)

​ \(=\sum_{i=1}^n (x^2*a_i-2*x*i*a_i+i^2*a_i)\)

因为 \(x\) 与 \(i\) 无关，所以可以拿出来。

原式 \(=x^2*\sum_{i=1}^na_i-2*x*\sum_{i=1}^n i*a_i+\sum_{i=1}^ni^2*a_i\)

那么我们发现除了 \(x\) , 其他部分都是一个常数，那么原式就是一个关于 \(x\) 的二次函数。

可以通过对称轴求解，当然数据范围很小，也可以直接枚举求解即可。

void Showball(){
   int n;
   cin>>n;
   LL a1=0,a2=0,a3=0;
   for(int i=1;i<=n;i++){
     LL x;
     cin>>x;
     a1+=x;
     a2+=i*x;
     a3+=1LL*i*i*x;
   }      
   LL ans=1e18;
   for(int i=1;i<=n;i++){
     ans=min(ans,1LL*i*i*a1-2LL*i*a2+a3);
   }
   cout<<ans<<endl;
}

E. 来硬的 DP

题意：给你 \(n\) 中煤炭，第 \(i\) 块煤炭燃烧 \(y_i\) 秒能够融化至多 \(x_i\) 单位的铁矿石。你有一次使用魔法的机会，可以选择一块煤炭使其燃烧 \(y_i/2\) 秒能够融化至多 \(2x_i\) 单位的铁矿石。 求出烧炼 \(m\) 单位铁矿石至少需要多少时间。

其中 \(1 \le n*m \le 1e6\) 。

思路：不妨定义\(f_{i,j,0/1}\) 表示前 \(i\) 块煤炭烧炼 \(j\) 单位铁矿石 不使用魔法/使用魔法 的最短时间。

考虑这个状态从哪个状态过来不容易，不妨考虑这个状态可以转移到哪个状态。

那么如果不使用魔法，显然 \(i,j\) 这个状态可以转移到 \(i+1,j+x_{i+1}\)这个状态。并且会花费 \(y_{i+1}\) 的时间

使用了魔法，显然 \(i,j\) 这个状态可以转移到 \(i+1,j+2*x_{i+1}\)这个状态。并且会花费 \(y_{i+1}/2\) 的时间

我们只需要考虑烧炼 \(m\) 单位即可，因此需要和 \(m\) 取个min。具体转移参考代码。

void Showball(){
   LL n,m;
   cin>>n>>m;
   vector<LL> x(n+1),y(n+1);
   for(int i=1;i<=n;i++) cin>>x[i]>>y[i];
   vector<vector<array<LL,2>>> f(n+1,vector<array<LL,2>>(m+1,{inf,inf}));  
   //f[i][j][0/1]表示考虑前i块煤炭烧炼j单位铁矿石 不使用/使用 魔法的 最短时间
   f[0][0][0]=0;
   for(int i=1;i<=n;i++){
    for(int j=0;j<=m;j++){
        f[i][j][0]=min(f[i][j][0],f[i-1][j][0]);
        f[i][j][1]=min(f[i][j][1],f[i-1][j][1]);
        f[i][min(m,j+x[i])][0]=min(f[i][min(m,j+x[i])][0],f[i-1][j][0]+y[i]);
        f[i][min(m,j+x[i])][1]=min(f[i][min(m,j+x[i])][1],f[i-1][j][1]+y[i]);
        f[i][min(m,j+2LL*x[i])][1]=min(f[i][min(m,j+2LL*x[i])][1],f[i-1][j][0]+y[i]/2);
    }
   }
   LL ans=inf;
   for(int i=1;i<=n;i++){
     ans=min(ans,min(f[i][m][0],f[i][m][1]));
   }   
   cout<<ans<<endl;
}

F. 快快乐乐剪羊毛 思维 差分

题意：给你 \(n\) 块草皮，每块草皮的宽度为 \(w_i\)，依次连接在一起。每块草皮有一个营养价值 \(v_i\)。现在有 \(m\) 只绵羊，他们的坐标分别为 \(x_i\)。绵羊在对应的草皮上就可以获得对应草皮的营养价值。现在你可以水平向左或者向右平移所有的草皮，求出营养价值之和有多少种不同的取值。

其中 \(1\le n*m \le 1e5\)。

思路：直接计算不容易，我们考虑去算每只羊对于草皮的贡献，我们不妨设草皮偏移量为 \(d\)，为了方便我们求出每段草皮的覆盖区间，我们可以对 \(w\) 数组前缀和处理即可。这样第 \(j\) 块草皮的覆盖区间就是 \([w_{j-1}+1,w_j]\)。

那么显然如果第 \(i\) 只绵羊的位置 \(x_i\) 满足 \(w_{j-1}+1 \le x_i+d \le w_j\) 时，就会产生 \(v_j\) 的贡献。

化简一下式子：\(w_{j-1}+1 -x_i \le d \le w_j -x_i\) 。

也就是说，只要偏移量符合这个区间，那么第 \(i\) 只绵羊就会产生 \(v_j\) 的贡献。

也就是对这个区间整体加上 \(v_j\)。这样我们就可以用差分进行维护。

考虑使用 \(map\)嵌套 \(vector\) 来存储。枚举所有的情况后，求前缀和然后放进 \(set\) 求种类即可。

代码非常好写，很好的思维题。

void Showball(){
  int n,m;
  cin>>n>>m;
  vector<LL> w(n+1),v(n+1),x(m+1);
  for(int i=1;i<=n;i++){
    cin>>w[i];
    w[i]+=w[i-1];
  }
  for(int i=1;i<=n;i++) cin>>v[i];
  for(int i=1;i<=m;i++) cin>>x[i];
  map<LL,vector<LL>> mp;
  for(int i=1;i<=m;i++){
    for(int j=1;j<=n;j++){
        mp[w[j-1]+1-x[i]].pb(v[j]);
        mp[w[j]-x[i]+1].pb(-v[j]);
    }
  }

  LL cur=0;
  set<LL> st;
  for(auto [k,v]: mp){
    for(auto it:v) cur+=it;
    st.insert(cur);
  }
  cout<<st.size()<<endl;
}