2026牛客寒假算法基础集训营4

链接： 2026牛客寒假算法基础集训营4

A

数组a存数值的出现次数，根据：“其他数字至少80%小于等于”，则我们可以判断至多其他数字的20%大于 $a_x$ 可以将 $a_x$ 分在A组中。

应当注意的是其他数字，所以基数要用 $n-1$ ，而不是 $n$ 。

#include <bits/stdc++.h>
using namespace std;
#define int long long
int a[2005];
signed main() {
    int n;
    cin>>n;
    memset(a,0,sizeof(a));
    for(int i=1;i<=n;i++){
        int tp;
        cin>>tp;
        a[tp]++;
    }
    double cnt=0,ans=0;
    double st=double(n-1)*0.2;

    for(int i=1000;i>=1;i--){
        if(cnt<=st){
            ans+=a[i]*i;
        }else{
            break;
        }

        cnt+=a[i];
    }
    cout<<ans;
}

B

数组存前缀和，查询时第$x$位代表下标，$y$年就直接加上，同时还要减一才是真实的年份。

#include <bits/stdc++.h>
using namespace std;
#define int long long
int d[200005];
signed main() {
    int  n,q,s;
    cin>>n>>q>>s;
    d[0]=s;
    for(int i=1;i<=n;i++){
        int tp;
        cin>>tp;
        d[i]=d[i-1]+tp;
    }
    for(int i=1;i<=q;i++){
        int tmp1,tmp2;
        cin>>tmp1>>tmp2;
        cout<<d[tmp1-1]+tmp2-1<<endl;
    }
}

C

想要让异或值最小的话，找规律可以发现，对于00，01，10，11 来说，可以是00，01，11，10。如果n再加1，则是 00，01，11，10，110，111，101，100. 可以发现，只需每次增加n时将前面的序列倒转过来，再在最高位改为1就可以。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxm = 1<<18 ;
int a[maxm+5];
signed main() { 
    int n;
    n=18;
    int pos=2;
    a[0]=0,a[1]=1;
    for(int i=2;i<=n;i++){
        for(int j=pos-1;j>=0;j--,pos++){
            a[pos]=(1<<(i-1));
            a[pos]+=a[j];

        }
    }
    cin>>n;
    for(int i=0;i<(1<<(n));i++){
        cout<<a[i]<<' ';
    }
}

F

最好的情况一定是 01 交错排列，这样所有的字串都 mex 都为 2 是最大的。那么对于无法交错排列的情况，我们就要尽可能地让字符串的字串最大数量地包含 01 。考虑将少的那个字符均匀地排在字符串上，假设每个稀缺字符 $a$ 对于另一种字符 $b$ 的间距至少为 $d$ ，那 $d\times{(a+1)}\le b $ ，由此可以得出 $d$ ，这时我们将多出间距 $d$ 的字符 $b$ 的剩余部分均分到每个块中。

#include <bits/stdc++.h>
using namespace std;
#define int long long 

signed main() { 
    int t;
    cin>>t;
    while(t--){
        int a,b;
        cin>>a>>b;
        int ma=max(a,b),mi=min(a,b),mit,mat;
        int d=ma/(mi+1);
        int rem=ma-d*(mi+1);
        if(mi==a) mat=1,mit=0;
        else mat=0,mit=1;
        for(int i=1;i<=mi;i++){
            for(int j=1;j<=d;j++){
                cout<<mat;
            }
            if(rem){
                rem--;
                cout<<mat;
            }
            cout<<mit;
        }
        for(int j=1;j<=d;j++){
            cout<<mat;
        }
        cout<<endl;
    }
}