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

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

简单题 求int型正整数在内存中存储时1的个数

可用gcc内置 __builtin_popcount()函数直接求出。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    cout << __builtin_popcount(n);
    return 0;
}

中等题 整数与IP地址间的转换

最大的长整数为 ，超过了 int 所能表示上限，可以使用 unsigned int 或 long long。
技巧：可以用 scanf("%lld.%lld.%lld.%lld", &a, &b, &c, &d); 读取 个用点号分隔的整数。
对于 IP 地址转长整数，第 个数乘以 相加，可使用位运算左移实现。
对于长整数转 IP 地址，求 的余数，并除以 ，倒序输出即为答案。

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long a, b, c, d;
    scanf("%lld.%lld.%lld.%lld", &a, &b, &c, &d);
    printf("%lld\n", (a << 24) + (b << 16) + (c << 8) + d);
    long long n;
    int f[4];
    scanf("%u", &n);
    for (int i = 3; i >= 0; i--) {
        f[i] = n % 256;
        n >>= 8;
    }
    printf("%d.%d.%d.%d\n", f[0], f[1], f[2], f[3]);
    return 0;
}

困难题 字符串通配符

可以考虑递归 ：

1. 当 且 ，返回 。
2. 当 和 有且只有一个成立，返回 。
3. 当 时，返回 。
4. 当 ，返回 。
5. 当 ，枚举 从 到 ，如果存在 使得 则返回 ，否则返回 。
6. 当 且 且 时，返回 。

最后答案是 。
提示：多个星号可看作一个星，会显著降低时间复杂度。

#include <bits/stdc++.h>
using namespace std;
string s, t;
int n, m;
bool match(int x, int y) {
    if (x == n && y == m)return 1;
    else if (x == n || y == m) return 0;
    else if (s[x] == t[y])
        return match(x + 1, y + 1);
    else if (s[x] == '?')
        return isalnum(t[y]) ? match(x + 1, y + 1) : 0;
    else if (s[x] == '*') {
        for (int i = y; i <= m; i++) {
            if (i > y && (!isalnum(t[i - 1])))return 0;
            if (match(x + 1, i))return 1;
        }
        return 0;
    } else return 0;
}
int main() {
    cin >> s >> t;
    for (auto& it : s)if (isalpha(it))it = tolower(it);
    for (auto& it : t)if (isalpha(it))it = tolower(it);
    n = s.length();
    m = t.length();
    string s2;
    s2 += s[0];
    for (int i = 0; i + 1 < n; i++) {
        if (s[i] == '*' && s[i + 1] == '*')continue;
        s2 += s[i + 1];
    }
    s = s2;
    n = s.length();
    cout << (match(0, 0) ? "true" : "false") << '\n';
    return 0;
}