牛客小白月赛 30 题解

A题：
因为牛牛特别讨厌白边，所以先把黑边全部加入图中，用并查集判断是否连通，如果不联通，就再用kruskal求最小生成树的思想尝试加边，加到最后如果还是不联通，就说明无解，输出-1。
代码如下：

#include<bits/stdc++.h>
using namespace std;
int x[200010],y[200010],z[200010],fa[200010];
int get(int x){
    if(x==fa[x])return x;
    return fa[x]=get(fa[x]);
}
int main(){
    int n,m,ans=0;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        fa[i]=i;
    for(int i=1;i<=m;i++){
        cin>>x[i]>>y[i]>>z[i];
        if(z[i]==0){
            int xx=get(x[i]),yy=get(y[i]);
            if(xx!=yy)fa[xx]=yy;
        }
    }
    for(int i=1;i<=m;i++){
        if(z[i]==1){
            int xx=get(x[i]),yy=get(y[i]);
            if(xx!=yy){
                ans++;
                fa[xx]=yy;
            }
        }
    }
    for(int i=1;i<=n;i++)
        fa[i]=get(fa[i]);
    sort(fa+1,fa+n+1);
    for(int i=2;i<=n;i++)
        if(fa[i]!=fa[i-1]){
            cout<<-1<<"\n";
            return 0;
        }
    cout<<ans<<"\n";
    return 0;
}

时间复杂度 O(m log m)

B题：
看到单点修改，区间处理的题目果断往线段树和树状数组的方向思考，这里提供线段树的方法。
线段树多维护最大值个数的信息。
在建树和修改函数中，通过比较该节点左子树和右子树的最大值大小，决定当前子树的最大值个数的值。
显然，当左子树的最大值大于右子树的最大值时，当前子树的最大值个数即为左子树的最大值个数；当左子树的最大值等于右子树的最大值时，当前子树的最大值个数即为左子树的最大值个数加上右子树的最大值个数；当左子树的最大值小于右子树的最大值时，当前子树的最大值个数即为右子树的最大值个数。
在查询函数中，返回一个pair类型，first即为最大值，second即为最大值个数，与建树和修改函数更新最大值个数的方法类似，这里留给读者思考。
代码如下：

#include<bits/stdc++.h>
using namespace std;
struct ljy{
    int l,r,s,ss;
}f[800010];
int a[200010];
typedef pair<int,int>PII;
inline void build(int l,int r,int p){
    f[p].l=l;f[p].r=r;
    if(f[p].l==f[p].r){
        f[p].s=a[l];
        f[p].ss=1;
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,p<<1);
    build(mid+1,r,(p<<1)+1);
    f[p].s=max(f[p<<1].s,f[(p<<1)+1].s);
    if(f[p<<1].s>=f[(p<<1)+1].s)f[p].ss+=f[p<<1].ss;
    if(f[p<<1].s<=f[(p<<1)+1].s)f[p].ss+=f[(p<<1)+1].ss;
    return;
}
inline void change(int x,int y,int p){
    if(f[p].l==f[p].r){
        f[p].s=y;
        return;
    }
    int mid=(f[p].l+f[p].r)>>1;
    if(x<=mid)change(x,y,p<<1);
    if(x>mid)change(x,y,(p<<1)+1);
    f[p].s=max(f[p<<1].s,f[(p<<1)+1].s);
    f[p].ss=0;
    if(f[p<<1].s>=f[(p<<1)+1].s)f[p].ss+=f[p<<1].ss;
    if(f[p<<1].s<=f[(p<<1)+1].s)f[p].ss+=f[(p<<1)+1].ss;
}
inline PII ask(int l,int r,int p){
    if(l<=f[p].l&&f[p].r<=r)return make_pair(f[p].s,f[p].ss);
    int mid=(f[p].l+f[p].r)>>1,s=0,ss=0;
    if(l<=mid){
        PII nxt=ask(l,r,p<<1);
        s=nxt.first;
        ss=ss+nxt.second;
    }
    if(r>mid){
        PII nxt=ask(l,r,(p<<1)+1);
        if(nxt.first==s)ss=ss+nxt.second;
        if(nxt.first>s){
            s=nxt.first;
            ss=nxt.second;
        }
    }
    return make_pair(s,ss);
}
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    build(1,n,1);
    for(int i=1;i<=m;i++){
        string str;
        cin>>str;
        if(str=="Change"){
            int x,y;
            cin>>x>>y;
            change(x,y,1);
        }
        else{
            int l,r;
            cin>>l>>r;
            PII nxt=ask(l,r,1);
            cout<<nxt.first<<" "<<nxt.second<<"\n";
        }
    }
    return 0;
}

时间复杂度 O((m+n) log n)

C题：
贪心易得，最优方案为三级，一级依次跳。所以根据n%4的余数分类处理即可。
代码如下：

#include<bits/stdc++.h>
using namespace std;
int main(){
    long long n;
    cin>>n;
    if(n%4==0)cout<<n/4*2<<"\n";
    else if(n%4==1)cout<<n/4*2+1<<"\n";
    else if(n%4==2)cout<<n/4*2+2<<"\n";
    else cout<<n/4*2+1<<"\n";
}

时间复杂度 O(1)

D题：
因为所有质数两两互质，所以把1到n的所有质数加入。
考虑到1不是质数，但与所有正整数互质，所以也要考虑在内。
接着加入剩下的任何一个合数，都会至少与加入的质数中的一个不互质。
所以答案即为 1到n中的质数+1+1。
注意到这个答案可能大于n，说明此时无解。
代码如下：

#include<bits/stdc++.h>
using namespace std;
int vis[100010];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n,ans=1;
    cin>>n;
    for(int i=2;i<=n;i++){
        if(!vis[i])ans++;
        for(int j=i;j<=n/i;j++)
            vis[i*j]=true;
    }
    if(ans+1>n)cout<<-1<<"\n";
    else cout<<ans+1<<"\n";
    return 0;
}

时间复杂度 O(n log n)

E题：
与传统的高精度加法类似，只是要注意前导0的问题。当0 0时，输出为0，不注意可能会没有输出。
代码如下：

#include<bits/stdc++.h>
using namespace std;
string a,b;
int c[200010];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>a>>b;
    for(int i=0;i<a.size()/2;i++)
        swap(a[i],a[a.size()-i-1]);
    for(int i=0;i<b.size()/2;i++)
        swap(b[i],b[b.size()-i-1]);
    int len=max(a.size(),b.size());
    for(int i=0;i<len;i++){
        int aa=0,bb=0;
        if(a.size()>i)aa=a[i]-'0';
        if(b.size()>i)bb=b[i]-'0';
        c[i]=(aa+bb)%10;
    }
    int p=len;
    while(p&&c[p]==0)p--;
    for(int i=p;i>=0;i--)
        cout<<c[i];
    cout<<"\n";
    return 0;
}

时间复杂度 O(max(lena,lenb))

F题：
考虑到最后留下的那个数一定是数组中的最大数，所以一直选与它相邻的数与它相加，可以得到最大值。
代码如下：

#include<bits/stdc++.h>
using namespace std;
long long a[200010];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    long long n;
    cin>>n;
    long long p=0,s=0,sum=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(a[i]>s){
            s=a[i];
            p=i;
        }
        sum=sum+a[i];
    }
    sum-=a[p];
    cout<<sum+s*(n-1)<<"\n";
    return 0;
}

时间复杂度 O(n)

G题：
一道经典的田忌赛马问题。
思想为用牛牛剩下来的最大的数去打败牛妹小于这个数的最大的数（注意：等于也不行）。
所以就可以想到先把牛牛和牛妹的华丽值分别排序，l指向牛牛华丽值数组的末尾，r指向牛妹华丽值数组的末尾，只要r指向的数大于或等于l指向的数，r--。接着ans++,l--,r--。当r==0或l==0时跳出循环。（以上就是双指针的思想）
代码如下：

#include<bits/stdc++.h>
using namespace std;
int a[200010],b[200010];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=m;i++)
        cin>>b[i];
    sort(a+1,a+n+1);
    sort(b+1,b+m+1);
    int l=n,r=m,ans=0;
    while(l>0&&r>0){
        while(r>0&&a[l]<=b[r])
            r--;
        if(r!=0)ans++;
        l--;
        r--;
    }
    cout<<ans<<"\n";
    return 0;
}

时间复杂度 O(m)

H题：
由于维护的是第k小，而且只增加数，不减少数，所以的k+1小，k+2小……的数据都没有用。
考虑建议一个大根堆。
处理初始值和操作1的时候往堆里塞数，当堆内数的数量大于k时，删去堆内最大值，也就是堆顶。
处理操作2的时候，此时若堆内数的数量小于k，则说明不存在第k小，答案为-1，若堆内数的数量等于k，则说明答案即为堆内最大值，也就是堆顶。
代码如下：

#include<bits/stdc++.h>
using namespace std;
priority_queue<int>q;
int main(){
    int n,m,k;
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++){
        int a;
        cin>>a;
        q.push(a);
        if(q.size()>k)q.pop();
    }
    for(int i=1;i<=m;i++){
        int op;
        cin>>op;
        if(op==1){
            int x;
            cin>>x;
            q.push(x);
            if(q.size()>k)q.pop();
        }
        else{
            if(q.size()==k)cout<<q.top()<<"\n";
            else cout<<-1<<"\n";
        }
    }
    return 0;
}

时间复杂度 O((m+n) log k)

I题：
看到n只有3000，考虑先用n^2暴力预处理出所有区间的异或和以及它的长度，存入pair类型的数组f。
接着对f进行排序，后缀和处理ss[i]，表示所有区间中异或和大于等于f[i].first的区间的最小长度。
最后对每个读入的数，用lower_bound从ss中二分查找到对应的答案。
代码如下：

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
PII f[9000010];
int a[3010],ss[9000010],tt[9000010];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n,m,tot=0;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++){
        int s=0;
        for(int j=i;j<=n;j++){
            s=s^a[j];
            f[++tot].first=s;
            f[tot].second=j-i+1;
        }
    }
    sort(f+1,f+tot+1);
    for(int i=1;i<=tot;i++)
        tt[i]=f[i].first;
    ss[tot+1]=2e9;
    for(int i=tot;i>=1;i--)
        ss[i]=min(ss[i+1],f[i].second);
    for(int i=1;i<=m;i++){
        int x;
        cin>>x;
        int p=lower_bound(tt+1,tt+tot+1,x)-tt;
        if(p>tot)cout<<-1<<"\n";
        else cout<<ss[p]<<"\n";
    }
    return 0;
}

时间复杂度 O(n^2 log n^2)
从形式上来看可能仍会超时，但是凭借C++ sort和lower_bound优秀的常数，可以卡过此题。

J题：
最优解问题，考虑dp。
设 dp[i]为从0~i这些数中取任何的一些数，可以获得的最大分数，f[i]为数组a中i出现的个数。
分为两个决策：
当取i这个数的时候，因为不能连续取，所以dp[i]=dp[i-2]+i* f[i]。
当不取i这个数的时候，因为没有任何限制，所以dp[i]继承dp[i-1]的值，即dp[i]=dp[i-1]。
总结，dp[i]=max(dp[i-2]+i* f[i],dp[i-1])。
初始：dp[0]=0,dp[1]=f[1]。
答案：dp[200000]。
代码如下：

#include<bits/stdc++.h>
using namespace std;
long long a[200010],dp[200010],f[200010];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        f[a[i]]++;
    }
    dp[0]=0;
    dp[1]=f[1];
    for(long long i=2;i<=200000;i++)
        dp[i]=max(dp[i-1],dp[i-2]+i*f[i]);
    cout<<dp[200000]<<"\n";
    return 0;
}

时间复杂度 O(200000)