牛客春招刷题训练营 - 2025.4.4 题解

活动地址：牛客春招刷题训练营 - 编程打卡活动

Easy 查找组成一个偶数最接近的两个素数

简要题意

如题。

Solution

筛出素数，暴力枚举即可。

这个数据范围筛素数可以暴力判断，下面代码中使用线性筛。

Code

vector<int> minp,primes;

void sieve(int n)
{
    minp.assign(n+1,0);
    primes.clear();
    for (int i=2;i<=n;i++)
    {
        if (!minp[i])
        {
            minp[i]=i;
            primes.push_back(i);
        }
        for (auto p:primes)
        {
            if (i*p>n) break;
            minp[i*p]=p;
            if (p==minp[i]) break;
        }
    }
}

void R()
{
	int n;
	cin>>n;
	int a=0,b=n;
	for (int i=2;i*2<=n;i++)
	{
		int j=n-i;
		if (minp[i]==i&&minp[j]==j)
			a=i,b=j;
	}
	cout<<a<<'\n'<<b;
	return;
}

Medium 最小循环节

简要题意

给一个字符串，你可以在其任意位置插入任意字符，求操作后串的最小循环节。

Solution

循环节中至少每种字符出现一次，容易把字符串构造成形如 ABCDabcdABCDabcdABCDabcd... 的形式，故答案就是串中字符种类数。

Code

void R()
{
	int ans=0;
	string s;
	cin>>s;
	map<char,bool> vis;
	for (char c:s)
		if (!vis[c])
			vis[c]=1,ans++;
	cout<<ans;
	return;
}

Hard 连续子数组最大和

简要题意

给定一个数组，求其最大子段和。

Solution

以某个位置结尾的最大子段和就是这个位置的元素加上或不加上上一个位置结尾的最大子段和。

Code

void R()
{
	int n;
	cin>>n;
	vector<int> a(n);
	for (int &x:a) cin>>x;
	for (int i=1;i<n;i++)
		a[i]+=max(a[i-1],0);
	cout<<*max_element(a.begin(),a.end());
	return;
}