牛客春招刷题训练营 - 2025.4.14 题解
活动地址：牛客春招刷题训练营 - 编程打卡活动
Easy 自守数
简要题意
定义平方的末尾几位等于自身的自然数为自守数，求 内自守数个数。
Solution
枚举范围内每个数 ，假设
，则
为自守数等价于
。
Code
void R()
{
int n,ans=0;
cin>>n;
auto len=[&](int x)->int
{
int res=1;
for (;x;res*=10,x/=10);
return res;
};
for (int i=0;i<=n;i++)
ans+=(i*i%len(i)==i);
cout<<ans;
return;
}
Medium 小红的双生串
简要题意
求让一个字符串前半部分为同一种字母，后半部分为同一个字母，最少需要修改多少个位置。
Solution
输出前半部分出现次数最多的字母的出现次数，前半部分长度减去这个次数就是前半部分的代价，后半部分同理。
Code
void R()
{
string s;
cin>>s;
int n=s.size(),ans=0;
vector<int> cnt(26);
for (int i=0;i<n/2;i++)
cnt[s[i]-'a']++;
ans+=n/2-*max_element(cnt.begin(),cnt.end());
cnt.assign(26,0);
for (int i=n/2;i<n;i++)
cnt[s[i]-'a']++;
ans+=n/2-*max_element(cnt.begin(),cnt.end());
cout<<ans;
return;
}
Hard abb
简要题意
给定字符串 ，求满足
的三元组
个数。
Solution
考虑枚举 ，则贡献为
，其中
分别是
前后
的出现次数。
我们可以先求出所有字母出现次数，这样再遍历字符串时，就可以维护前后缀字母出现次数。
Code
void R()
{
int n;
i64 ans=0;
string s;
cin>>n>>s;
vector<int> pre(26),suf(26);
for (int i=0;i<n;i++)
suf[s[i]-'a']++;
for (int i=0;i<n;i++)
{
int p=s[i]-'a';
pre[p]++,suf[p]--;
ans+=1ll*(i-pre[p]+1)*suf[p];
}
cout<<ans;
return;
}
投递字节跳动等公司10个岗位
阿里云工作强度 284人发布