2023 广东省大学生程序设计竞赛(部分题解)

目录

A - Programming Contest

B - Base Station Construction

C - Trading

D - New Houses

E - New but Nostalgic Problem

I - Path Planning

K - Peg Solitaire

A - Programming Contest

签到题：直接模拟

直接按照题目意思模拟即可，为了好去重，我们使用set即可

void solve(){int l,r; cin>>l>>n;set<int> s;while(n--){int x; cin>>x;s.insert(x);}cin>>r;int ans = 0;for(int i=l;i<=r;i++) ans += !s.count(i);cout << ans << endl;return ;
}

B - Base Station Construction

 银牌题：优先队列优化dp

我们可以读懂题目也就是说对于一个区间[l,r]而言我们一定要选一个，可以知道r+1从l转移过来肯定是最优的，由此我们可以对于每一个点维护最优的前一个点的转移，同时注意到后缀一定是满足前缀的要求的所以pre[r+1]=max(pre[r+1],l)同时再用前缀最大值处理一下，我们定义在第i个点建立电站同时满足前面的每一个区间的同时的最优解为f_i,转移方程为f_i = min_{f_j} + a[i]，为前缀的点同时随着i的增大j一定是同时增大的变化,所以可以考虑使用优先队列维护dp即可，同时注意怎么判断最后答案是上面，我们可以++n这样满足答案就是f_n

void solve(){cin>>n;vector<int> a(n+5),pre(n+5),q(n+5);vector<LL> dp(n+5);for(int i=1;i<=n;i++) cin>>a[i];n++;cin>>m;while(m--){int l,r; cin>>l>>r;pre[r+1]=max(pre[r+1],l);}for(int i=1;i<=n;i++) pre[i]=max(pre[i-1],pre[i]);int hh=0,tt=0;q[0]=0;for(int i=1;i<=n;i++){while(hh<=tt and q[hh]<pre[i]) hh++;dp[i] = dp[q[hh]] + a[i];while(hh<=tt and dp[q[tt]]>=dp[i]) tt--; q[++tt]=i;}cout << dp[n] << endl;return ;
}

C - Trading

 签到题：贪心

我们可以有个明显的结论就是从价格最便宜的买入，在贵的卖出就行了，进一步贪心我肯定是买最多的同时卖了最优，所以就是买一半卖一半即可

void solve(){cin>>n;LL sum = 0;for(int i=1;i<=n;i++){int a,b; cin>>a>>b;w[i]={a,b};sum += b;}sort(w+1,w+1+n);LL buy = 0,cnt = 0;for(int i=1;i<=n;i++){auto [a,b]=w[i];int now = min(sum/2-cnt,b);buy += (LL)a*now;cnt += now;}LL use = 0,num = 0;for(int i=n;i>=1;i--){auto [a,b]=w[i];int now = min(sum/2-num,b);use += (LL)a*now;num += now;}LL ans = use - buy;cout << ans << endl;return ;
}

D - New Houses

签到题：贪心

设有邻居贡献为x,无为y

我们有个明显的结论就是如果你是有邻居优就让你有邻居，否则让你没邻居，我们一开始可以所有人挤在一起，放置在前i个位置，\sum_i^nx_i，(特判n==1)接着按照没有邻居贡献大的来排序，可以注意到多了几个位置就可以有多少人是可以没有邻居的同时贡献要大于有邻居的时候才考虑，贡献为y-x,同时注意到如果说后面排了n-1个人的时候前面最开始就没有邻居了，就需要特判到底是合在一起还是分开贡献最优即可

void solve(){cin>>n>>m;LL ans = 0;// 一开始所有人都挤在一起for(int i=1;i<=n;i++){int x,y; cin>>x>>y;a[i]={x,y};ans += x;}if(n==1){cout << a[1].second << endl;return ;}sort(a+1,a+1+n,[](PII a,PII b){return a.second-a.first>b.second-b.first;});int pos = 0;for(int i=1;i<=m-n and a[i].second-a[i].first>=0 and i<=n;i++){auto [x,y]=a[i];ans += y-x;pos = i;}if(pos==n-1){// 由于前面挤在一起的只有一个人 考虑合在一起或者是分开ans = max(ans+a[n-1].first-a[n-1].second,ans-a[n].first+a[n].second);}cout << ans << endl;return ;
}

E - New but Nostalgic Problem

 银牌-金牌题：trie树+dfs贪心

我们选出m个使得结果最小我们可以发现要维护的是最长公共前缀，那么我们考虑字符的存储可以考虑使用trie树，我们有一个贪心的想法，我一定是从aaa...abc....这样的结果来看是不是满足数量最优的，如果说对于当前已经选了“abc"下一个是选择d组合为abcd，那么满足是abcd的前缀起码要选择两个，同时前面的abc[a-c]肯定是都得加上因为如果这前面有更优解肯定跑到前面去了，同时对于[e-z]每一个分支最多选择一个，因为如果选择多了当前结果就不是abcd了，同时我们可以发现这样也就是遍历了每一个字符串而已,所以时间是\sum_{}s_i符合要求，接下来就是用实现即可

int tr[N][26],sum[N],ed[N];
string s,ans;
bool ok;
void insert(){int p = 0;for(auto&v:s){int x=v-'a';if(!tr[p][x]) tr[p][x]=++idx;p = tr[p][x];sum[p]++;}ed[p]++;
}
void used(){for(int i=0;i<=idx;i++){for(int j=0;j<26;j++) tr[i][j]=0;sum[i]=ed[i]=0;}ok = false;idx = 0;ans.clear();
}
void dfs(int u,int last){if(ok) return ;int s = 0;//ab 之后  aba abb abc abd ...//得到的答案是abint now = last + ed[u];for(auto v : tr[u]) s += min(1,v); // 表示对于当前分支接着都取不一样if(now + s>=m){cout << (u ? ans : "EMPTY") << endl;ok = true;return ;}int pre = 0;for(int i=0;i<26;i++){if(!tr[u][i]) continue;// 表示需要加一个分支去走ans.push_back(i+'a');dfs(tr[u][i],now+pre+s-1); // 表示在s取过了ans.pop_back();pre += sum[tr[u][i]]-1; // 表示这个字母在s取过了}
}
void solve(){cin>>n>>m;for(int i=1;i<=n;i++){cin>>s;insert();}dfs(0,0);used();return ;
}

F - Traveling in Cells

金牌题：二分+动态开点线段树+树装数组

我们有个明显的想法就是对于操作3二分找到最远左右边界即可，但是对于左右边界如果判断是不是符合集合的值难以解决，我们可以注意到 颜色的数量过多，同时还得支持颜色的修改，我们考虑使用动态开点线段树来维护，对于每一个点开出的线段树的用到的节点数量只有(n+m)logn个，我们使用这个数据结构可以维护要求，同时对于查询左右区间的贡献已经修改值都可以通过树装数组来维护,核心还是考察了动态开点线段树

int t,n,m,k,idx;
struct code{int l,r;int val;
}tr[N*40];int c[N],v[N],s[M];
int rc[N];
LL vc[N];void update(int p){tr[p].val = tr[tr[p].l].val + tr[tr[p].r].val;
}void change(int &p,int l,int r,int x,int val){if(!p) p = ++ idx;if(l==r){tr[p].val+=val;return ;}int mid = l+r>>1;if(x<=mid) change(tr[p].l,l,mid,x,val);else change(tr[p].r,mid+1,r,x,val);update(p);
}int query(int p,int l,int r,int L,int R){if(!p) return 0;if(L <= l and r <= R) return tr[p].val;int mid = l+r>>1;int res = 0;if(L<=mid) res += query(tr[p].l,l,mid,L,R);if(R>mid)  res += query(tr[p].r,mid+1,r,L,R);return res;
}
void add(int k,int x){for(int i=k;i<=n;i+=lowbit(i)) vc[i] += x;
}
LL ask(int k){LL res = 0;for(int i=k;i;i-=lowbit(i)) res += vc[i];return res;
}
bool check(int l,int r){int cnt = 0;for(int i=1;i<=k;i++)cnt += query(rc[s[i]],1,n,l,r);return cnt == r-l+1;
}
void clear(){for(int i=1;i<=n;i++) rc[i]=vc[i]=0;for(int i=1;i<=idx;i++) tr[i].l=tr[i].r=tr[i].val=0;idx = 0;
}
void solve(){clear();cin>>n>>m;for(int i=1;i<=n;i++){cin>>c[i];change(rc[c[i]],1,n,i,1);}for(int i=1;i<=n;i++){cin>>v[i];add(i,v[i]);}while(m--){int op,p,x;cin>>op;if(op==1){cin>>p>>x;change(rc[c[p]],1,n,p,-1);change(rc[x],1,n,p,1);c[p]=x;}else if(op==2){cin>>p>>x;add(p,x-v[p]);v[p]=x;}else{int pos;cin>>pos>>k;for(int i=1;i<=k;i++) cin>>s[i];LL ans = 0;int posl = pos,posr = pos;int l = 1, r = pos;while(l<r){int mid = l+r>>1;if(check(mid,pos)) r=mid;else l=mid+1; }posl = l;l = pos,r = n;while(l<r){int mid=l+r+1>>1;if(check(pos,mid)) l=mid;else r=mid-1;}posr = r;cout << ask(posr)-ask(posl-1) << endl;}}return ;
}

I - Path Planning

 铜牌题：mex + 二分

我们可以注意到题目要求路径上的mex最大，如果x是可以的那么[1-x]一定是可以的，同时如果x不可以那么[x,..]一定是不可以的，所以具有二分性质，现在核心就是二分，我们可以发现路径一定是右下的走法，也就是满足要求的j一定不会比上面满足要求的j要小否则就是往回走了，由此我们可以得到二分的写法

void solve(){cin>>n>>m;vector<vector<int>> s(n+5,vector<int>(m+5));for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>s[i][j];auto check = [&](int x){int last = 0;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(s[i][j]<x){if(j<last) return false;last = max(last,j);}return true;};int l=1,r=n*m;while(l<r){int mid=l+r+1>>1;if(check(mid)) l=mid;else r=mid-1;}cout << l << endl;return ;
}

K - Peg Solitaire

 签到-铜牌题：dfs暴力

可以注意到数据范围是很小的所以我们可以考虑直接暴力因为分支很少dfs的不会很多

按照题目意思模拟暴力即可

int ans;
int dx[]={-1,1,0,0},dy[]={0,0,1,-1};
void dfs(int cnt){ans = min(ans,cnt);if(ans==1) return ;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){if(s[i][j]){for(int u=0;u<4;u++){int a=i+dx[u],b=j+dy[u];int na=i+2*dx[u],nb=j+2*dy[u];if(1<=na and na<=n and 1<=nb and nb<=mand s[a][b] and !s[na][nb]){s[a][b]=s[i][j]=false;s[na][nb]=true;dfs(cnt-1);s[a][b]=s[i][j]=true;s[na][nb]=false;}}}}
}
void solve(){cin>>n>>m>>k;ans = k;memset(s,0,sizeof s);for(int i=1;i<=k;i++){int x,y; cin>>x>>y;s[x][y]=true;}dfs(k);cout << ans << endl;return ;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/317819.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

C——双向链表

C——双向链表

一.链表的概念及结构 链表是一种物理存储单元上非连续、非顺序的存储结构&#xff0c;数据元素的逻辑顺序是通过链表中的指针链接次序实现的。什么意思呢&#xff1f;意思就是链表在物理结构上不一定是连续的&#xff0c;但在逻辑结构上一定是连续的。链表是由一个一个的节点连…
阅读更多...
CMake使用

CMake使用

一、CMake 是什么 CMake 是一个跨平台的自动化构建系统&#xff0c;它使用配置文件 CMakeLists.txt 来管理软件构建过程。CMake 基于 Makefile 做了二次开发。 二、单个文件目录 # CMake 最低版本号要求 cmake_minimum_required(VERSION 3.16.3)# 工程名 project(CMakeSingle)…
阅读更多...
uniapp0基础编写安卓原生插件和调用第三方jar包和编写语音播报插件之使用jar包插件

uniapp0基础编写安卓原生插件和调用第三方jar包和编写语音播报插件之使用jar包插件

前言 如果你不会编写安卓插件，你可以先看看我之前零基础的文章(uniapp0基础编写安卓原生插件和调用第三方jar包和编写语音播报插件之零基础编写安卓插件)， 我们使用第三方包，jar包编写安卓插件 开始 把依赖包，放到某个模块的/libs目录（myTestPlug/libs） 还要到build…
阅读更多...
缓存分享(1)——Guava Cache原理及最佳实践

缓存分享(1)——Guava Cache原理及最佳实践

Guava Cache原理及最佳实践 1. Guava Cache是什么1.1 简介1.2 核心功能1.3 适用场景 2. Guava Cache的使用2.1 创建LoadingCache缓存2.2 创建CallableCache缓存 缓存的种类有很多&#xff0c;需要根据不同的应用场景来选择不同的cache&#xff0c;比如分布式缓存如redis、memca…
阅读更多...
Java设计模式 _结构型模式_桥接模式

Java设计模式 _结构型模式_桥接模式

一、桥接模式 1、桥接模式 桥接模式&#xff08;Bridge Pattern&#xff09;是一种结构型设计模式。用于把一个类中多个维度的抽象化与实现化解耦&#xff0c;使得二者可以独立变化。 2、实现思路 使用桥接模式&#xff0c;一定要找到这个类中两个变化的维度&#xff1a;如支…
阅读更多...
【消息队列】RabbitMQ五种消息模式

【消息队列】RabbitMQ五种消息模式

RabbitMQ RabbitMQRabbitMQ安装 常见的消息模型基本消息队列SpringAMQPWorkQueue消息预取发布订阅模式Fanout ExchangeDirectExchangeTopicExchange 消息转换器 RabbitMQ RabbitMQ是基于Erlang语言开发的开源消息通信中间件 官网地址&#xff1a;https://www.rabbitmq.com/ R…
阅读更多...
C语言趣味代码（四）

C语言趣味代码（四）

这一篇主要编写几个打字练习的小程序&#xff0c;然后通过这些小程序的实现来回顾复习我们之前学过的知识&#xff0c;然后通过这写打字练习的小程序来提升我们的打字技术和编程技术。 1. 打字练习 1.1 基本打字练习 1.1.1 基本实现 首先我们来制作一个用于计算并显示输入一…
阅读更多...
嵌入式学习59-ARM7(自动设备号和混杂设备)

嵌入式学习59-ARM7(自动设备号和混杂设备)

知识零碎&#xff1a; 头文件查找&#xff1a; /arm/路径下的头文件 linux驱动程序的编写&#xff0c;编译&#xff0c;运行过程 -------------------------------------------------------------------------------------------------------------------------------- 1.…
阅读更多...
【C语言】深入了解文件：简明指南

【C语言】深入了解文件：简明指南

&#x1f308;个人主页&#xff1a;是店小二呀 &#x1f308;C语言笔记专栏&#xff1a;C语言笔记 &#x1f308;C笔记专栏&#xff1a; C笔记 &#x1f308;喜欢的诗句:无人扶我青云志 我自踏雪至山巅 文章目录 一、文件的概念1.1 文件名:1.2 程序文件和数据文件 二、数据文…
阅读更多...
手拉手springboot整合kafka

手拉手springboot整合kafka

前期准备安装kafka 启动Kafka本地环境需Java 8以上 Kafka是一种高吞吐量的分布式发布订阅消息系统&#xff0c;它可以处理消费者在网站中的所有动作流数据。 Kafka启动方式有Zookeeper和Kraft&#xff0c;两种方式只能选择其中一种启动&#xff0c;不能同时使用。 Kafka下载…
阅读更多...
头歌：Spark的安装与使用

头歌：Spark的安装与使用

第1关&#xff1a;Scala语言开发环境的部署 相关知识 Scala是一种函数式面向对象语言&#xff0c;它融汇了许多前所未有的特性&#xff0c;而同时又运行于JVM之上。随着开发者对Scala的兴趣日增&#xff0c;以及越来越多的工具支持&#xff0c;无疑Scala语言将成为你手上一件…
阅读更多...
第5篇：创建Nios II工程之Hello_World＜四＞

第5篇：创建Nios II工程之Hello_World＜四＞

Q&#xff1a;最后我们在DE2-115开发板上演示运行Hello_World程序。 A&#xff1a;先烧录编译Quartus硬件工程时生成的.sof文件&#xff0c;在FPGA上成功配置Nios II系统&#xff1b;然后在Nios II Eclipse窗口右键点击工程名hello_world&#xff0c;选择Run As-->Nios II …
阅读更多...
如何使用Go语言进行并发安全的数据访问？

如何使用Go语言进行并发安全的数据访问？

文章目录 并发安全问题的原因解决方案1. 使用互斥锁&#xff08;Mutex&#xff09;示例代码&#xff1a; 2. 使用原子操作&#xff08;Atomic Operations&#xff09;示例代码&#xff1a; 3. 使用通道&#xff08;Channels&#xff09; 在Go语言中&#xff0c;进行并发编程是常…
阅读更多...
SpringMVC整体工作流程

SpringMVC整体工作流程

. 用户发起一个请求&#xff0c;请求首先到达前端控制器前端控制器接收到请求后会调用处理器映射器&#xff0c;由此得知&#xff0c;这个请求该由哪一个Controller来进行处理(并未调用Controller)&#xff1b;前端控制器调用处理器适配器&#xff0c;告诉处理器适配器应该要…
阅读更多...
搭建vue3组件库(三): CSS架构之BEM

搭建vue3组件库(三): CSS架构之BEM

文章目录 1. 通过 JS 生成 BEM 规范名称1.1 初始化 hooks 目录1.2 创建 BEM 命名空间函数1.3 通过 SCSS 生成 BEM 规范样式 2. 测试 BEM 规范 BEM 是由 Yandex 团队提出的一种 CSS 命名方法论&#xff0c;即 Block&#xff08;块&#xff09;、Element&#xff08;元素&#xf…
阅读更多...
qt-C++笔记之滑动条QSlider和QProgressBar进度条

qt-C++笔记之滑动条QSlider和QProgressBar进度条

qt-C笔记之滑动条QSlider和QProgressBar进度条 —— 2024-04-28 杭州 本例来自《Qt6 C开发指南》 文章目录 qt-C笔记之滑动条QSlider和QProgressBar进度条1.运行2.阅读笔记3.文件结构4.samp4_06.pro5.main.cpp6.widget.h7.widget.cpp8.widget.ui 1.运行 2.阅读笔记 3.文件结构…
阅读更多...
安装VMware Tools报错处理（SP1）

安装VMware Tools报错处理（SP1）

一、添加共享文件 因为没有VMware Tools&#xff0c;所以补丁只能通过共享文件夹进行传输了。直接在虚拟机的浏览器下载的话&#xff0c;自带的IE浏览器太老了&#xff0c;网站打不开&#xff0c;共享文件夹会方便一点&#xff0c;大家也可以用自己的方法&#xff0c;能顺利上…
阅读更多...
关于我转生从零开始学C++这件事：升级Lv.10

关于我转生从零开始学C++这件事：升级Lv.10

❀❀❀ 文章由不准备秃的大伟原创 ❀❀❀ ♪♪♪ 若有转载&#xff0c;请联系博主哦~ ♪♪♪ ❤❤❤ 致力学好编程的宝藏博主&#xff0c;代码兴国&#xff01;❤❤❤ 盘古开天辟地&#xff0c;大伟五一更新。大家好哇&#xff0c;大伟今天继续给大家来更新我们的C&#xff1a;…
阅读更多...
【Linux】进程终止

【Linux】进程终止

思维导图 学习内容 进程终止是进程控制里面的一个重要的知识&#xff0c;通过这一篇博客&#xff0c;我们可以学习到进程终止的概念&#xff0c;进程终止的三种情况&#xff0c;进程终止的退出码和退出信号&#xff0c;最后在来学习进程是如何进行终止的。 学习目标 进程终止…
阅读更多...
CTFHub-Web-文件上传

CTFHub-Web-文件上传

CTFHub-Web-文件上传-WP 一、无验证 1.编写一段PHP木马脚本 2.将编写好的木马进行上传 3.显示上传成功了 4.使用文件上传工具进行尝试 5.连接成功进入文件管理 6.上翻目录找到flag文件 7.打开文件查看flag 二、前端验证 1.制作payload进行上传发现不允许这种类型的文件上传 …
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023