2023年广东省大学生程序设计竞赛题解

2024-05-07 03:20
文章标签 竞赛题 2023 程序设计 广东省 大学生

本文主要是介绍2023年广东省大学生程序设计竞赛题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

比赛链接：The 2023 Guangdong Provincial Collegiate Programming Contest

文章目录

  • A. Programming Contest（签到）
  • B. Base Station Construction（单调队列优化dp）
  • C. Trading（排序）
  • D. New Houses（枚举+排序）
  • E. New but Nostalgic Problem（字典树）
  • F. Traveling in Cells（线段树+树状数组+二分）
  • I. Path Planning（二分）
  • K. Peg Solitaire（DFS）

A. Programming Contest（签到）

#include <bits/stdc++.h>using namespace std;#define int long long
using i64 = long long;typedef pair<int, int> PII;
typedef pair<int, char> PIC;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;
typedef pair<int, pair<int, bool>> PIIB;const int N = 10;
const int maxn = 1e6 + 10;
const int mod = 1e9 + 7;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;void solve()
{int x1, x2;cin >> x1;int x; cin >> x;vector<int> a(x);for (int i = 0; i < x; i ++ ) cin >> a[i];cin >> x2;int ans = x2 - x1 + 1;for (auto t : a){if (t >= x1 && t <= x2) ans -- ;}cout << ans << '\n';
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--){solve();}
}

B. Base Station Construction（单调队列优化dp）

设计状态 dp[i] 表示前 i 个位置满足条件，且第 i 个位置必选的最小代价，转移方程即为： d p [ i ] = min ⁡ d p [ j ] + a [ i ] dp[i]=\min{dp[j]}+a[i] dp[i]=mindp[j]+a[i]，j 需要满足的条件是， [ j , i − 1 ] [j,\ i-1] [j, i−1] 没有完整的区间限制

所以我们先在存储限制的时候记录下每个右端点对应的左端点，之后用单调队列更新当前能取的最大的 j

我们可以将 a[n + 1] 赋值为 0，这样最终答案即为 dp[n + 1]

#include <bits/stdc++.h>using namespace std;#define int long long
using i64 = long long;typedef pair<int, int> PII;
typedef pair<int, char> PIC;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;
typedef pair<int, pair<int, bool>> PIIB;const int N = 5e5 + 10;
const int maxn = 1e6 + 10;
const int mod = 1e9 + 7;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;void solve()
{int n; cin >> n;vector<int> a(n + 2);for (int i = 1; i <= n; i ++ ) cin >> a[i];a[n + 1] = 0;vector<int> dp(n + 2);int m; cin >> m;vector<int> lt(n + 2);for (int i = 1; i <= m; i ++ ){int l, r; cin >> l >> r;lt[r] = max(l, lt[r]);}deque<int> dq;dq.push_back(0);for (int i = 1; i <= n + 1; i ++ ){dp[i] = dp[dq.front()] + a[i];while (!dq.empty() && dp[dq.back()] > dp[i]) dq.pop_back();dq.push_back(i);while (!dq.empty() && dq.front() < lt[i]) dq.pop_front();}cout << dp[n + 1] << '\n';
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--){solve();}
}

C. Trading（排序）

排序即可，便宜的买，贵的卖

#include <bits/stdc++.h>using namespace std;#define int long long
using i64 = long long;typedef pair<int, int> PII;
typedef pair<int, char> PIC;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;
typedef pair<int, pair<int, bool>> PIIB;const int N = 10;
const int maxn = 1e6 + 10;
const int mod = 1e9 + 7;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;void solve()
{int n;cin >> n;vector<PII> a(n);for (int i = 0; i < n; i ++ ) cin >> a[i].first >> a[i].second;sort(a.begin(), a.end());int sum = 0;for (auto t : a) sum += t.second;int cnt = sum / 2;int sum1 = 0, sum2 = 0;for (auto t : a){if (t.second <= cnt){sum1 += t.first * t.second;cnt -= t.second;}else if (cnt > 0){sum1 += cnt * t.first;cnt = 0;break;}else if (cnt <= 0) break;} cnt = sum / 2;for (int i = n - 1; i >= 0; i -- ){if (a[i].second <= cnt){sum2 += a[i].first * a[i].second;cnt -= a[i].second;}else if (cnt > 0){sum2 += cnt * a[i].first;cnt = 0;break;}else if (cnt <= 0) break;}cout << sum2 - sum1 << '\n';
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--){solve();}
}

D. New Houses（枚举+排序）

根据二者的差值排序，然后枚举多少人没有邻居就可以了

#include <bits/stdc++.h>using namespace std;#define int long long
using i64 = long long;typedef pair<int, int> PII;
typedef pair<int, char> PIC;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;
typedef pair<int, pair<int, bool>> PIIB;const int N = 10;
const int maxn = 1e6 + 10;
const int mod = 1e9 + 7;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;void solve()
{int n, m;cin >> n >> m;vector<PII> a(n + 1);for (int i = 1; i <= n; i ++ ) cin >> a[i].first >> a[i].second;auto cmp = [&](PII a, PII b){return a.second - a.first > b.second - b.first;};sort(a.begin() + 1, a.end(), cmp);vector<int> pre1(n + 1), pre2(n + 1);for (int i = 1; i <= n; i ++ ){pre1[i] = pre1[i - 1] + a[i].first;pre2[i] = pre2[i - 1] + a[i].second;}int ans = 0;for (int i = 0; i <= n; i ++ ){int j = n - i;if (j == 1) continue;if (j == 0 && (i - 1) * 2 + 1 > m) continue;else if (j != 0 && i * 2 + j > m) continue;int res = pre2[i] + pre1[n] - pre1[i];ans = max(ans, res);}cout << ans << '\n';
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--){solve();}
}

E. New but Nostalgic Problem（字典树）

从左到右确定答案的每一位，假设我们已经确定了前三位 abc，开始枚举第四位，假设枚举到第四位为 g，那么我们的取值是怎样的呢？

首先 abc[a-g] 随便取，因为他们的公共前缀对最终答案不造成影响，然后 abc[h-z] 每种情况只能取一个，因为只要取了两个，就不能保证最终公共前缀是 abcg 了

如果这样可以选择大于等于 k 个字符串，那么答案的前缀确定是 abcg，如果不能，就要继续枚举第四个字符是其他的情况

前四位确定之后我们要看是不是只有四位呢？

如果答案只有四位的话，abcg[a-z] 每种情况最多取一个，看这样能不能取大于等于 k 个字符串，如果可以的话答案就是 abcg，不能的话再继续枚举第五位

#include <bits/stdc++.h>using namespace std;#define int long long
using i64 = long long;typedef pair<int, int> PII;
typedef pair<int, char> PIC;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;
typedef pair<int, pair<int, bool>> PIIB;const int N = 1e6 + 10;
const int maxn = 1e6 + 10;
const int mod = 1e9 + 7;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;int idx, cnt[N], st[N], tr[N][26];int newNode()
{idx++;st[idx] = cnt[idx] = 0;memset(tr[idx], 0, sizeof(tr[idx]));return idx;
}void add(string s)
{int p = 1;// cnt[p] ++ ;for (auto t : s){int c = t - 'a';if (!tr[p][c]) tr[p][c] = newNode();p = tr[p][c];cnt[p] ++ ;}st[p] ++ ;
}void solve()
{idx = 0;newNode();int n, k;cin >> n >> k;for (int i = 0; i < n; i ++ ){string s;cin >> s;add(s);}int p = 1;while (1){int tmp = st[p];for (int i = 0; i < 26; i ++ )if (cnt[tr[p][i]]) tmp ++ ;if (tmp >= k){if (p == 1) cout << "EMPTY";cout << '\n';return;}for (int i = 0; i < 26; i ++ ){if (cnt[tr[p][i]]){tmp += cnt[tr[p][i]] - 1;if (tmp >= k){k -= tmp - cnt[tr[p][i]];p = tr[p][i];cout << (char)(i + 'a');break;}}}}
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--){solve();}
}

F. Traveling in Cells（线段树+树状数组+二分）

首先看查询操作，很容易想到，就是要找包含起始点的最长子段，子段的左端点和右端点都可以通过二分找到

二分的check函数怎么写呢？以左端点为例，如果 [mid, x] 在集合内的颜色数是 x - mid + 1 个，说明这一段都是满足条件的，mid 可以继续往左搜索，否则往右搜索

现在我们需要的就是，查找 [l, r] 之间第 i 个颜色的出现次数，再把集合内的颜色累加一下得到答案，但是直接加会mle的很惨，所以考虑一下怎么优化

我们可以把所有颜色捡到一棵树上，用动态开点线段树，然后再存储一下每个颜色的树根结点，每次从这个颜色的根节点往下找就可以

最后用树状数组维护一下区间的权值和

#include <bits/stdc++.h>using namespace std;#define int long long
using i64 = long long;typedef pair<int, int> PII;
typedef pair<int, char> PIC;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;
typedef pair<int, pair<int, bool>> PIIB;const int N = 3e5 + 10;
const int maxn = 1e6 + 10;
const int mod = 1e9 + 7;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;int n;
int c[N], v[N];
int rt[N], idx;struct node
{int ls, rs, sum;
} tr[N * 10];void modify(int &u, int l, int r, int pos, int val)
{if (!u) u = ++ idx;if (l == r){tr[u].sum += val;return;}int mid = l + r >> 1;if (pos <= mid) modify(tr[u].ls, l, mid, pos, val);else modify(tr[u].rs, mid + 1, r, pos, val);tr[u].sum = tr[tr[u].ls].sum + tr[tr[u].rs].sum;
}int query(int u, int l, int r, int ql, int qr)
{if (!u) return 0;if (l >= ql && r <= qr) return tr[u].sum;int mid = l + r >> 1;int res = 0;if (ql <= mid) res += query(tr[u].ls, l, mid, ql, qr);if (qr > mid) res += query(tr[u].rs, mid + 1, r, ql, qr);return res;
}int ttr[N];int lowbit(int x)
{return x & -x;
}void add(int pos, int val)
{for (int i = pos; i <= n; i += lowbit(i))ttr[i] += val;
}int get_sum(int pos)
{int res = 0;for (int i = pos; i > 0; i -= lowbit(i)) res += ttr[i];return res;
}int get_sum(int l, int r)
{return get_sum(r) - get_sum(l - 1);
}vector<int> cq;bool check(int l, int r, int cnt)
{int res = 0;for (auto t : cq)res += query(rt[t], 1, n, l, r);return res == cnt;
}void get_ans()
{int st, k;cin >> st >> k;cq.clear();for (int i = 1; i <= k; i ++ ){int xx; cin >> xx;cq.push_back(xx);}sort(cq.begin(), cq.end());cq.erase(unique(cq.begin(), cq.end()), cq.end());int l = 1, r = n;int lr = st, rl = st;while (l < lr){int mid = l + lr >> 1;if (check(mid, st, st - mid + 1)) lr = mid;else l = mid + 1;}while (rl < r){int mid = rl + r + 1 >> 1;if (check(st, mid, mid - st + 1)) rl = mid;else r = mid - 1;}cout << get_sum(l, r) << '\n';
}void clear()
{for (int i = 0; i <= idx; i++)tr[i] = {0, 0, 0};for (int i = 1; i <= n; i++)rt[i] = ttr[i] = 0;idx = 0;
}void solve()
{clear();int q;cin >> n >> q;for (int i = 1; i <= n; i ++ ){cin >> c[i];modify(rt[c[i]], 1, n, i, 1);}for (int i = 1; i <= n; i ++ ){cin >> v[i];add(i, v[i]);}while (q -- ){int op, pos, x;cin >> op;if (op == 1){cin >> pos >> x;modify(rt[c[pos]], 1, n, pos, -1);c[pos] = x;modify(rt[c[pos]], 1, n, pos, 1);}else if (op == 2){cin >> pos >> x;add(pos, x - v[pos]);v[pos] = x;}else get_ans();}
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--){solve();}
}

I. Path Planning（二分）

输入的时候存储每一个数字所在的位置，然后二分，把路径存储下来，按 x 排序，判断 y 有没有不合理的地方即可

#include <bits/stdc++.h>using namespace std;#define int long long
using i64 = long long;typedef pair<int, int> PII;
typedef pair<int, char> PIC;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;
typedef pair<int, pair<int, bool>> PIIB;const int N = 10;
const int maxn = 1e6 + 10;
const int mod = 1e9 + 7;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;void solve()
{int n, m;cin >> n >> m;vector<PII> pos(n * m);for (int i = 1; i <= n; i ++ )for (int j = 1; j <= m; j ++ ){int x; cin >> x;pos[x] = {i, j};}auto check = [&](int x){vector<PII> v;for (int i = 0; i < x; i ++ ){v.push_back(pos[i]);}sort(v.begin(), v.end());int tmp = v[0].second;for (int i = 1; i < v.size(); i ++ ){if (v[i].second < tmp) return false;tmp = v[i].second;}return true;};int l = 0, r = n * m;while (l < r){int mid = l + r + 1 >> 1;if (check(mid)) l = mid;else r = mid - 1;}cout << r << '\n';
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--){solve();}
}

K. Peg Solitaire（DFS）

数据范围特别小，所以直接打暴力即可

#include <bits/stdc++.h>using namespace std;#define int long long
using i64 = long long;typedef pair<int, int> PII;
typedef pair<int, char> PIC;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;
typedef pair<int, pair<int, bool>> PIIB;const int N = 10;
const int maxn = 1e6 + 10;
const int mod = 1e9 + 7;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};void solve()
{int n, m, k;cin >> n >> m >> k;vector<vector<int>> g(n + 1, vector<int>(m + 1));vector<vector<int>> st(n + 1, vector<int>(m + 1, -1));for (int i = 0; i < k; i ++ ){int x, y;cin >> x >> y;g[x][y] = 1;}int res = 0;int ans = 0;function<void(int, int)> dfs = [&](int x, int y){for (int i = 0; i < 4; i ++ ){int nx = x + dx[i], ny = y + dy[i];int nnx = nx + dx[i], nny = ny + dy[i];if (nx <= 0 || ny <= 0 || nx > n || ny > m) continue;if (nnx <= 0 || nny <= 0 || nnx > n || nny > m) continue;if (g[nx][ny] == 1 && g[nnx][nny] == 0){g[x][y] = 0;g[nx][ny] = 0;g[nnx][nny] = 1;res ++ ;ans = max(ans, res);for (int ii = 1; ii <= n; ii ++ ){for (int jj = 1; jj <= m; jj ++ ){if (g[ii][jj] == 1) dfs(ii, jj);}}g[x][y] = 1;g[nx][ny] = 1;g[nnx][nny] = 0;res -- ;}}};for (int i = 1; i <= n; i ++ )for (int j = 1; j <= m; j ++ )if (g[i][j] == 1) dfs(i, j);cout << k - ans << '\n';
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--){solve();}
}

这篇关于2023年广东省大学生程序设计竞赛题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/966183。

相关文章

CVE-2023-37474（目录遍历）

CVE-2023-37474（目录遍历）

靶场简介 Copyparty是一个可移植的文件服务器。在1.8.2版本之前的版本存在一个CTF技巧，该漏洞位于`.cpr`子文件夹中。路径遍历攻击技术允许攻击者访问位于Web文档根目录之外的文件、目录. 靶场 进入靶场 根据简介访问.cpr目录 使用curl命令访问etc/passwd文件 确定存在目录遍历漏洞 直接访问flag 得到flag{e775aaa4-1d
阅读更多...
大学生如何学习node.js?

大学生如何学习node.js?

1. 学习 JavaScript 基础知识 语法：变量、数据类型、操作符、控制结构（if、switch、loops）。函数：定义、调用、参数、作用域。对象和原型：对象字面量、构造函数、继承。数组：方法（map、filter、reduce）、迭代。ES6+ 特性：箭头函数、模板字符串、解构赋值、Promises、async/await。 2. 安装 Node.js 从官网下载适合你操作系统的版
阅读更多...
【2023】LitCTF

【2023】LitCTF

LitCTF2023（复现） Web： 1、我Flag呢？ ​ ctrl+u 读取源码，在最后发现了flag： <!--flag is here flag=NSSCTF{3d5218b9-4e24-4d61-9c15-68f8789e8c48} --> 2、PHP是世界上最好的语言！！ ​ 右边那个框下面是 RUN CODE ，结合题目是PHP，推测为RCE，先输入echo 12
阅读更多...
新技术前沿-2023-大模型的本质

新技术前沿-2023-大模型的本质

大模型时代需要什么样的人才？ 1 大模型的本质 特斯拉前AI总监Andrej Karpathy的新教程，涵盖模型推理、训练、微调和新兴大模型操作系统以及安全挑战。 1.1 大模型本质就是两个文件 首先，大模型是什么？ 大模型本质就是两个文件： 一个是参数文件，一个是包含运行这些参数的代码文件。 前者是组成整个神经网络的权重，后者是用来运行这个神经网络的代码，可以是C或者其他任何编程语言写的
阅读更多...
数据中心智能化运维发展研究报告（2023）解读

数据中心智能化运维发展研究报告（2023）解读

数据中心智能化运维发展研究报告（2023）解读 《数据中心智能化运维发展研究报告（2023）》探讨了数据中心智能化运维的概念、核心内容、实际应用和发展建议。报告指出，通过人工智能、大数据等新一代信息技术的深度应用，实现设施自动化运行、平台智能化管理、体系精细化落地和服务价值化输出，从而提升数据中心运维的效率和质量，推动数据中心向精细化、绿色化和智能化方向发展。 数据中心智能化运维发展研究报告（
阅读更多...
大学生如何学习JavaScript？

大学生如何学习JavaScript？

学习 JavaScript 对于大学生来说是一个宝贵的技能，因为它是现代网页开发的核心语言之一。以下是一些详细的步骤，帮助大学生学习 JavaScript： 1. 了解 Web 开发基础 学习 HTML 和 CSS，这是网页开发的基石。 2. 学习 JavaScript 基础 语法：变量、数据类型、操作符、控制语句（if、for、while）。函数：如何声明、调用函数，理解参数和返回值。数
阅读更多...
北航第五次数据结构与程序设计编程题复习

北航第五次数据结构与程序设计编程题复习

北航第五次数据结构与程序设计编程题复习 树叶节点遍历（树-基础题）计算器（表达式计算-表达式树实现）服务优化词频统计（树实现） 树叶节点遍历（树-基础题） 【问题描述】 从标准输入中输入一组整数，在输入过程中按照左子结点值小于根结点值、右子结点值大于等于根结点值的方式构造一棵二叉查找树，然后从左至右输出所有树中叶结点的值及高度（根结点的高度为1）。例如，若按照以下顺序输入一组整
阅读更多...
大学生如何学习Web前端

大学生如何学习Web前端

基础学习： 学习HTML（超文本标记语言），它是构建网页内容的基础。学习CSS（层叠样式表），用于设置网页的布局和样式。 实践操作： 通过编写简单的网页来实践HTML和CSS，理解它们是如何一起工作的。 JavaScript入门： 学习JavaScript，这是Web前端开发中实现交互性的关键技术。 响应式设计： 学习如何使用CSS媒体查询来创建响应式网页设计，使网页能够适应不同的设备和屏幕尺寸
阅读更多...
上市公司-市场竞争程度（1999-2023年）赫份达尔、勒纳指数数据集

上市公司-市场竞争程度（1999-2023年）赫份达尔、勒纳指数数据集

数据年份：1999-2023年 有效样本：64505条 数据来源：上市公司年报 数据说明： ① 在行业层面，赫芬达尔指数可衡量一个公司在市场中的相对份额或集中度。它是由每家公司在市场中份额的平方和得到的。指数值越高，表示该市场或行业的集中度越高，竞争可能相对较小。 ② 在企业维度，勒纳指数可用于刻画企业在产品市场的定价能力。计算公式为： 勒纳指数=(企业营业收入-营业成本－销售费用－
阅读更多...
大学生学习Java路线2024版

大学生学习Java路线2024版

第一阶段：基础入门 了解计算机基础： 学习基本的计算机科学知识，如操作系统、数据结构和算法。 Java语言概述： 了解Java语言的历史、特点和应用领域。 安装开发环境： 安装JDK和IDE（如IntelliJ IDEA或Eclipse）。 Java基础语法： 学习变量、数据类型、运算符、控制流（if-else, loops, switch-case）。 面向对象编程： 理解类和对象、封装、继
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2