牛客周赛 Round 39

IOI赛制，600+，y神 关键思路，C D 题的对 P 取模
D 题是一个完全背包，不优化可过
E 因为边界导致没 a 出来，30 分
F 暴力可以过…

A

签到

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 2e6 + 10;

int main() {
    int n = 0;
    vector<ll> nums(6);
    ll sum = 0;
    for (int i = 0; i < 6; i++) {
        cin >> nums[i];
        sum += nums[i];
    }
    if (nums[0] * 30 < sum) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

B

从大到小排序，模拟即可

#include <bits/stdc++.h>  

using namespace std;  
typedef long long ll;  
const int N = 2e6 + 10;  

int main() {  
    ll n = 0, k;  
    cin >> n >> k;  
    vector<ll> nums(n);  
    ll sum = 0;  
    for (int i = 0; i < n; i++) {  
        cin >> nums[i];  
        sum += nums[i];  
    }  
    sort(nums.begin(), nums.end(), greater<ll>());  
    ll yu = sum % k;  
    if (yu == 0) {  
        cout << 0 << endl;  
        return 0;  
    }    for (int i = 0; i < n; i++) {  
        if (nums[i] <= yu) {  
            yu -= nums[i];  
        } else {  
            yu = 0;  
        }        if (yu == 0) {  
            cout << i + 1 << endl;  
            return 0;  
        }    }    cout << n << endl;  
    return 0;  
}

C

因为 p == 3 只需要判断三种情况

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 2e6 + 10;

int main() {
    // read file
    ll n, p;
    cin >> n >> p;
    vector<ll> v(n);
    for (auto &it: v) {
        cin >> it;
        it = it % 3;
    }

    // n 种 food
    // value ai
    // sum % 3 == 0
    // 0 1 2
    unordered_map<int, int> M;
    for (auto it: v) {
        if (it == 0) {
            cout << 1 << endl;
            return 0;
        } else if (it == 1) {
            M[1]++;
        } else if (it == 2) {
            M[2]++;
        }
    }
    if (M.count(1) && M.count(2)) {
        cout << 2 << endl;
        return 0;
    }
    if (M.count(1)) {
        cout << 3 << endl;
        return 0;
    }
    if (M.count(2)) {
        cout << 3 << endl;
        return 0;
    }
    return 0;
}

D

Bfs ，加剪枝，暴力即可过

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 2e6 + 10;

int main() {
    // read file
    ll n, p;
    cin >> n >> p;
    vector<ll> v(n);
    set<ll> s;
    for (auto &it: v) {
        cin >> it;
        it = it % p;
        s.insert(it);
    }
    vector<ll> nv;
    queue<pair<int, int>> q;
    vector<bool> vis(p, false);
    for (auto it: s) {
        nv.push_back(it);
        q.push({it, 1});
        vis[it] = true;
    }
    if (s.count(0)) {
        cout << 1 << endl;
        return 0;
    }

    // bfs
    while (!q.empty()) {
        auto [cur, step] = q.front();
        q.pop();
        if (cur == 0) {
            cout << step << endl;
            return 0;
        }
        for (auto it: nv) {
            int to = (cur + it) % p;
            if (vis[to]) continue;
            q.push({to, step + 1});
            vis[to] = true;
        }
    }
    cout << -1 << endl;
    return 0;
}

E

求有多少种 1 <= i <= p, 1 <= j <= m, 1 <= k <= p, 注意去重
满足 i x j + 2 x i x k + 2 x j x k == x
思路 枚举+二分找答案

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int main() {
    ll n = 0, k, p, ans = 0, x, m;
    cin >> n >> m >> p >> x;
    unordered_set<ll> s;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            ll l = 1, r = p + 1;
            while (l <= r) {
                ll mid = l + (r - l) / 2;
                if (i * j + 2 * i * mid + 2 * j * mid == x && mid <= p) {
                    s.insert(i + j * 3001 + 1ll * mid * 3001 * 3001);
                    break;
                } else if (i * j + 2 * i * mid + 2 * j * mid < x) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
        }
    }
    cout << s.size() << endl;
}

F

暴力能过，数据很弱

看到有并查集，二分，线段树的解法