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

news/2024/5/20 17:29:11

目录

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.mrgr.cn/p/32052831

相关文章

实现队列 栈 双端队列

以下都是用list来实现的实现Stack# Implement a Stack in Python class Stack(object):def __init__(self):self.items = []def is_empty(self):return self.items == []def push(self, item):self.items.append(item)def pop(self):return self.items.pop()def peek(self):ret…

微信小程序之搜索框样式(带源码)

一、效果图&#xff1a; 点击搜索框&#xff0c;“请输入搜索内容消失”&#xff0c;可输入关键字 二、代码&#xff1a; 2.1、WXML代码&#xff1a; <!--搜索框部分--><view class"search"><view class"search-btn">&#x1f50d;&l…

数据库加密数据模糊匹配查询技术方案

文章目录 前言沙雕方案内存加载解密密文映射表 常规做法实现数据库加密算法参考 分词组合加密&#xff08;推荐&#xff09; 超神方案总结个人简介 前言 在数据安全性和查询效率之间找到平衡是许多数据管理系统所面临的挑战之一。特别是在涉及加密数据的情况下&#xff0c;如何…

IP协议,网络层

一、IP协议报文 在网络层最主要的协议是IP协议&#xff0c;网络层的主要任务是进行&#xff1a;1.地址管理 2.路由选择 地址管理&#xff1a;使用一套地址体系&#xff0c;描述互联网中每个设备所处的位置。 IP地址有两个版本&#xff0c;1.IPV4 2.IPV6 &#xff0c;IP…

uiautomator2使用方法

一.设备连接 1.usb单设备连接d = u2.connect()2.usb多设备连接d = u2.connect("90bf8faf") # 多台设备填写device即可3.wifi连接d = u2.connect("ip:proxy") # wifi连接设备adb使用wifi连接设备:https://www.cnblogs.com/lihongtaoya/p/17553171.html 二…

W801学习笔记二十:宋词学习应用

前三章完成了唐诗的应用&#xff0c;本章将实现宋词的学习应用。 宋词与唐诗的区别不大&#xff0c;马上开始。 1、我们需要参考前面唐诗的方式&#xff0c;把宋词文本下载下来&#xff0c;并进行格式整理。 W801学习笔记十七&#xff1a;古诗学习应用——上 2、在菜单中添加…

查看、删除数据库

#删除和查询数据库 #查看当前数据库服务器中的所有数据库 show databases #查看hsp_db01数据库的定义信息 show create database `hsp_db01` #在创建数据库,表的时候为了规避关键字,可以用``反引号解决 #删除数据库hsp_db01 drop database hsp_db01

element-ui使用el-date-picker日期组件常见场景

开始 最近一直在使用 element-ui中的日期组件。 所以想对日期组件常用的做一个简单的总结; 1.处理日期组件选择的时候面板联动问题 2.限制时间范围解除两个日期面板之间的联动 我们发现2个日期面板之间其实是有联动关系的; 开始时间面板和结束时间面板始终只能相邻; 不能出…

[鸟哥私房菜]4.首次登录与在线求助

第4章 首次登录与在线求助 4.1.3 X Window 与命令行模式的切换 通常我们称命令行界面为终端界面、Terminal 或 Console。Linux 默认的情况下会提供六个终端(Terminal)来让用户登录, 切换的方式为使用:[Ctrl] + [Alt] + [F1]~[F6] 的组合按钮。其中 [Ctrl] + [Alt] + [F1] 为…

vue3项目引入VueQuill富文本编辑器(成功)及 quill-image-uploader 图像模块(未成功)

tip&#xff1a;重点解释都写在代码注释里了&#xff0c;方便理解&#xff0c;所以看起来比较密集 富文本基本使用 项目文件夹路径安装依赖 npm install vueup/vue-quilllatest --save 全局注册&#xff1a;main.js // main.js// 自己项目的一些配置&#xff08;只放了主要…

vue+ant-design+formBuiler表单构建器——技能提升——form design——亲测有效

最近看到后端同事在弄一个后台管理系统&#xff0c;额&#xff0c;前端真的是夹缝中生存啊&#xff0c;AI抢饭碗&#xff0c;后端也想干前端的活儿。。。 他用到了表单构建器&#xff0c;具体效果如下: 网上有很多适用于ElementUi和ant-design的form design插件&#xff0c;下…

wePWNise:一款功能强大的红队Office宏VBA代码生成工具

关于wePWNise wePWNise是一款功能强大的Office宏VBA代码生成工具&#xff0c;该工具基于纯Python开发&#xff0c;可以帮助广大研究人员生成用于Office宏或模版的VBA代码&#xff0c;并以此来测试目标Office环境、应用程序控制和防护机制的安全性。 wePWNise的设计理念将自动化…

20211317李卓桐 Exp6 MSF攻防实践 实验报告

Exp6 MSF攻防实践 实践内容本实践目标是掌握metasploit的基本应用方式,重点常用的三种攻击方式的思路。具体需要完成: 1.1一个主动攻击实践,尽量使用最新的类似漏洞; 1.2 一个针对浏览器的攻击,尽量使用最新的类似漏洞; 1.3 一个针对客户端的攻击,如Adobe或office,尽量使…

深入理解Django:中间件与信号处理的艺术

title: 深入理解Django:中间件与信号处理的艺术 date: 2024/5/9 18:41:21 updated: 2024/5/9 18:41:21 categories:后端开发tags:Django 中间件 信号 异步 性能 缓存 多语言引言 在当今的Web开发领域,Django以其强大的功能、简洁的代码结构和高度的可扩展性,已成为众多开发者…

JAVA链表相关习题2

1.反转一个单链表。 . - 力扣&#xff08;LeetCode&#xff09; //2在1前面 //1在3前面 //ListNode curhead.next //head.nextnull(翻转后头节点变为最后一个节点) // while(cur ! null) { //记录 当前需要翻转节点的下一个节点 ListNode curNext cu…

零知识证明: Tornado Cash 项目学习

前言 最近在了解零知识证明方面的内容,这方面的内容确实不好入门也不好掌握,在了解了一些基础的概念以后,决定选择一个应用了零知识证明的项目来进行进一步的学习。最终选择了 Tornado Cash 这个项目,因为它著名且精致,适合入门的同学进行学习。 学习 Tornado Cash 项目,…

高并发秒杀项目随手笔记

1 数据库基字符集为什么选择utf8mb4? 2 在 MyBatis 中,JavaBean 属性名和数据库字段名的映射非常关键,正确设置这一映射是保证数据正确封装到 JavaBean 中的前提。以下是 MyBatis 映射机制的详细解释: 1. 默认映射行为 如果在 MyBatis 的 <resultMap> 中没有明确指定…

创建数据库

#数据库的操作 #删除数据库指令 DROP DATABASE hsp_db01;#hsp_db01这个对应的是数据 #用指令创建数据库 CREATE DATABASE hsp_db01; #创建一个使用utf8字符集的hsp_db02数据库 CREATE DATABASE hsp_db02 CHARACTER SET utf8 #创建一个使用utf8字符集,并带校队规则的hsp_db03数…

前后端数据交互形式随手笔记

注解@RequestParam Map<String, String> params 的使用1 在Spring MVC中,使用@RequestParam Map<String, String> params可以接收前端发出的请求参数并将它们作为一个Map收集起来。这种方式非常灵活,可以处理来自前端的各种数据提交形式。以下是一些常见的前端数…

【华为】AC直连二层组网隧道转发实验配置

【华为】AC直连二层组网隧道转发实验配置 实验需求拓扑配置AC数据规划表 AC的配置顺序AC1基本配置(二层通信)AP上线VAP组关联--WLAN业务流量 LSW1AR1STA获取AP的业务流量 配置文档 实验需求 AC组网方式&#xff1a;直连二层组网。 业务数据转发方式&#xff1a;隧道转发。 DHC…