首页 > 其他分享 >The 13th Shandong ICPC Provincial Collegiate Programming Contest

The 13th Shandong ICPC Provincial Collegiate Programming Contest

时间：2023-12-04 22:26:36浏览次数：33  
标签：Provincial Shandong Contest int auto cin long -- using

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;
}

标签：Provincial,Shandong,Contest,int,auto,cin,long,--,using
From： https://www.cnblogs.com/PHarr/p/17876160.html

相关文章

  • [Educational Codeforces Round 159 (Rated for Div. 2)](https://codeforces.com/con
    EducationalCodeforcesRound159(RatedforDiv.2)好困，差点没打A-BinaryImbalance#include<bits/stdc++.h>#defineintlonglong#defineendl'\n'usingnamespacestd;voidsolve(){ strings; intn; cin>>n; cin>>s; if(n==......
  • AtCoder Beginner Contest 328
    AtCoderBeginnerContest328链接：ToyotaProgrammingContest2023#7（AtCoderBeginnerContest328）-AtCoderA题意：给定n个数，将小于等于x的数加起来输出。#include<bits/stdc++.h>#defineintlonglong#defineendl'\n';usingnamespacestd;voidsolve(){......
  • AtCoder Beginner Contest 331
    AtCoderBeginnerContest331这场状态好差，下午的校赛也打的好差。A-Tomorrow#include<bits/stdc++.h>#defineintlonglong#defineendl'\n'usingnamespacestd;voidsolve(){intM,D;inty,m,d;cin>>M>>D>>y>>m>&......
  • AtCoder Beginner Contest 331 G Collect Them All
    洛谷传送门AtCoder传送门设数字\(i\)第一次拿到的时间为\(t_i\)，所求即为\(E(\max\limits_{i=1}^mt_i)\)。施min-max容斥，有：\[\begin{aligned}E(\max\limits_{i=1}^mt_i)&=\sum\limits_{T\subseteq[1,m]\landT\ne\varnothing}(-1)^{|T|-1}E(\min\l......
  • 2023-2024 CTU Open Contest
    A.Beth'sCookiesn=int(input())s=input()res=[]foriins:ifres==[]:res.append(i)elifi=='(':ifres[-1]==')':res.append("*")res.append(i)else:......
  • AtCoder Beginner Contest 331
    B-BuyOneCartonofMilk难度:⭐题目大意选择有三种套餐,6个鸡蛋S元,8个鸡蛋M元,12个鸡蛋L元;问如果要买至少N个鸡蛋,最少花费多少钱;解题思路一道入门级dp;神秘代码#include<bits/stdc++.h>#defineintlonglong#defineIOSios::sync_with_stdio(false......
  • The 13th Shandong ICPC Provincial Collegiate Programming Contest
    Preface昨天VP的那场没有字符串还没有原形毕露，今天遇到一个后期字符串直接和祁神大眼瞪小眼了最后一个半小时祁神狂冲F成功写出两个version的假算法，而我已经滚去补之前欠下的题目了赛后被徐神狠狠拷打了，评价为徐神是我们的红太阳，没有他我们都不能活A.Orders签到，按截止时间......
  • AtCoder Beginner Contest 295
    B-Bombs题意：就是说有一种炸弹，能炸曼哈顿距离的障碍物，要你打印出炸完后的图模拟#include<bits/stdc++.h>usingnamespacestd;charmp[50][50];voidsolve(){ intn,m; cin>>n>>m; for(inti=1;i<=n;i++){ for(intj=1;j<=m;j++){ cin>>mp[i][j]; } } for......
  • AtCoder Beginner Contest 326
    B-326-likeNumbers题意：找到一个不小于n的数是326数，定义是思路：简单的模拟循环即可#include<bits/stdc++.h>usingnamespacestd;boolcheck(intx){ vector<int>a; while(x){ a.push_back(x%10); x/=10; } if(a[1]*a[2]==a[0])returntrue; elsereturnfalse;}......
  • The 2023 ICPC Asia Hefei Regional Contest Test D. Balanced Array
    Preface这题赛场上出了个关键点基本都想到的做法，但因为一个地方卡住了没过去导致不得不选择弃掉这道题赛后补了下发现\(O(n\logn)\)的做法是只差临门一脚了，但\(O(n)\)的做法还是trick性挺强的Solution首先考虑枚举\(k\)，不难发现此时合法的前缀一定是个连续的区间，其中区间的......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99