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。

相关文章

CSP 2023 提高级第一轮 CSP-S 2023初试题 完善程序第二题解析 未完

CSP 2023 提高级第一轮 CSP-S 2023初试题 完善程序第二题解析 未完

一、题目阅读 （最大值之和）给定整数序列 a0,⋯,an−1，求该序列所有非空连续子序列的最大值之和。上述参数满足 1≤n≤105 和 1≤ai≤108。 一个序列的非空连续子序列可以用两个下标 ll 和 rr（其中0≤l≤r<n0≤l≤r<n）表示，对应的序列为 al,al+1,⋯,ar​。两个非空连续子序列不同，当且仅当下标不同。 例如，当原序列为 [1,2,1,2] 时，要计算子序列 [
阅读更多...
HNU-2023电路与电子学-实验3

HNU-2023电路与电子学-实验3

写在前面： 一、实验目的 1.了解简易模型机的内部结构和工作原理。 2.分析模型机的功能，设计 8 重 3-1 多路复用器。 3.分析模型机的功能，设计 8 重 2-1 多路复用器。 4.分析模型机的工作原理，设计模型机控制信号产生逻辑。 二、实验内容 1.用 VERILOG 语言设计模型机的 8 重 3-1 多路复用器； 2.用 VERILOG 语言设计模型机的 8 重 2-1 多
阅读更多...
C语言程序设计(数据类型、运算符与表达式)

C语言程序设计(数据类型、运算符与表达式)

一、C的数据类型 C语言提供的数据类型： 二、常量和变量 2.1常量和符号常量 在程序运行过程中，其值不能被改变的量称为常量。 常量区分为不同的类型： 程序中用＃define（预处理器指令）命令行定义变量将代表常量，用一个标识符代表一个常量，称为符合常量。 2.2变量 变量代表内存中具有特定属性的一个存储单元，用来存放数据，在程序运行期间，这些值是可以 改变的。 变
阅读更多...
C语言程序设计(选择结构程序设计)

C语言程序设计(选择结构程序设计)

一、关系运算符和关系表达式 1.1关系运算符及其优先次序 ①＜（小于） ②＜＝（小于或等于） ③＞（大于） ④＞＝（大于或等于 ） ⑤＝＝（等于） ⑥！＝（不等于） 说明： 前4个优先级相同，后2个优先级相同，关系运算符的优先级低于算术运算符，关系运算符的优先级高于赋值运算符 1.2关系表达式 用关系运算符将两个表达式（可以是算术表达式或关系表达式，逻辑表达式，赋值表达式，字符
阅读更多...
如何打造个性化大学生线上聊天交友系统？Java SpringBoot Vue教程，2025最新设计思路

如何打造个性化大学生线上聊天交友系统？Java SpringBoot Vue教程，2025最新设计思路

✍✍计算机编程指导师 ⭐⭐个人介绍：自己非常喜欢研究技术问题！专业做Java、Python、微信小程序、安卓、大数据、爬虫、Golang、大屏等实战项目。 ⛽⛽实战项目：有源码或者技术上的问题欢迎在评论区一起讨论交流！ ⚡⚡ Java实战 | SpringBoot/SSM Python实战项目 | Django 微信小程序/安卓实战项目 大数据实战项目 ⚡⚡文末获取源码 文章目录
阅读更多...
智能工厂程序设计 之1 智能工厂都本俱的方面（Facet，Aspect和Respect）即智能依赖的基底Substrate 之1

智能工厂程序设计 之1 智能工厂都本俱的方面（Facet，Aspect和Respect）即智能依赖的基底Substrate 之1

Q1、昨天分别给出了三个智能工厂的 “面face”（里面inter-face，外面outer-face和表面surface） 以及每个“面face” 各自使用的“方”（StringProcessor，CaseFilter和ModeAdapter）  。今天我们将继续说说三个智能工厂的“方面” 。在展开之前先看一下三个单词：面向facing，取向oriented，朝向toword。理解这三个词 和
阅读更多...
2024 年高教社杯全国大学生数学建模竞赛题目——2024 年高教社杯全国大学生数学建模竞赛题目的求解

2024 年高教社杯全国大学生数学建模竞赛题目——2024 年高教社杯全国大学生数学建模竞赛题目的求解

2024 年高教社杯全国大学生数学建模竞赛题目 （请先阅读“ 全国大学生数学建模竞赛论文格式规范 ”） 2024 年高教社杯全国大学生数学建模竞赛题目 随着城市化进程的加快、机动车的快速普及， 以及人们活动范围的不断扩大，城市道 路交通拥堵问题日渐严重，即使在一些非中心城市，道路交通拥堵问题也成为影响地方经 济发展和百姓幸福感的一个“痛点”，是相关部门的棘手难题之一。 考虑一个拥有知名景区
阅读更多...
2024 年高教社杯全国大学生数学建模竞赛 C 题 农作物的种植策略 参考论文 无水印

2024 年高教社杯全国大学生数学建模竞赛 C 题 农作物的种植策略 参考论文 无水印

持续更新中，2024年数学建模比赛思路代码论文都会发布到专栏内，只需订阅一次！  完整论文+代码+数据结果链接在文末！  订阅后可查看参考论文文件 第一问 1.1 问题重述 这个问题围绕的是华北山区的某乡村，在有限的耕地条件下，如何制定最优的农作物种植策略。乡村有 34 块露天耕地和 20 个大棚，种植条件包括粮食作物、蔬菜、水稻和食用菌。除了要考虑地块的面积、种植季节等，还要确保
阅读更多...
2024年全国大学生数学建模A题借鉴论文

2024年全国大学生数学建模A题借鉴论文

问题  1： 舞龙队的动态位置与速度计算 1. **螺旋线的几何建模**：根据题目描述，舞龙队沿着等距螺旋线前进。螺旋线的螺距为 55 cm， 需根据极坐标公式确定每节板凳的位置。 -  极坐标螺旋线方程：\( r = a + b\theta \)， 其中  \( b \)  是螺距， 可以利用该方程计算 每秒舞龙队的各个节数的坐标。 2. **速度计算**：给定龙头的行进速度为 1 m/s ，
阅读更多...
C语言程序设计 笔记代码梳理 重制版

C语言程序设计 笔记代码梳理 重制版

前言 本篇以笔记为主的C语言详解，全篇一共十章内容，会持续更新基础内容，争取做到更详细。多一句没有，少一句不行!  形而上学者谓之道，形而下学者谓之器 形而上学者谓之道，形而下学者谓之器 第1章 C语言的流程 1.C程序经历的六个阶段 编辑(Edit)预处理(Preprocess)编译(Compile)汇编(Assemble)链接(Link)执行(Execute)  2.
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2