牛客春招刷题训练营 - 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;
}
亿联网络公司福利 779人发布