牛客小白月赛92（A-F)

A(简单数学） 乘一下，化简一下

#define x first   
#define y second 
using namespace std;
typedef long long LL;
typedef double D;
const int N = 2e5 + 10;
typedef pair<int, int> Pii;
void solved()
{
      int x;
    cin>>x;
    x=x*8;
    cout<<x;
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int t;
t=1;
  while (t--)
  {
  solved();
  }
  return 0;
}

B(暴力，贪心） 要求数量最多的，所以要节省体力，所以优先考虑只要花一点体力就能挖到的，然后再去考虑花俩点题里挖到的

#define x first   
#define y second 
using namespace std;
typedef long long LL;
typedef double D;
const int N = 2e5 + 10;
typedef pair<int, int> Pii;
char mp[6][N];
void solved()
{
     int n,h;
    cin>>n>>h;
    int ans=0;
    for(int i=1;i<=5;i++){
        for(int j=1;j<=n;j++){
            cin>>mp[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        if(mp[2][i]=='*'&&h)ans++,h--,mp[2][i]='.';
         if(mp[4][i]=='*'&&h)ans++,h--,mp[4][i]='.';
    }
    for(int i=1;i<=n;i++){
        if(mp[1][i]=='*'&&mp[2][i]=='.'&&h)ans++,h--,mp[1][i]='.';
        if(mp[5][i]=='*'&&mp[4][i]=='.'&&h)ans++,h--,mp[5][i]='.';
    }
    if(h<2){cout<<ans;return;}
    for(int i=1;i<=n;i++){
        if(mp[1][i]=='*'&&h>=2)ans++,h-=2;
         if(mp[5][i]=='*'&&h>=2)ans++,h-=2;
    }
        cout<<ans<<"\n";
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int t;
t=1;
  while (t--)
  {
  solved();
  }
  return 0;
}

C(模拟） 理解题意就知道。一直种一直种，直到所有的种子都比k小就不用管

#define int long long 
using namespace std;

typedef double D;
const int N = 2e5 + 10;
typedef pair<int, int> Pii;
map<int,int>mp;
int a[N];
void solved()
{
     int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        int x;cin>>x;
        mp[x]++;
    }
    int k;cin>>k;
    int ans;
    if(mp.count(k))ans=mp[k];
    else ans=0;
    while(mp.size()>0){
        map<int,int>tp;
        for(auto [x,y]:mp){
            int xx=x+2;
            int tt=xx/3;
            if(tt>=k)tp[tt]+=y*2;
        }
        mp.clear();
        if(tp.count(k))ans=max(ans,tp[k]);
        mp=tp;
    }
    cout<<ans<<"\n";
    
}
signed main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int t;
 t=1;
  while (t--)
  {
  solved();
  }
  return 0;
}

D（数学，化简） 把x当成定值，然后化简，发现好多的东西都是定值，只有x属于1~n是变的,然后随便谢谢就过了，注意求完对称轴之后的的精度问题，都讨论一下，最多+-1

#define x first   
#define int long long 
using namespace std;
 
typedef double D;
const int N = 2e5 + 10;
typedef pair<int, int> Pii;
int a[N];
int pre[N],hou[N];
void solved()
{   int n;
    cin>>n; 
     int sum=0;
     int aa=0,bb=0;
    for(int i=1;i<=n;i++)cin>>a[i],sum+=(i*i)*a[i],aa+=a[i],bb+=i*a[i];
    int k=bb/aa;
 
    if(k==0){k=1;cout<<k*k*aa+sum-2*k*bb;return;}
    int tp=k*k*aa+sum-2*k*bb;
    int ans=tp;
    if(k>1){
        k-=1;
        tp=k*k*aa+sum-2*k*bb;
        ans=min(ans,tp);
        k+=1;
    }
    if(k<n){
        k+=1;
        tp=k*k*aa+sum-2*k*bb;
        ans=min(ans,tp);
    }
    cout<<ans<<"\n";
     
    
 
}
signed main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int t;
 t=1;
  while (t--)
  {
  solved();
  }
  return 0;
}

E(dp，状态机) 赛时的时候因为题目看错gg了，以为变成暗物质之后燃烧的时间不变，燃烧物质倍增.......

通过mn<1e6很容易得到状态定义是dp[i][j]，标识前i个煤矿融化j个铁矿所需要的时间，但是因为题目,还有1次机

会变成暗物质，那么这个就很显然是个三维dp[i][j][k],表示前i个煤矿融化j个铁矿，用了一次机会，和没有用那一

次机会，然后自己转移，不开longlong会gg

#define x first   
#define int long long 
using namespace std;
typedef double D;
const int N = 2e5 + 10;
typedef pair<int, int> Pii;
const int inf=1e9;
int a[N],b[N];

void solved()
{
  int n,m;
  cin>>n>>m;
  for(int i=1;i<=n;i++){
     cin>>b[i]>>a[i];
  }
  
  vector<vector<vector<int>>>dp(n+1,vector<vector<int>>(m+1,vector<int>(2,inf)));
 dp[0][0][0]=0,dp[0][0][1]=0;
 for(int i=1;i<=n;i++)dp[i][0][0]=0,dp[i][0][1]=0;
  for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
       dp[i][j][0]=dp[i-1][j][0];
       dp[i][j][1]=dp[i-1][j][1];
       dp[i][j][0]=min(dp[i][j][0],dp[i-1][max((int)0,j-b[i])][0]+a[i]);
      dp[i][j][1]=min(dp[i-1][max(j-2*b[i],(int)0)][0]+a[i]/2,dp[i][j][1]);
      dp[i][j][1]=min(dp[i-1][max((int)0,j-b[i])][1]+a[i],dp[i][j][1]);
  }
    
  }
  
  cout<<min(dp[n][m][0],dp[n][m][1]);    

}
signed main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int t;
  t=1;
  while (t--)
  {
  solved();
  }
  return 0;
}

F(思维） 对于整个草皮的移动，由于w的2范围非常大，如果直接这么模拟肯定会g，那么我们抓住这俩个小的n,m,所以就可以这对每个草坪，第i只羊在第j块草皮的的d的范围是可以求出来的，所有就我们就可以枚举每只羊在这个范围内的贡献，然后通过差分解决，代码有注释

#define int long long 
using namespace std;

typedef double D;
const int N = 2e5 + 10;
typedef pair<int, int> Pii;

int n,m;
int w[N],v[N];
int p[N];
map<int,int>mp;
void solved()
{
     cin>>n>>m;
    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>>p[i];
    //第i块草皮区域为wi-1 + 1....wi
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            //第i只羊在第j块草皮的
            //w(j-1)+1<=x+d<=wj
            //        wj-1 +1-h<=d<=wj-x
            //就是当d在这个区域时候对这一段的时候dii只羊的贡献都为vj
            //通过差分mp维护，然后枚举每一个值d
            mp[w[j-1]+1-p[i]]+=v[j];
            mp[w[j]-p[i]+1]-=v[j];
        }
    }

    int sum=0;
    set<int>st;
    st.insert(sum);

    for(auto [x,y]:mp){
        sum+=y;
        st.insert(sum);
    }

    cout<<st.size();
}
signed main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int t;
 t=1;
  while (t--)
  {
  solved();
  }
  return 0;
}