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

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

简单题 自守数

题意即判断 内含多少 使得 。
注意特判 ，因为 无定义。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    int ans = 1;
    for (int i = 1; i <= n; i++) {
        int square = i * i;
        int digit = log10(i) + 1;
        int mod = 1;
        while (digit--)mod *= 10;
        if (square % mod == i)ans++;
    }
    cout << ans << '\n';
    return 0;

}

中等题 小红的双生串

将字符串截成前后两段，两段分别变成这一段出现次数最多的字符。

#include <bits/stdc++.h>
using namespace std;
int main() {
    string s;
    cin >> s;
    int cnt1[26] = {}, cnt2[26] = {};
    int n = s.length();
    for (int i = 0; i < n; i++) {
        if (i < n / 2)cnt1[s[i] - 'a']++;
        else cnt2[s[i] - 'a']++;
    }
    int max1 = *max_element(cnt1, cnt1 + 26);
    int max2 = *max_element(cnt2, cnt2 + 26);
    cout << n - max1 - max2 << '\n';
    return 0;
}

困难题 abb

倒序遍历，我们遍历 a 找 bb。
设截止到位置 的后缀的 b 的出现次数为 ，则共有 种组合可以组合成 bb。
当前位置所加贡献为 ，注意 不能等于 。
然后 。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    int cnt[26] = {};
    long long ans = 0;
    for (int i = n - 1; i >= 0; i--) {
        for (int j = 0; j < 26; j++) {
            if (j == s[i] - 'a')continue;
            ans += (cnt[j]) * (cnt[j] - 1) / 2;
        }
        cnt[s[i] - 'a']++;
    }
    cout << ans << '\n';
}