526互联

The 13th Shandong ICPC Provincial Collegiate Programming Contest

发布时间 2023-12-04 22:13:13作者: PHarr

A. Orders

按照订单的结束时间排序，然后遍历一遍即可

#include<bits/stdc++.h>

using namespace std;

#define int long long
using pii = pair<int, int>;
using i32 = int32_t;

void solve() {
    int n, k;
    cin >> n >> k;
    vector<pii> p(n);
    for (auto &[a, b]: p)
        cin >> a >> b;
    sort(p.begin(), p.end());

    int cnt = 0, sum = 0;
    for (int lst = 0; const auto &[a, b]: p) {
        cnt += ( a - lst ) * k , sum += b , lst = a;
        if( cnt < sum ) {
            cout << "No\n";
            return ;
        }
    }
    cout << "Yes\n";
    return;
}

i32 main() {
    int TC;
    for (cin >> TC; TC; TC--)
        solve();
    return 0;
}

B. Building Company

解法类似求拓扑序，只是约束关系比较复杂。

我们统计每一种员工不同的项目要求的数量。每次吸引到新的员工后就检查该种员工是否满足了新的项目要求。如果新的项目所有要求都被满足了，就把他加入到队列中。

#include<bits/stdc++.h>

using namespace std;

#define int long long

using i32 = int32_t;
using vi = vector<int>;
using pii = pair<int, int>;


i32 main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int g;
    cin >> g;

    unordered_map<int, int> have;
    for (int t, u; g; g--)
        cin >> t >> u, have[t] += u;
    int n;
    cin >> n;
    // 把所有的需求按照员工种类分类并排序
    unordered_map<int, priority_queue<pii, vector<pii>, greater<pii>>> requirements;
    // 每个项目还有多少个需求等待满足
    vi cnt(n, 0);
    // 完成每个项目可以吸引的员工数量
    vector attract(n, vector<pii>());
    queue<int> q;
    for (int i = 0, k; i < n; i++) {
        cin >> cnt[i];
        for (int j = cnt[i], a, b; j; j--) {
            cin >> a >> b;
            if (have[a] >= b) {
                cnt[i]--;
            } else requirements[a].emplace(b, i);
        }
        if (cnt[i] == 0) q.push(i);
        cin >> k, attract[i].resize(k);
        for (auto &[c, d]: attract[i]) cin >> c >> d;
    }

    int res = 0;
    for (int u; !q.empty();) {
        u = q.front(), q.pop();
        res++;
        for (auto [c, d]: attract[u]) {
            have[c] += d;
            for (int v, id; !requirements[c].empty();) {
                v = requirements[c].top().first, id = requirements[c].top().second;
                if (v > have[c]) break;
                requirements[c].pop(), cnt[id]--;
                if (cnt[id] == 0) q.push(id);
            }
        }
    }
    cout << res << "\n";
    return 0;
}

D. Fast and Fat

二分答案。

我们二分的最终的速度\(x\)，那么就可以把人分成两类，一类是速度大于\(x\)，另一类是速度小于\(x\)。

对于速度大于\(x\)的人，最大可以背负的人的重量为\(v+w-x\)。对于速度小于\(x\)的人，其速度是没有意义的，只需要记录下重量，然后贪心的优先满足重量大的选手，这样就可以判断出是否可以使得所有人的速度都大于\(x\)

#include<bits/stdc++.h>

using namespace std;

#define int long long
using pii = pair<int, int>;
using i32 = int32_t;
const int inf = 1e9;

void solve() {
    int n;
    cin >> n;
    vector<pii> p(n);
    for (auto &[w, v]: p) cin >> v >> w;
    int l = 0, r = inf, res = -1;
    auto check = [p](int x) -> bool {
        vector<int> a;
        multiset<int> b;
        for (const auto &[w, v]: p)
            if (v < x) a.push_back(w);
            else b.insert(v + w - x);
        if (a.size() > b.size()) return false;
        sort(a.begin(), a.end(), greater<int>());
        for (const auto &i: a) {
            if (i > *b.rbegin()) return false;
            b.erase(b.lower_bound(i));
        }
        return true;
    };
    for (int mid; l <= r;) {
        mid = (l + r) / 2;
        if (check(mid)) res = mid, l = mid + 1;
        else r = mid - 1;
    }
    cout << res << "\n";
    return;
}

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int TC;
    for (cin >> TC; TC; TC--)
        solve();
    return 0;
}

E. Math Problem

可以注意到的是先乘再除是没有意义的，所以最优解一定是先做除法。

可以枚举做除法的次数，然后计算出做乘法可以得到结果的区间，直到区间可以包含\(m\)时结束。

过程中会溢出，我这里使用了__int128

#include<bits/stdc++.h>

using namespace std;

#define int long long
using pii = pair<int, int>;
using i32 = int32_t;
using i128 = __int128;
const int inf = 1e9;

istream &operator>>(istream &is, i128 &x) {
    int y;
    is >> y, x = y;
    return is;
}

ostream &operator<<(ostream &os, i128 &x) {
    int y = x;
    os << y;
    return os;
}

void solve() {
    i128 n, k, m, a, b;
    cin >> n >> k >> m >> a >> b;

    if (n % m == 0) {
        cout << "0\n";
        return;
    }
    if (k == 1) {
        cout << "-1\n";
        return;
    }
    auto check = [m](i128 l, i128 r) {
        i128 t = (l / m) * m;
        if (l <= t and t <= r) return true;
        t += m;
        if (l <= t and t <= r) return true;
        return false;
    };
    i128 res = LLONG_MAX;
    for (i128 cnt = 0, sum = 0, l, r; true;) {
        for (l = n, r = n, cnt = 0; check(l, r) == false and l <= r; l = l * k, r = r * k + k - 1, cnt += a);
        res = min(res, cnt + sum);
        if (n == i128(0)) break;
        sum += b, n /= k;
    }
    cout << res << "\n";
    return;

}

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int TC;
    for (cin >> TC; TC; TC--)
        solve();
    return 0;
}

G. Matching

对于原始等式可以修改为\(i-a_i=j-a_j\)的形式，然后把点按照\(i-a_i\)的形式分类，贪心选择就好了

#include<bits/stdc++.h>

using namespace std;

#define int long long
using pii = pair<int, int>;
using i32 = int32_t;
const int inf = 1e9;

void solve() {
    int n;
    cin >> n;
    map<int, vector<int>> g;
    for (int i = 1, a; i <= n; i++) {
        cin >> a;
        g[i - a].push_back(a);
    }
    int res = 0;
    for (auto &[k, v]: g) {
        sort(v.begin(), v.end(), greater<int>());
        for (int i = 0; i < v.size(); i += 2)
            if (i + 1 < v.size() and v[i] + v[i + 1] >= 0) res += v[i] + v[i + 1];
    }
    cout << res << "\n";


}

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int TC;
    for (cin >> TC; TC; TC--)
        solve();
    return 0;
}

I. 三只骰子

暴力枚举

#include<bits/stdc++.h>

using namespace std;

#define int long long
using pii = pair<int, int>;
using i32 = int32_t;

pii operator+(const pii &a, const pii &b) {
    pii ans = {a.first + b.first, a.second + b.second};
    return ans;
}

i32 main() {
    vector<pii> T = {{1, 0},
                     {0, 2},
                     {0, 3},
                     {4, 0},
                     {0, 5},
                     {0, 6}};
    pii t;
    cin >> t.first >> t.second;
    for (auto i: T)
        for (auto j: T)
            for (auto k: T)
                if ((i + j + k) == t) {
                    cout << "Yes\n";
                    return 0;
                }
    cout << "No\n";

    return 0;
}

L. Puzzle: Sashigane

首先我们可以一圈一圈的放置，直到目标点一定在边界上是，我们可以不断的包裹目标点，直到目标点变成一个在角落的正方形，然后再包裹这个正方形就好了。

#include<bits/stdc++.h>

using namespace std;

#define int long long
using pii = pair<int, int>;
using i32 = int32_t;
using i128 = __int128;
const int inf = 1e9;
using vi = vector<int>;

vector<array<int, 4>> res;

const int dx[] = {1, 1, -1, -1};
const int dy[] = {1, -1, 1, -1};


void op2(int sx, int sy, int tx, int ty, int x, int y) {
    vi cnt(4);
    for (int i = 0, px, py; i < 4; i++) {
        px = x + dx[i], py = y + dy[i];
        while (sx <= px and px <= tx and sy <= py and py <= ty)
            cnt[i]++, px += dx[i], py += dy[i];
    }


    int t = -1;
    for (int i = 0; i < 4; i++) {
        if (cnt[i] == 0) continue;
        if (t == -1 or cnt[i] < cnt[t]) t = i;
    }
    int d = tx - sx - cnt[t];
    cnt[t] = 0;
    for (int px = x + dx[t], py = y + dy[t], p = -1;
         sx <= px and px <= tx and sy <= py and py <= ty; px += dx[t], py += dy[t], p--) {
        res.push_back({px, py, p * dx[t], p * dy[t]});
    }
    t = -1;
    for (int i = 0; i < 4; i++) {
        if (cnt[i] == 0) continue;
        if (t == -1) t = i;
    }
    if (t == -1 or d == 0 ) return;
    for (int px = (dx[t] == -1 ? sx : tx), py = (dy[t] == -1 ? sy : ty), p = sx - tx;
         sx <= px and px <= tx and sy <= py and py <= ty and d > 0;
         px -= dx[t], py -= dy[t], p++, d--) {
        res.push_back({px, py, p * dx[t], p * dy[t]});
    }
    return;
}

void op1(int sx, int sy, int tx, int ty, int x, int y) {
    if (sx == x or sy == y or tx == x or ty == y) {
        op2(sx, sy, tx, ty, x, y);
        return;
    }
    int d = tx - sx;
    res.push_back({sx, sy, d, d});
    res.push_back({tx, ty, 1 - d, 1 - d});
    op1(sx + 1, sy + 1, tx - 1, ty - 1, x, y);
    return;
}

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n, x, y;
    cin >> n >> x >> y;
    if (n == 1 and x == 1 and y == 1) {
        cout << "Yes\n0\n";
        return 0;
    }
    op1(1, 1, n, n, x, y);
    cout << "Yes\n" << res.size() << "\n";
    for (auto it: res) {
        for (auto i: it) cout << i << " ";
        cout << "\n";
    }
    return 0;
}

赛后看了官解，发现自己的做法太糟糕了

#include<bits/stdc++.h>

using namespace std;

#define int long long

using i32 = int32_t;

i32 main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n, l, r, u, d;
    cin >> n >> u >> l, r = l, d = u;
    cout << "Yes\n" << n - 1 << "\n";
    for (int i = 1; i < n; i++) {
        if (u > 1 and l > 1) {
            u--, l--;
            cout << u << " " << l << " " << d - u << " " << r - l << "\n";
        } else if (u > 1 and r < n) {
            u--, r++;
            cout << u << " " << r << " " << d - u << " " << l - r << "\n";
        } else if (l > 1) {
            d++, l--;
            cout << d << " " << l << " " << u - d << " " << r - l << "\n";
        } else {
            d++, r++;
            cout << d << " " << r << " " << u - d << " " << l - r << "\n";
        }
    }
    return 0;
}

J. Not Another Path Query Problem

思路类似数位 dp。

首先大于的\(V\)的整数\(v’\)在二进制下一定有一个前缀和\(V\)相同。我们枚举这个前缀，然后包含所有的使用包含这个前缀的所有边，这样每次再用 bfs 计算一下连通性就可以判断答案是否有解。

#include<bits/stdc++.h>

using namespace std;

#define int long long

using i32 = int32_t;
using vi = vector<int>;
using pii = pair<int, int>;


i32 main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n, m, q, V;
    cin >> n >> m >> q >> V;
    vector e(n + 1, vector<pii>());
    for (int u, v, w; m; m--) {
        cin >> u >> v >> w;
        e[u].emplace_back(v, w);
        e[v].emplace_back(u, w);
    }
    vector<pii> query(q);
    for (auto &[a, b]: query) cin >> a >> b;
    vi res(q);
    auto calc = [&res, query, n, e, q](int t) {
        vi col(n + 1);
        auto bfs = [&col, e](int s, int t) {
            queue<int> q;
            q.push(s), col[s] = s;
            for (int u; !q.empty();) {
                u = q.front(), q.pop();
                for (auto [v, w]: e[u]) {
                    if (col[v] or (w & t) != t) continue;
                    q.push(v), col[v] = s;
                }
            }
        };
        for (int i = 1; i <= n; i++)
            if (!col[i]) bfs(i, t);
        for (int i = 0; i < q; i++)
            res[i] |= col[query[i].first] == col[query[i].second];
    };
    if (V == 0) calc(0);
    else for (int t = V, T = (1ll << 60); t < T; t += (t & -t)) calc(t), cerr << t << "\n";
    for (auto i: res)
        cout << (i ? "Yes\n" : "No\n");
    return 0;
}