2023 CPC 广东省赛(B,D)

这篇具有很好参考价值的文章主要介绍了2023 CPC 广东省赛(B,D)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

链接:The 2023 Guangdong Provincial Collegiate Programming Contest

有中文题面,题意就省略了。

B Base Station Construction

思路

本题参考了官方题解。

注意观察题目数据 n , m n, m n,m 的和都不超过 5 e 5 5e5 5e5,那么我们dp就可以从这两方面考虑,这里我们从站点而不从区间来入手。

定义dp方程: f [ i ] : f[i]: f[i]: i i i 个站点,且第 i i i 个站点必须建基站的最小花费。状态转移就是枚举上一个站点建在哪 j j j f [ i ] = min ⁡ j i − 1 f [ j ] + a [ i ] f[i] = \min_j^{i-1}f[j] +a[i] f[i]=minji1f[j]+a[i].

注意一个问题,有些转移是不合法的,当存在区间 [ l , r ] [l, r] [l,r] 使得 l > j , r < i l > j,r<i l>j,r<i.这样就有区间中没有站点,这是不合法的。 考虑对于每个 i i i 找到 p [ i ] : p[i]: p[i]:最远的合法转移点,用优先队列求解,易知 p [ i ] p[i] p[i] 一定是单调递增的,我们可以将区间按右端点排序,对于所有右端点小于当前点 ( r < i ) (r < i) (r<i) 的区间存入优先队列大顶堆按左端点排序,这样每次从队首取元素判断当前最远点 k k k 是否合法,如果不合法 l > k l > k l>k,就将 k = l k = l k=l.

具体实现见代码:

struct seg{
    int l, r;
    bool operator <(const seg& A){
        if(r == A.r) return l < A.l; 
        return r < A.r;
    }
}s[N];
priority_queue<pair<int, int> > q;
sort(s + 1, s + 1 + m);
while(!q.empty()) q.pop();
for(int i = 1, j = 0, k = 0; i <= n; i ++){
    while(j <= m && s[j].r < i) q.push({s[j].l, s[j].r}), j ++;
    if(!q.empty() && q.top().first > k) k = q.top().first; // 队列中都是r < i 的,若是 l > k 说明两个站点之间没有包含到该区间,这是不合法的,之间让k跳到l
    p[i] = k;
}

值得一提的是,官方题解中是用双指针求解 p [ i ] p[i] p[i] 的,时间更加优秀。

接下来的转移就很好想了,就是对于合法区间 f [ i ] = min ⁡ j = p [ i ] i − 1 f [ j ] + a [ i ] f[i] = \min_{j=p[i]}^{i-1}f[j] + a[i] f[i]=minj=p[i]i1f[j]+a[i]. 求区间最小值,可以用线段树维护,单点修改区间查询,转移时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn)。由于 p [ i ] p[i] p[i] 是单调递增的,可以用单调队列优化转移时间复杂度 O ( n ) O(n) O(n)。这里采用单调队列的方法。

最后的最后可以建立一个虚拟点来方便直接输出 a [ n + 1 ] = 0 a[n + 1] = 0 a[n+1]=0.

代码

/*
n和m之和都小于5e5 所以可以从这两方面来考虑,枚举站点和枚举区间
*/
#include <bits/stdc++.h>
using namespace std;

#define ll long long
const int N = 5e5 + 10;
const ll inf = 1e18;

struct seg{
    int l, r;
    bool operator <(const seg& A){
        if(r == A.r) return l < A.l; 
        return r < A.r;
    }
}s[N];

int a[N], n, m;

ll f[N], p[N]; // f:前i个站点 且第i个站点必须建立电站的最小花费(枚举上一个站点j求解) p:要求两个站点之间不能有完整的区间,pi = 最小的满足有要求的站点j
priority_queue<pair<int, int> > q;

ll que[N];
void solve(){
    cin >> n;
    for(int i = 1; i <= n; i ++) cin >> a[i];

    a[++ n] = 0; // 虚拟站点

    cin >> m;
    for(int i = 1; i <= m; i ++){
        cin >> s[i].l >> s[i].r;
    }
    
    sort(s + 1, s + 1 + m);

    while(!q.empty()) q.pop();
    for(int i = 1, j = 0, k = 0; i <= n; i ++){
        while(j <= m && s[j].r < i) q.push({s[j].l, s[j].r}), j ++;
        if(!q.empty() && q.top().first > k) k = q.top().first; // 队列中都是r < i 的,若是 l > k 说明两个站点之间没有包含到该区间,这是不合法的,之间让k跳到l
        p[i] = k;
    }

    int tot = 0, top = 0;
    f[0] = 0;
    for(int i = 1; i <= n; i ++){ // 求的是合法区间中p[i] ~ i - 1的最小值,由于p[i]单调递增可以用单调队列维护
        while(top <= tot && que[top] < p[i]) top ++;
        f[i] = f[que[top]] + a[i];
        while(tot >= top && f[que[tot]] > f[i]) tot --;
        que[++ tot] = i;
    }

    for(int i = 1; i <= n; i ++) que[i] = 0;
    cout << f[n] << "\n";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int t;
    cin >> t;
    while(t --){
        solve();
    }
    return 0;
}

D New Houses

思路

容易知道,对于不喜欢一起住的人即 a i < b i a_i<b_i ai<bi 的人,当迫不得已必须一起住的时候,价值就会减少 b i − a i b_i-a_i biai,当出现这种情况的时候,肯定是选减少价值最少的去一起住,这是本题唯一的算法贪心点。

接下来我们就不用思考那么多边界问题,直接大力分类讨论!具体看代码,每行几乎都有详细注释。

代码

#include <bits/stdc++.h>
using namespace std;

#define ll long long
const int N = 1e6 + 10;

struct node{
    int a, b;
};

bool cmp(node &A, node &B){
    return A.b - A.a < B.b - B.a;
}
void solve(){
    int n, m;
    cin >> n >> m;
    vector<node> A, B;

    ll sumA = 0, sumB = 0;
    for(int i = 1; i <= n; i ++){
        int a, b;
        cin >> a >> b;
        if(a >= b) A.push_back({a, b}), sumA += a; // 按喜好区分,将价值求和
        else B.push_back({a, b}), sumB += b;
    }

    int sizA = A.size(), sizB = B.size();

    if(sizB == 0){ // 没有喜欢单独住的
        if(sizA == 1) cout << A[0].b << "\n"; // 如果只有一个人,必须单独住
        else cout << sumA << "\n"; // 直接输出全部一起住的价值
        return ;
    }

    sort(B.begin(), B.end(), cmp); // 按如果不能独自住,按损失的最少的排序

    if(sizA == 0){ // 全是喜欢独自住的
        if(m < sizB * 2 - 1){ // 不能全部单独住
            for(auto [a, b] : B){ // 枚举有多少是必须一起住的
                sumB -= (b - a); // 将一起住的减少的值减去
                m --;
                sizB --;
                if(m >= sizB * 2) break; // 满足剩下的人可以单独住结束
            }
        } 
        cout << sumB << "\n";
        return ;
    }

    if(sizA == 1){ // 只有一个喜欢一起住的
        ll ans = sumB;
        m --;
        if(m < sizB * 2){ // 剩下的人不能全部单独住
            ans += A[0].a; // 喜欢一起住的人就能加上价值
            for(auto [a, b] : B){
                ans -= (b - a);
                m --;
                sizB --;
                if(m >= sizB * 2) break;
            }
        }
        else{ // 剩下的人可以全部单独住,分情况讨论
            ans = max(sumB + A[0].b, sumB - (B[0].b - B[0].a) + A[0].a); // 全部单独住,或者有一对一起住
        }
        cout << ans << "\n";
        return ;
    }

    // sizA > 1 && sizB > 0

    // 喜欢一起住的肯定都一起住,剩下的位置让无法独自住,选减少价值最小的一起住
    ll ans = sumA + sumB;
    m -= sizA;
    if(m < sizB * 2){
        for(auto [a, b] : B){
            ans -= (b - a);
            m --;
            sizB --;
            if(m >= sizB * 2) break;
        }
    }
    cout << ans << "\n";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int t;
    cin >> t;
    while(t --){
        solve();
    }
    return 0;
}

F Traveling in Cells

大致题意:每个格子有颜色和价值(两者都有修改操作)每次给定颜色集合 A A A 只能走集合内颜色的格子,问从 x x x 点开始最多能收集到多少价值。

思路

对于这种维护东西很多很杂无从下手的问题我们开始逐步简化

对于每一个询问我们要解决的主要问题是:从给定点 x x x 出发最远能走到的边界 [ l , r ] [l, r] [l,r] 是多少,解决这个问题后,只需要用一个线段树/树状数组就可以维护单点修改,区间求和输出答案了。

对于从 x x x 开始最多能走多远,无疑是有单调性的,即如果往左边走我们不能走到 l l l 点,那么 1 ∼ l − 1 1\sim l-1 1l1 肯定也不能走到,右边同理。既然有单调性我们就考虑二分。要二分就必须知道一个区间内颜色有多少个是属于集合 A A A,注意每次给定颜色集合大小 k k k,保证 ∑ k i ≤ 1 e 6 \sum k_i \leq 1e^6 ki1e6,所以我们可以对每个颜色分开查询,最后算总数是否等于我们二分出来的该区间长度即可。

到此为此问题被简化为询问一个区间内指定单一颜色的个数(带修),我们继续简化问题。如果问题保证所有点只有两种颜色我们是否能解决该问题?显然用线段树就能很方便解决,将颜色分为黑白 0 / 1 0/1 0/1 维护每个区间的价值,区间之和就代表白色点的个数。
回到有多种颜色的问题,我们是否能对每一种颜色都建一棵线段树呢?对于颜色 i i i 的线段树,颜色 i i i 代表 1 1 1,其他颜色代表 0 0 0. 关于 n n n 棵线段树空间不够的问题我们可以动态开点,每次只新增一条链空间复杂度为 O ( ( n + q ) l o g n ) O((n + q)logn) O((n+q)logn).

时间复杂度:二分答案 + 线段树,上界取决于询问的集合总大小 k k k,所以为 O ( ( l o g n ) 2 ∑ k i ) O((logn)^2 \sum k_i) O((logn)2ki).
到此为止问题已经在逐步简化下解决了具体见代码及注释。文章来源地址https://www.toymoban.com/news/detail-741092.html

代码

/*
对区间的价值用树状数组维护
对颜色用线段树维护,即对每种颜色建立一棵线段树,动态开点保证空间,对于颜色i, 区间[l, r].sum 表示的是区间中颜色i的数量
*/
#include <bits/stdc++.h>
using namespace std;

#define ll long long
typedef vector<int> Vec;
const int N = 1e5 + 10, MAX = 1e5;

int n, q;

int v[N], c[N];

int T[N], tot; // T[i]:颜色为i的线段树的根
struct node{ 
    int ls, rs, sum;
}tr[N * 200];

void update(int& p, int loc, int k, int l = 1, int r = MAX){ // 对于该颜色更新点loc的价值+1
    if(!p) p = ++ tot;
    tr[p].sum += k;
    if(l == r) return ;
    int mid = (l + r) >> 1;
    if(loc <= mid) update(tr[p].ls, loc, k, l, mid);
    else update(tr[p].rs, loc, k, mid + 1, r);
}

int query(int p, int ql, int qr, int l = 1, int r = MAX){ // 对于颜色i查询区间[ql, qr]该颜色的个数
    if(!p) return 0;
    if(ql <= l && r <= qr) return tr[p].sum;
    int mid = (l + r) >> 1, ans = 0;
    if(ql <= mid) ans += query(tr[p].ls, ql, qr, l, mid);
    if(qr > mid) ans += query(tr[p].rs, ql, qr, mid + 1, r);
    return ans; 
}

ll val[N]; // 树状数组维护单点修改和区间求和
int lowbit(int x){ return x & -x; }
void update(int r, int k){
    for(int i = r; i <= n; i += lowbit(i)) val[i] += k;
}
ll get_sum(int l, int r){
    ll ans = 0;
    for(int i = r; i; i -= lowbit(i)) ans += val[i];
    for(int i = l - 1; i; i -= lowbit(i)) ans -= val[i];
    return ans;
}

Vec ci; // 每次查询的颜色集合
bool check(int len, int l, int r){
    int sum = 0;
    for(auto x : ci){
        sum += query(T[x], l, r); // 对于所有集合中的颜色查询[l, r].sum
    }
    return sum == len;
}

void get_ans(){
    int x, k;
    cin >> x >> k;
    ci.clear();
    for(int i = 1, y; i <= k; i ++){
        cin >> y;
        ci.push_back(y);
    }
	
	sort(ci.begin(), ci.end());
	ci.erase(unique(ci.begin(), ci.end()), ci.end()); // 去重

    int l = 1, r = n;

    int Lr = x;
    while(l <= Lr){ // 二分找最远能到的左边界
        int mid = (l + Lr) >> 1;
        if(check(x - mid + 1, mid, x)) Lr = mid - 1;
        else l = mid + 1;
    }

    int Rl = x;
    while(Rl <= r){ // 二分找最远合法的右边界
        int mid = (Rl + r) >> 1;
        if(check(mid - x + 1, x, mid)) Rl = mid + 1;
        else r = mid - 1;
    }
    cout << get_sum(l, r) << "\n"; // 输出求和
}

void clear(){
	for(int i = 0; i <= tot; i ++) tr[i] = {0, 0, 0};
	for(int i = 1; i <= n; i ++) T[i] = val[i] = 0;
	tot = 0;
}
void solve(){
	cin >> n >> q;
	clear();
    for(int i = 1; i <= n; i ++){
        cin >> c[i];
        update(T[c[i]], i, 1);
    }
    for(int i = 1; i <= n; i ++){
        cin >> v[i];
        update(i, v[i]);
    }

    for(int i = 1; i <= q; i ++){
        int op, p, x;
        cin >> op;
        if(op == 1){ // 更改颜色
            cin >> p >> x;
            update(T[c[p]], p, -1);
            c[p] = x;
            update(T[c[p]], p, 1);
        }
        else if(op == 2){ // 更改价值
            cin >> p >> x;
            update(p, x - v[p]);
            v[p] = x;
        }
        else get_ans();
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int t;
    cin >> t;
    while(t --){
    	solve();
    }
    return 0;
}

到了这里,关于2023 CPC 广东省赛(B,D)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 小师弟:2022广东省工科赛分享(越障排爆省一,完整项目)

         小师弟说在广东省工科赛跟电赛拿奖了,听了很开心,那个腼腆的男孩,也能开始自己独挡一面了。我个人认为,在大学中参与竞赛,并不是要蛮干,而是要在竞赛中,实践,查漏补缺,进行总结,所以今天邀请小师弟写写自己的心得,分享给大家。      经过大一

    2024年02月14日
    浏览(39)
  • 2020-2021 年度广东省职业院校学生专业技能大赛网络空间安全赛项

    2020-2021 年度广东省职业院校学生专业技能大赛网络空间安全赛项 (总分100分) 一、竞赛项目简介 “网络安全”竞赛共分A. 基础设施设置与安全加固;B. 网络安全事件响应、数字取证调查和应用安全;C. CTF夺旗-攻击;D. CTF夺旗-防御等四个模块。根据比赛实际情况,竞赛赛场

    2024年02月04日
    浏览(45)
  • 广东省第三届职业技能大赛“网络安全项目”B模块任务书

    PS: 关注鱼影安全 模块 B 竞赛项目试题 本文件为:广东省第三届职业技能大赛网络安全项目试题

    2024年02月02日
    浏览(40)
  • 广东省第三届职业技能大赛“网络安全项目”B模块--数字取证解析

    PS: 关注鱼影安全 模块 B 竞赛项目试题 本文件为:广东省第三届职业技能大赛网络安全项目试题-模块 B 本次比赛时间为 4 个小时。 介绍 竞赛有固定的开始和结束时间,参赛队伍必须决定如何有效的分配时间。请认真阅读以下指引! (1)当竞赛结束,离开时请不要关机; (

    2024年01月19日
    浏览(60)
  • “广东省五一劳动奖章”获得者卫晓欣:“她”力量让新兴技术更获认可

    近日,2023年广东省庆祝“五一”国际劳动节暨五一劳动奖表彰大会顺利召开,大会表彰了2023年全国和省五一劳动奖、工人先锋号代表。 其中,来自FISCO BCOS开源社区产业应用合作伙伴广电运通的创新中心总监卫晓欣,凭借在区块链领域的突出贡献,荣获“广东省五一劳动奖章

    2024年02月03日
    浏览(42)
  • 2023-05-02 动态规划简介

    阶段、状态、决策、策略、状态转移方程 1) 阶段和阶段变量 将问题的全过程恰当地分成若干个相互联系的阶段 闫氏DP分析法:对应f[i][j]的ij遍历时形成的所有f[i][j] 阶段的划分一般根据时间和空间的自然特征去划分 阶段的划分便于把问题转化成 多阶段决策 问题 2) 状态和状

    2024年02月03日
    浏览(34)
  • 动态规划机试2023.4.19

    eg12.1 N阶楼梯上楼问题 ex12.1 吃糖果和(eg12.1的程序一模一样) eg12.2 最大序列和 eg12.3 最大子矩阵(北京大学复试上机题) 复习了二维前缀和并且使用暴力做法解出该题 ex12.2 最大连续子序列(浙江大学复试上机题) 使用前缀和 eg12.4 拦截导弹(北京大学复试上机题) 最大不

    2023年04月22日
    浏览(27)
  • 【算法】动态规划 ⑧ ( 动态规划特点 )

    求解类型 : 动态规划 必须是求 最值 , 可行性 , 方案数 , 三者之一 , 如果求其它内容 , 则不能使用动态规划算法 ; 求最值 : 最大值 , 最小值 等 ; 大规模问题的结果 由 小规模问题 的计算结果 取最大值 大规模问题的结果 由 小规模问题 的计算结果 取最小值 可行性 : 是否可行

    2023年04月08日
    浏览(46)
  • 【算法 - 动态规划】原来写出动态规划如此简单!

    从本篇开始,我们就正式开始进入 动态规划 系列文章的学习。 本文先来练习两道通过 建立缓存表 优化解题过程的题目,对如何将 递归函数 修改成 动态规划 的流程有个基本的熟悉。 用最简单的想法完成题目要求的 递归 函数; 定义明确 递归函数 的功能!!! 分析是否存

    2024年02月21日
    浏览(44)
  • 各个AI模型写2023年广东高考作文大比拼

    今天是一年一度的高考开始的日子,寒窗苦读十二年,剑指今朝。         作为过来人,当年的高考场景还历历在目。这里先预祝各位莘莘学子,高考正常发挥,旗开得胜,马到功成,考上心中理想的大学。 今天早上是语文卷。里面的大头归属作文了。 今年广东高考的语文

    2024年02月08日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包