2026牛客寒假算法基础集训营4（A B C I H F G）

依旧开场叠罚时😭😭

A 本场比赛灵感来源于树状数组出题组

思路：
首先计算以下 个数的 是多少，然后从第一个数到最后一个数遍历，然后再遍历一个循环。
代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
const int N=2e3+5;
int a[N];
void solve()
{
    int n;
    cin>>n;
    int ans=0;
    int ttt=(4*(n-1)+4)/5;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int i=0;i<n;i++)
    {
        int cnt=0;
        for(int j=0;j<n;j++)
        {
            if(a[j]<=a[i])cnt++;
        }
        if((cnt-1)>=ttt)ans+=a[i];
    }
    cout<<ans;
}
signed main(){
	IOS
	int t=1;
	while(t--)
	{
		solve();
	}
}

B 构造部落

思路：
记录一下每个首领登基的年份。
代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
const int N=2e5+5;
int a[N];
int year[N];
void solve()
{
    int n,q,s;
    cin>>n>>q>>s;
    year[1]=s;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        year[i+1]=year[i]+a[i];
    }
    while(q--)
    {
        int x,y;
        cin>>x>>y;
        cout<<year[x]+y-1<<endl;
    }
}
signed main(){
	IOS
	int t=1;
	while(t--)
	{
		solve();
	}
}

C 墨提斯的排列

思路：
要让相邻两项异或值最小，就需要二进制表示只有一位二进制数不同，这种任意两个相邻的代码只有一位二进制数不同的编码称为格雷码。
代码：

void solve()
{
    int n;
    cin>>n;
    for(int i=0;i<(1<<n);i++)
    {
        cout<<(i^(i>>1))<<" ";
    }
}

I 初华的扭蛋机

思路：
谨记不要赌博，所以我一个都不押。
代码：

void solve()
{
    cout<<"######";
}

H 时不时使使用玉米加农炮掩饰害羞的邻座艾莉同学

思路：
这个的话我刚开始感觉是二维前缀和，不过这个图形是个菱形。手画一下，定义一下偏移量数组，用 sc 数组表示该点的得分。记录最大值和对应坐标。每次添加时只遍历地图中的 范围，满足曼哈顿距离的加分，然后不断更新最大值。
还是注意开 longlong。

○ ○ ● ○ ○ 
○ ● ● ● ○ 
● ● ● ● ● 
○ ● ● ● ○ 
○ ○ ● ○ ○ 

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
const int N=550;
int a[N][N];
int sc[505][505];
int dx[13]={-2,-1,-1,-1,0,0,0,0,0,1,1,1,2};
int dy[13]={0,-1,0,1,-2,-1,0,1,2,-1,0,1,0};
void solve()
{
    int n,m,q;
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>a[i][j];
        }
    }
    int ansx,ansy,ma=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            int cnt=0;
            for(int d=0;d<13;d++)
            {
                int xx=i+dx[d];
                int yy=j+dy[d];
                if(xx>0&&yy>0&&xx<=n&&yy<=m)
                {
                    cnt+=a[xx][yy];
                }
            }
            sc[i][j]=cnt;
            if(sc[i][j]>ma){
                ma=sc[i][j];
                ansx=i;
                ansy=j;
            }
        }
    }
    while(q--)
    {
        int x,y,z;
        cin>>x>>y>>z;
        a[x][y]+=z;
        for(int i=max(1LL,x-2);i<=min(n,x+2);i++)
        {
            for(int j=max(1LL,y-2);j<=min(m,y+2);j++)
            {
                if(abs(i-x)+abs(j-y)<=2)
                {
                    sc[i][j]+=z;
                    if(sc[i][j]>ma)
                    {
                        ansx=i;
                        ansy=j;
                        ma=sc[i][j];
                    }
                }
            }
        }
        cout<<ansx<<" "<<ansy<<endl;
    }
}
signed main(){
	IOS
	int t=1;
	while(t--)
	{
		solve();
	}
}

F 爱音的01串构造

思路：
赛时就想着交替分布了，没想到均匀分布。：将数量较少的字符作为分隔符，数量较多的字符分成尽可能均匀的段。
代码：

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define int long long
#define endl '\n'
void solve()
{
    int a,b;
    cin>>a>>b;
    int n=a+b;
    string s;
    if(a==0){
        cout<<string(b,'1')<<endl;
        return;
    }
    if(b==0){
        cout<<string(a,'0')<<endl;
        return;
    }
    if(a>=b){
        string tt(n,'0');
        s=tt;
        int d=a/(b+1);//每组至少有d个0
        int res=a%(b+1);//前res组每组多一个0
        for(int i=d;i<n;i+=d+1)//在字符串中每隔(d+1)个位置放一个1
        {
            if(res>0)//多放一个0
            {
                res--;
                i++;
            }
            s[i]='1';
        }
    }else{
        int d=b/(a+1);
        int res=b%(a+1);
        string tt(n,'1');
        s=tt;
        for(int i=d;i<n;i+=d+1)
        {
            if(res>0)
            {
                res--;
                i++;
            }
            s[i]='0';
        }
    }
    cout<<s<<endl;
}
signed main()
{
    int t;
    cin>>t;
    while(t--)
    {
        solve();
    }
}

G 真白的幻觉

思路：
表示拒绝补这个题，还真有人用 bfs 做出来了。
代码：

void solve()
{
    cout<<"277777788888899 27777789999999999";
}