首页 > 其他分享 >The 2023 Guangdong Provincial Collegiate Programming Contest(2023广东省赛)

The 2023 Guangdong Provincial Collegiate Programming Contest(2023广东省赛)

时间：2023-07-23 15:34:11浏览次数：42  
标签：Provincial begin Contest int pos cin ++ vector 2023

链接：https://codeforces.com/gym/104369

A. Programming Contest

C++ Code 
#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

void solve() {
    int y1, y2;
    cin >> y1;
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    cin >> y2;
    int ans = y2 - y1 + 1;
    for (int i = 0; i < n; i++) {
        if (a[i] >= y1 && a[i] <= y2) {
            ans--;
        }
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

C. Trading

C++ Code 
#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

void solve() {
    int n;
    cin >> n;
    vector<pair<int, int>> a(n);
    for (auto &[x, y] : a) {
        cin >> x >> y;
    }
    sort(a.begin(), a.end());
    i64 ans = 0;
    for (int l = 0, r = n - 1; l < r; ) {
        auto &[x1, y1] = a[l];
        auto &[x2, y2] = a[r];
        int c = min(y1, y2);
        ans += 1LL * (x2 - x1) * c;
        y1 -= c;
        y2 -= c;
        if (y1 == 0) {
            l++;
        }
        if (y2 == 0) {
            r--;
        }
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

D. New Houses

C++ Code 
#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

void solve() {
    int n, m;
    cin >> n >> m;

    vector<int> a(n), b(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i] >> b[i];
    }    
    vector<int> v(n);
    for (int i = 0; i < n; i++) {
        v[i] = a[i] - b[i];
    }
    i64 sum = 0;
    i64 ans = 0;
    sort(v.begin(), v.end(), greater());
    for (int i = 0; i < n; i++) {
        sum += b[i];
    }
    if (m >= 2 * n - 1) {
        ans = max(ans, sum);
    }
    sum += v[0];
    for (int i = 1; i < n; i++) {
        sum += v[i];
        if (m >= 2 * n - (i + 1)) {
            ans = max(ans, sum);
        }
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

F. Traveling in Cells

C++ Code 
#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

template <typename T>
struct Fenwick {
    int n;
    vector<T> a;
    Fenwick(const int &n = 0) : n(n), a(n, T()) {}
    void modify(int i, T x) {
        for (i += 1; i <= n; i += i & -i) {
            a[i - 1] += x;
        }
    }
    T get(int i) {
        T res = T();
        for (; i > 0; i -= i & -i) {
            res += a[i - 1];
        }
        return res;
    }
    T sum(int l, int r) { // [l, r)
        return get(r) - get(l);
    }
    int kth(T k) {
        int x = 0;
        for (int i = 1 << __lg(n); i; i >>= 1) {
            if (x + i <= n && k >= a[x + i - 1]) {
                x += i;
                k -= a[x - 1];
            }
        }
        return x;
    }
};

void solve() {
    int n, q;
    cin >> n >> q;
    vector<int> c(n), v(n);
    for (int i = 0; i < n; i++) {
        cin >> c[i];
        c[i]--;
    }
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }
    vector<vector<int>> pos(n);
    for (int i = 0; i < n; i++) {
        pos[c[i]].push_back(i);
    }

    vector<pair<int, vector<int>>> que(q);
    for (int i = 0; i < q; i++) {
        vector<int> qi;
        int o;
        cin >> o;
        if (o == 1) {
            int p, x;
            cin >> p >> x;

            p--, x--;
            pos[x].push_back(p);
            qi.push_back(p);
            qi.push_back(x);
        } else if (o == 2) {
            int p, x;
            cin >> p >> x;
            p--;
            qi.push_back(p);
            qi.push_back(x);            
        } else {
            int x, k;
            cin >> x >> k;
            x--;
            qi.push_back(x);
            for (int j = 0; j < k; j++) {
                int x;
                cin >> x;
                x--;
                qi.push_back(x);
            }
        }
        que[i] = {o, qi};
    }

    vector<Fenwick<int>> col(n);
    vector<Fenwick<i64>> val(n);
    for (int i = 0; i < n; i++) {
        sort(pos[i].begin(), pos[i].end());
        pos[i].erase(unique(pos[i].begin(), pos[i].end()), pos[i].end());
        int N = pos[i].size();
        col[i] = Fenwick<int>(N);
        val[i] = Fenwick<i64>(N);
    }

    for (int i = 0; i < n; i++) {
        int j = lower_bound(pos[c[i]].begin(), pos[c[i]].end(), i) - pos[c[i]].begin();
        col[c[i]].modify(j, 1);
        val[c[i]].modify(j, v[i]);
    }

    for (int i = 0; i < q; i++) {
        auto &[o, vec] = que[i];
        if (o == 1) {
            int p = vec[0];
            int x = vec[1];
            int j = lower_bound(pos[c[p]].begin(), pos[c[p]].end(), p) - pos[c[p]].begin();
            col[c[p]].modify(j, -1);
            val[c[p]].modify(j, -v[p]);
            j = lower_bound(pos[x].begin(), pos[x].end(), p) - pos[x].begin();
            col[x].modify(j, +1);
            val[x].modify(j, +v[p]);
            c[p] = x;
        } else if (o == 2) {
            int p = vec[0];
            int x = vec[1];
            int j = lower_bound(pos[c[p]].begin(), pos[c[p]].end(), p) - pos[c[p]].begin();
            val[c[p]].modify(j, x - v[p]);
            v[p] = x;            
        } else {
            int x = vec[0];
            vec.erase(vec.begin());
            int ql = x, qr = x + 1;
            auto check1 = [&](int r, const vector<int> &a) {
                int l = x;
                int res = 0;
                for (auto &ai : a) {
                    int jl = lower_bound(pos[ai].begin(), pos[ai].end(), l) - pos[ai].begin();
                    int jr = lower_bound(pos[ai].begin(), pos[ai].end(), r) - pos[ai].begin();
                    res += col[ai].sum(jl, jr);
                }
                return r - l == res;
            };
            int l = x + 1, r = n;
            while (l <= r) {
                int m = (l + r) >> 1;
                if (check1(m, vec)) {
                    l = m + 1;
                    qr = m;
                } else {
                    r = m - 1;
                }
            }

            auto check2 = [&](int l, const vector<int> &a) {
                int r = x + 1;
                int res = 0;
                for (auto &ai : a) {
                    int jl = lower_bound(pos[ai].begin(), pos[ai].end(), l) - pos[ai].begin();
                    int jr = lower_bound(pos[ai].begin(), pos[ai].end(), r) - pos[ai].begin();
                    res += col[ai].sum(jl, jr);                    
                }
                return r - l == res;
            };
            l = 0, r = x;
            while (l <= r) {
                int m = (l + r) >> 1;
                if (check2(m, vec)) {
                    r = m - 1;
                    ql = m;
                } else {
                    l = m + 1;
                }
            }

            i64 ans = 0;
            for (auto &xi : vec) {
                int jl = lower_bound(pos[xi].begin(), pos[xi].end(), ql) - pos[xi].begin();
                int jr = lower_bound(pos[xi].begin(), pos[xi].end(), qr) - pos[xi].begin();
                ans += val[xi].sum(jl, jr);
            }
            cout << ans << '\n';
        }
    }

}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

I. Path Planning

C++ Code 
#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> p(n * m);
    vector<vector<int>> a(n, vector<int>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
        }
    }
    auto check = [&](int x) {
        int pre = -1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (a[i][j] < x) {
                    if (pre > j) {
                        return false;
                    }
                    pre = j;
                }
            }
        }
        return true;
    };
    int ans = 0;
    int l = 0, r = n * m;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (check(mid)) {
            l = mid + 1;
            ans = mid;
        } else {
            r = mid - 1;
        }
    }
    cout << ans << '\n';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

K. Peg Solitaire

C++ Code 
#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<vector<int>> a(n, vector<int>(m));
    for (int i = 0; i < k; i++) {
        int x, y;
        cin >> x >> y;
        x--, y--;
        a[x][y] = 1;
    }
    int dx[] = {+1, -1, +0, +0};
    int dy[] = {+0, +0, +1, -1};
    int ans = 1E9;
    function<void(int)> dfs = [&](int res) {
        ans = min(ans, res);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (a[i][j]) {
                    for (int k = 0; k < 4; k++) {
                        int nx = i + dx[k];
                        int ny = j + dy[k];
                        int tx = i + 2 * dx[k];
                        int ty = j + 2 * dy[k];
                        if (nx < 0 || ny < 0 || nx >= n || ny >= m) {
                            continue;
                        }
                        if (tx < 0 || ty < 0 || ty >= m || tx >= n) {
                            continue;
                        }
                        if (a[nx][ny] && !a[tx][ty]) {
                            a[tx][ty] = 1;
                            a[i][j] = a[nx][ny] = 0;
                            dfs(res - 1);
                            a[tx][ty] = 0;
                            a[i][j] = a[nx][ny] = 1;                            
                        }
                    }
                }
            }
        }
    };
    dfs(k);
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

标签：Provincial,begin,Contest,int,pos,cin,++,vector,2023
From： https://www.cnblogs.com/kiddingma/p/17575066.html

相关文章

  • 练习记录-AtCoder Beginner Contest 311-(A-E)
    写的还挺顺的F之后补A-FirstABC找abc三个字母什么时候出现了一次输出即可B-VacationTogether题意：最长的几个人一排里面均有时间#include<bits/stdc++.h>#defineclosestd::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)usingnamespacestd;typedeflon......
  • Toyota Programming Contest 2023#4（AtCoder Beginner Contest 311）——D
    https://atcoder.jp/contests/abc311/tasks/abc311_d思路题目说如果当前方向的下一个点能走，那么就一直走，否则才能转向。根据题意模拟即可，这道题的难点在于，碰到已经走过的点到底要不要走。如果当前方向走到底，其中的点之前全部都走过那么就不能再走了。我们用bfs模拟，对于能一直走......
  • 2023.7.23 接雨水
    一个能接雨水的区域，肯定是两边高，中间低，基于这个前提出发就能得到两种做法。动态规划预处理出每个柱子左边最高的柱子，同时也处理出每个柱子右边的最高的柱子。两者取一个min，记做h。那么如果h比当前柱子更高，那么起码当前这个柱子就可以在垂直领域上可以存下h-当前柱子高个单位......
  • 我的2023暑假青岛3天2晚旅游计划
    我的原暑假出游计划：https://ntopic.cn/p/2023072301/看海玩水优选青岛小朋友们最开心的暑假来了，今年我的2位小朋友最希望去玩的是看海和玩水。这样今年暑假我的出游目标就比较明确了，该计划实施路径了。出游目的地的比较和选择（维度：温度适宜、有海有沙滩）：上海本地游：有海有沙滩的......
  • 2023.29 人工智能的发展特征
    今年以来，人工智能又热了起来，发展有以下几个特征:涌现出很多大模型，它们使用大量数据集进行训练，所以称它们为大型语言模型(LLM)。这些模型是生成式的。这意味着他们可以创建新内容，无论是文本、图像、声音、视频、3D对象，甚至是计算机代码。这是相较于旧人工智能模型的一个进步，旧的......
  • 2023牛客暑期多校训练营2 补题
    D.TheGameofEating题意：有n个人和m道菜，每个人对每个菜的都有一个喜好度a[i][j]，所有人都知道其他人的喜好度，现在需要上k道菜，从1，2...，n，1，2.....的顺序来选，如果每个人都只考虑自己的喜好，问最后哪些菜会被端上来Solution我们考虑到所有人都知道其他人的喜好度，也就是说，假设当前要选......
  • 「赛后总结」20230722 CSP 模拟赛
    「赛后总结」20230722CSP模拟赛点击查看目录目录「赛后总结」20230722CSP模拟赛反思题解T1回文思路代码T2快速排序思路代码T3混乱邪恶思路代码T4校门外歪脖树上的鸽子思路吓死我了我还以为K8He不更博了。为啥前天模拟赛不写啊？打过，没参加。为啥昨天模拟赛不......
  • NOI2023游记
    7.21坐飞机提前来成都，飞机晚点了一个小时，但只晚到了15分钟。酒店房间太小了，愤怒。晚上点外卖，吃了一大堆水果。水了一晚上qq。7.22早上起来pvz。报到，因为到太早会有人拿着摄像机拍一路所以9点多到的，结果是AH第一个到的被采访了，不会说话/ll。去宿舍的时候有小姐姐帮忙拎箱子......
  • 2023年7月23日 天气：晴
       今天早上起来看了一个小时的英语阅读，接着背了一小时的英语单词，然后写了一个小时的Java，然后看了一小时的阅读，接着看了两个小时的作业。  明天打算背会单词，然后看几个小时的构建之法，接着出去玩一个小时。......
  • 2023.7.22
    今天去学ret2dlreolve剩下的部分，再次人傻了，剩下内容是64位下NORELRO和PartialRELRO的例题exp，我原本以为和32位差不多，当时也不清楚为什么还要再分个64位出来，差点没去看。结果看了之后人傻了，exp用了之前学过的csu的相关知识，我也不太懂为什么要用这个技巧。然后各种exp部分搞得特......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99