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

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

简单题 单词倒排

将标点换成空格后以空格分隔单词输入即可。

#include <bits/stdc++.h>
using namespace std;
int main() {
    string s;
    getline(cin, s);
    for (auto& it : s)
        if (!isalnum(it))
            it = ' ';
    vector<string> words;
    string word;
    stringstream sin(s);
    while (sin >> word)
        words.push_back(word);
    reverse(words.begin(), words.end());
    for (auto it : words)
        cout << it << ' ';
    return 0;
}

还有 Python 极致压行（逃

print(*reversed("".join(" " if i in __import__("string").punctuation else i for i in input()).split()))

中等题 判断两个IP是否属于同一子网

模拟。
注意样例的不定行数输入。
可以用 string 读入后 sscanf 格式化输入 IP 地址。

#include <bits/stdc++.h>
using namespace std;
string s[3];
int a[3][4];
void solve() {
    for (int i = 0; i < 3; i++) {
        sscanf(s[i].c_str(), "%d.%d.%d.%d", &a[i][0], &a[i][1], &a[i][2], &a[i][3]);
    }
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 4; j++) {
            if (a[i][j] < 0 || a[i][j] > 255) {
                cout << "1\n";
                return;
            }
        }
    }
    
    long long ym = ((1ll * a[0][0]) << 24) + ((1ll * a[0][1]) << 16) +
    ((1ll * a[0][2]) << 8) + (1ll * a[0][3]);
    bool isone = 1;
    for (int i = 31; i >= 0; i--) {
        if ((ym & (1LL << i)) == 0) {
            isone = 0;
        } else {
            if (!isone) {
                cout << "1\n";
                return;
            }
        }
    }
    for (int i = 1; i <= 2; i++) {
        for (int j = 0; j < 4; j++) {
            a[i][j] &= a[0][j];
        }
    }
    int ans = 0;
    for (int i = 0; i < 4; i++)
        if (a[1][i] != a[2][i])
            ans = 2;
    cout << ans << '\n';
}
int main() {
    while (cin >> s[0] >> s[1] >> s[2])
        solve();
    return 0;
}

困难题 将真分数分解为埃及分数

使用 map 存储分数。
表示 。
随后遍历 map 直到不能操作：

1. 如果 能约分，将其约分。
2. 如果 不能约分，则枚举 从 到 ，如果 和 不互质，则分解成 。
3. 如果分子不能拆分出和 不互质的数，则将 拆分成 。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int fz, fm;
    scanf("%d/%d", &fz, &fm);
    map<long long, long long> mp;
    mp[fm] = fz;
    bool ok = 1; //1=不能继续分解 0=能继续分解
    do {
        ok = 1;
        for (auto it : mp) {
            long long x = it.first;
            long long y = it.second; // y/x
            if (y == 0) {
                mp.erase(x);
                ok = 0;
                break;
            }
            else if (gcd(x, y) > 1) {
                mp.erase(x);
                long long g = gcd(x, y);
                x /= g;
                y /= g;
                mp[x] += y;
                ok = 0;
                break;
            }
            else if (y >= 2) {
                bool ok2 = 1; //0能拆分 1不能拆分
                for (int i = y; i >= 1; i--) {
                    if (gcd(x, i) > 1) {
                        mp[x] -= i;
                        long long g = gcd(x, i);
                        mp[x / g] += (i / g);
                        ok2 = 0;
                        break;
                    }
                }
                if (ok2) {
                    mp.erase(x);
                    mp[x + 1] += y;
                    mp[x * (x + 1)] += y;
                }
                ok = 0;
                break;
            }
        }
    } while (!ok);
    vector<pair<long long, long long>> ans;
    for (auto it : mp) {
        if (it.second == 1) {
            ans.push_back(it);
        }
    }
    for (int i = 0; i < ans.size(); i++)
        cout << ans[i].second << '/' << ans[i].first << "+\n"[i == ans.size() - 1];
    return 0;
}