牛客小白月赛81 全部题解

A.小辰打比赛

读题

我们肯定优先按照最小的来pk,所以直接排序就好

void solve()
{
    cin>>n>>m;
    vector<int> w(n);
    for(auto&v:w) cin>>v;
    sort(w.begin(),w.end());
    int cnt=0;
    for(auto&v:w){
        if(m>v){
            cnt+=v;
        }
        else break;
    }
    cout<<cnt<<endl;
    return ;
}

B.小辰的圣剑

暴力枚举 && 细节*

1.注意到数据范围很小我们直接在两个循环里面做处理即可

2.倘若使用前缀和可能会导致[l,r]最后的声望<=u但是[l,mid]在中间过程中会出现大于u的情况,对于这种情况可以固定左端点枚举右端点然后做个最大值的处理

2的处理如下

for(int i=1;i<=n;i++){
        cin>>b[i];
        b[i]+=b[i-1];
    }
    for(int j=1;j<=n;j++)
        for(int i=1;i<=j;i++)
            s[i][j]=max(s[i][j-1],b[j]-b[i-1]);
        

简单写法

void solve()
{
    cin>>n>>m>>u;
    vector<int> a(n),b(n);
    for(auto&v:a) cin>>v;
    for(auto&v:b) cin>>v;
    int ans=0;
    for(int i=0;i<n;i++){
        int cnt=0,x=0,y=0;
        for(int j=i;j<n;j++){
              x+=a[j];
              y+=b[j];
              if(x>m || y>u) break;
              cnt++;
        }
        ans=max(ans,cnt);
    }
         
    cout<<ans<<endl;
    return ;
}

C.陶陶学算术

分解质因数

首先注意到数据范围数1e5每一个数也是1e5,直接按照乘法和除法进行明显会出现下去整或者爆数的问题(1e5个1e5做乘除) 所以我们考虑如何简单化,我们思考一下最后答案要一样表示这两个式子有什么特征是一样的?每次乘除的贡献是什么,由此我们可以发现 同时在1e5的数据范围下我们考虑每一个数的贡献变为每一个数拆分为质因数这样就可以一起来计算他们的贡献了

void solve()
{
    vector<int> a(N),b(N);
    int cnt=0;
    auto get = [&](vector<int>&a,int now){// 重复处理使用函数来解决
        cin>>n;
        while(n--){
            int op,x; cin>>op>>x;
            if(x<0) cnt+=now,x=-x;
            int ok = op==1 ? 1: -1;
            for(int i=2;i<=x/i;i++){
                while(x%i==0){
                    a[i]+=ok;
                    x/=i;
                }
            }
            if(x>1) a[x]+=ok;
        }
    };
    get(a,1);
    get(b,-1);
    cout<<(a==b && cnt%2==0 ? "YES" : "NO")<<endl;
    return ;
}

D.小辰的借钱计划

数学期望

我要是不换我的数学期望就是本身这个数,我要是交换的就是其他每一个数乘以他们出现的概率,也可以做一个简单转化就是a*出现的数的数量和他们的总和比较

void solve()
{
    cin>>m>>a;
    int sum=0,cnt=0;
    for(int i=1;i<=m-a;i++){
        if(i%a==0 || a%i==0){
            sum+=i;
            cnt++;
        }
    }
    cout<<(sum > cnt*a ? "YES" : "NO")<<endl;
    return ;
}

E.小辰的智慧树

推式子和差分

考虑对于这个式子我们进行变形可以得到-(x-h)^2+h^2但是我们发现并没什么作用,因为我们不能看一个带来的影响而是看每一个树应该砍多少如何分配,当独这也是没有头绪的我们不妨思考一下砍树的性质,我们会发现如果把一个数分开成为2个数不同的来砍带来的贡献是一样的

所以我们对于每个位置一个一个的砍由此我们可以用差分来求出每一个位置的数量

对于这道题我们并没有什么算法可以解决我们数据范围也是1e6我们发现似乎给定的是一个左右边界-->考虑简单的算法差分

int w[N];
 
void solve()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int l,r; cin>>r>>l;
        w[l+1]++,w[r+1]--;
    }    
    for(int i=1;i<N;i++) w[i]+=w[i-1];
     
    int ans=0;
    for(int i=N-1;i>=0;i--){
        int now=min(m,w[i]);
        m-=now;
        ans+=now*(2*i-1);
    }
    cout<<ans<<endl;
    return ;
}

F.小辰刚学 gcd

gcd的特性和区间的继承性质

我们可以发现一个区间内[l,r]中固定右边即题目意思数量不会多于32,这是因为一个数于另一个数的gcd一定是这个数的本身或者是小于等于这个数的一半,由此我们可以推出每一个位置为[1,pos]的答案数量不会多余32,我们把这个贡献记录在pos这个位置我们看一下pos+1和pos的关系可以发现只要是具有传承的性质的,对于pos的gcd数需要进行于我pos+1位置这个数进行gcd,注意每个数的位置更新就好

vector<PII> g[N];
 
void solve()
{
    cin>>n>>m;
    vector<int> a(n+5);
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
     
    unordered_map<int,int> mp;
     
    for(int i=1;i<=n;i++){
        g[i].push_back({a[i],i});
        mp[a[i]]=i;
        for(auto&[x,id]:g[i-1]){
            int v=__gcd(x,a[i]);
            if(!mp.count(v) || mp[v]!=i){// 在前面或者是没有出现过是新的
                mp[v]=i;// 向后走
                g[i].push_back({v,id});
            }
        }
    }
     
    while(m--){
        int l,r; cin>>l>>r;
        int cnt=0;
        for(auto&[x,id]:g[r]){
            if(id>=l) cnt++;
        }
        cout<<cnt<<endl;
    }
    return ;
}