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

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

简单题 小美的外卖订单编号

相当于求 除以 的余数，如果能够除尽即为第 号订单。
其实可以直接计算 除以 的余数加 。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int q;
    cin >> q;
    while (q--) {
        int m, x;
        cin >> m >> x;
        cout << (x - 1) % m + 1 << '\n';
    }
    return 0;
}

中等题 买卖股票的最好时机(一)

枚举 的过程中， 记录 之前的股票的最低价格，当 为 时则为 ，则在 处卖出股票的最大收益为 ，用 记录这个收益的最大值。
然后更新 。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++)cin >> a[i];
    int minval = 1e9;
    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans = max(ans, a[i] - minval);
        minval = min(minval, a[i]);
    }
    cout << ans << '\n';
    return 0;
}

困难题 数位染色

观察到只有 位，直接dfs枚举每个数位是被染色还是不被染色，分别加到两种数字之和中，最后判定两种数字之和是不是相等。
时间复杂度 ， 为 的数字位数。

#include <bits/stdc++.h>
using namespace std;
int main() {
    string s;
    cin >> s;
    int n = s.length();
    vector<int> a(n);
    for (int i = 0; i < n; i++)a[i] = s[i] - '0';
    bool ok = false;
    auto dfs = [&](auto&& self, int d, int sum1, int sum2)->void {
        if (d == n) {
            if (sum1 == sum2)ok = true;
            return;
        }
        self(self, d + 1, sum1 + a[d], sum2);
        self(self, d + 1, sum1, sum2 + a[d]);
    };
    dfs(dfs, 0, 0, 0);
    if (ok)
        cout << "Yes\n";
    else
        cout << "No\n";
    return 0;
}

另有dp解法，类似于01背包，将数位看成体积，检查体积 是否能被装到。
时间复杂度 ， 为数位之和。

#include <bits/stdc++.h>
using namespace std;
int main() {
    string s;
    cin >> s;
    int n = s.length();
    vector<int> a(n);
    for (int i = 0; i < n; i++)a[i] = s[i] - '0';
    int sum = accumulate(a.begin(), a.end(), 0LL);
    if (sum % 2 == 1) {
        cout << "No\n";
    } else {
        vector<bool> dp(sum + 1);
        dp[0] = true;
        for (int i = 0; i < n; i++)
            for (int j = sum; j >= a[i]; j--)
                if (dp[j - a[i]])
                    dp[j] = true;
        if (dp[sum / 2])cout << "Yes\n";
        else cout << "No\n";
    }
    return 0;
}