题解 | 牛客周赛 Round 24

赛题整体上偏简单, 但是需要注意数据范围和其他小细节。

A-小红的矩阵构造

显然, 如果 是奇数, 我们可以构造出类似

1 2 3

4 5 6

7 8 9

这样的答案, 若 为偶数, 考虑将偶数行翻转。

#include <bits/stdc++.h>
using i64 = long long;

int main() {
    std::ios::sync_with_stdio(false); std::cin.tie(nullptr);
    int n, x = 1;
    std::cin >> n;
    std::vector<std::vector<int>> ans(n + 1, std::vector<int>(n + 1));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            ans[i][j] = x++;
        }
    }
    if (n % 2 == 0) {
        for (int i = 2; i <= n; i += 2) std::reverse(ans[i].begin() + 1, ans[i].end());
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            std::cout << ans[i][j] << " \n"[j == n];
        }
    }
    return 0;
}

B-小红的因子

枚举因子即可, 只是需要注意的是, 若 很大, 并且 是个质数, 那么答案 , 这时候做乘法会溢出, 改为判断 是否大于 即可。

#include <bits/stdc++.h>
using i64 = long long;

void solve() {
    i64 n;
    std::cin >> n;
    std::vector<i64> factors;
    for (i64 i = 1; i <= n / i; i++) {
        if (n % i == 0) {
            factors.push_back(i);
            if (i * i != n) factors.push_back(n / i);
        }
    }
    std::sort(factors.begin(), factors.end());
    for (auto x : factors) {
        if (x > std::sqrt(n)) {
            std::cout << x << "\n";
            break;
        }
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int T;
    std::cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

C-小红的小数点串 (贪心)

遇到小数点时, 将前面的剩余部分拿来做整数部分, 剩下的一位做小数部分显然是最优的。

#include <bits/stdc++.h>
using i64 = long long;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::string s;
    std::cin >> s;
    int n = s.size();
    double ans = 0;
    int lst = -1;
    if (s.find(".") == std::string::npos) {
        std::cout << s << "\n";
        return 0;
    }
    for (int i = 0; i < n; i++) {
        if (s[i] == '.') {
            std::string t = s.substr(lst + 1, i - 1 - lst);
            i64 inte = std::stoll(t); 
            lst = i + 1;
            ans += inte;
            ans += (s[i + 1] - '0') * 1.0 / 10;
            i += 1;
        }
    }
    int back = n - 1;
    for (int i = n - 1; i >= 0; i--) {
        if (s[i] == '.') {
            back = i;
            break;
        }
    }
    i64 add = 0;
    for (int i = back + 2; i < n; i++) {
        add = add * 10 + (s[i] - '0');
    }
    ans += add;
    std::cout << std::fixed << std::setprecision(1) << ans << "\n";
    return 0;
}

D-小红的数组操作

显然可以二分答案, 将问题转化为判定问题, 但是需要注意的是, 若 check 的值很小并且 , 那么操作次数会极多, 因此, check 时, 如果当前所需的操作次数 了, 需要直接跳出去, 避免超出 long long 范围。

#include <bits/stdc++.h>
using i64 = long long;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n, k, x;
    std::cin >> n >> k >> x;
    std::vector<i64> a(n + 1);
    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
    }
    i64 L = -1E18, R = 1E18;
    auto check = [&](i64 t) -> bool {
        i64 cnt = 0;
        for (int i = 1; i <= n; i++) {
            if (a[i] > t) {
                cnt += (a[i] - t + x - 1) / x;
                if (cnt > k) return false;
            }
        }
        return true;
    };
    while (L < R) {
        i64 mid = L + R >> 1;
        if (check(mid)) {
            R = mid;
        } else {
            L = mid + 1;
        }
    }
    std::cout << L << "\n";
    return 0;
}