2024 National Invitational of CCPC (Zhengzhou)(CCPC郑州邀请赛暨CCPC河南省赛)

本文主要是介绍2024 National Invitational of CCPC (Zhengzhou)(CCPC郑州邀请赛暨CCPC河南省赛),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

2024 National Invitational of CCPC (Zhengzhou)

2024CCPC郑州邀请赛暨CCPC河南省赛

2024 National Invitational of CCPC (Zhengzhou)
在这里插入图片描述

B. 扫雷 1

题意:扫n轮雷,每轮开始获得一枚扫雷币,可保存,从第一轮开始,可以决定在任意轮进行任意次扫雷,但过去的轮数不能返回,第i轮需要花费 c i c_i ci枚扫雷币扫雷一次,n轮最多扫多少雷。

思路:记录一个最便宜的扫雷后缀,遇见当前后缀最便宜的就开始买。

AC code:

void solve() {int n; cin >> n;for (int i = 1; i <= n; i ++) cin >> a[i];r[n + 1] = INF;for (int i = n; i >= 1; i --) {r[i] =  min(r[i + 1], a[i]);}int cnt = 0, now = 0;for (int i = 1; i <= n; i ++) {now ++;if (a[i] == r[i]) {cnt += now / a[i];now -= (now / a[i]) * a[i];}}cout << cnt << endl;
}

F. 优秀字符串

题意:略;

思路:照着题意模拟即可;

AC code:

void solve() {int n; cin >> n;int cnt = 0;while (n --) {string s; cin >> s;if (s.size() != 5) continue;if (s[2] != s[4]) continue;bool flag = 1;for (int i = 0; i < 4; i ++) for (int j = i + 1; j < 4; j ++) {if (s[i] == s[j]) flag = 0;}if (flag) cnt ++;}cout << cnt << endl;
}

H. 随机栈

题意:给出一个空栈,还有一个操作序列,当当前操作元素不为-1时,将该元素压入栈中,否则取出一个栈中元素,取出当前栈中每个元素的概率是相同的,求最终取出元素序列为非递减的概率是多少,结果对998244353取模。

思路:模拟这个过程可以用优先队列来解决,当前栈中的元素总数为分母,当前队头的最小元素的数量即为分子,该数量可以用map来记录,计算不同分数的积并进行取模;

注意,运算过程中需要对各分数进行逆元取模运算,即分子*分母的逆元的过程不断累乘,过程中注意取模;

AC code:

int qmi(int a, int k, int p) {int res = 1;while (k) {if (k & 1) res = res * a % p;a = a * a % p;k >>= 1;} return res;
}void solve() {int n; cin >> n;map<int, int> mp;priority_queue<int, vector<int>, greater<int>> q;int x = 1, y = 1;int ans = qmi(1, MOD - 2, MOD);for (int i = 1; i <= 2*n; i ++) {cin >> a[i];} int last = -1;for (int i = 1; i <= 2*n; i ++) {if (a[i] == -1) {int t = q.top();if (last <= t) last = t;else {cout << 0 << endl;return;}int xx = mp[t], yy = q.size();int gd = gcd(xx, yy);//cout << xx << ' ' << yy <<' ' << gd << endl;ans = ((ans * xx) % MOD) * qmi(yy, MOD - 2, MOD) % MOD;mp[t] --;q.pop();} else {q.push(a[i]);mp[a[i]] ++;}}cout << ans % MOD << endl;
}

J. 排列与合数

题意:给出一个五位数字,重排后在没有前导零的情况下是否可能出现合数;

思路:预处理一下五位的合数,O1进行判断,然后DFS跑一下五位数的全排列即可;

AC code:

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
#define fast() ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;typedef long long LL;
typedef pair<int, int> PII;
const int N = 2e5+10, M = 2001;
const int INF = 0x3f3f3f3f3f, MOD = 998244353;
int T;
int n, ans;
int a[N], b[N], st[10];
bool p[N];bool iprime(int x) {if (x == 1) return false;for (int i = 2; i <= x / i; i ++) {if (x % i == 0) {return true;}} return false;
}void dfs(string aim, string s) {if (ans != -1) return;if (aim.size() == 5) {int cnt = 0, tt = 10000;if (aim[0] == '0') return;for (int i = 0; i < 5; i ++) {cnt += (aim[i] - '0') * tt;tt /= 10;}if (p[cnt]) {ans = cnt;return;}return;}for (int i = 0; i < 5; i ++) {if (!st[i]) {st[i] = 1;aim += s[i];dfs(aim, s);aim.pop_back();st[i] = 0; }}
}void solve() {string s; cin >> s;for (int i = 0; i < 5; i ++) st[i] = 0;string ss = "";ans = -1;dfs(ss, s);cout << ans << endl;
}signed main() {fast();T = 1;for (int i = 1; i < 100000; i ++) {if (iprime(i)) p[i] = 1;else p[i] = 0;}cin >> T;while (T --) {solve();}return 0;
}

K. 树上问题

题意:n个结点的无根树,每个结点有一个正权值,美丽节点的定义为,以当前节点为根时,除根节点外的所有节点,其点权不小于父节点的一半,计算有多少美丽节点。

思路:

首先初始就满足x * 2 >= y的节点y一定可以为x的父节点,即有一条有向边,若两个点互相可为父节点,则这两点可以由并查集记录为同一点在图中存在;

现在统计每个点当前可能的父节点,并根据上述情况合并到同一并查集中,记录每个连通块的大小;

然后通过DFS进行记录各点的出度,出度为0的点即为可能的根节点,注意在统计过程中进行标记防止重复统计;

注意,如果存在某一点的出度大于1,则该连通图必然不可能存在美丽节点。

AC code:

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
#define fast() ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;typedef long long LL;
typedef pair<int, int> PII;
const int N = 2e5+10, M = 2001;
const int INF = 0x3f3f3f3f3f, MOD = 998244353;
int T;
int n;
int a[N], f[N], d[N];
vector<int> g[N];
map<int, int> mp, pos;int find(int x) {if (f[x] != x) f[x] = find(f[x]);return f[x];
}void dfs(int u, int v) {for (auto t : g[u]) {if (t == v) continue;dfs(t, u);int fu = find(u), ft = find(t);if (fu == ft) continue;if (a[t] * 2 >= a[u] && a[u] * 2 >= a[t]) continue;else if (a[t] * 2 >= a[u]) d[ft] ++;else if (a[u] * 2 >= a[t]) d[fu] ++;else d[ft] ++, d[fu] ++;}
}void solve() {cin >> n;mp.clear();pos.clear();for (int i = 1; i <= n; i ++) {cin >> a[i];f[i] = i;d[i] = 0;g[i].clear();}for (int i = 1; i < n; i ++) {int u, v; cin >> u >> v;g[u].push_back(v);g[v].push_back(u);int fu = find(u), fv = find(v);if (a[u] * 2 >= a[v] && a[v] * 2 >= a[u]) {f[f[u]] = fv;}}for (int i = 1; i <= n; i ++) {mp[find(i)] ++;}dfs(1, -1);int ans = 0;for (int i = 1; i <= n; i ++) {if (d[find(i)] > 1) {cout << 0 << endl;return;}if (d[find(i)] || pos[find(i)]) continue;pos[find(i)] ++;ans += mp[find(i)];}cout << ans << endl;
}signed main() {fast();T = 1;cin >> T;while (T --) {solve();}return 0;
}

L. Toxel 与 PCPC II

题意:总共n行代码,已知m行有bug,扫描一行需要一秒,同时处理x个bug需要 x 4 x^4 x4秒,最短多少秒可以完成;

思路:dp,在更新每个点的最短debug时间时最多不会超过同时处理30个bug;

AC code:

int qmi (int a, int k) {int res = 1;while (k) {if (k & 1) res = res * a;a = a * a;k >>= 1;} return res;
}void solve() {int n, m; cin >> n >> m;vector<int> a(m + 10), dp(m + 10, INF);dp[0] = 0;for (int i = 1; i <= m; i ++) cin >> a[i];for (int i = 1; i <= m; i ++) {for (int j = i - 1; j >= max(0LL, i - 30); j --) {dp[i] = min(dp[i], dp[j] + a[i] + qmi(i - j, 4));}}cout << dp[m] << endl;
}  

M. 有效算法

题意:给出长度为n的序列a和b,对于每个a元素进行一次操作满足|ai - x| <= k * bi的任意整数x,求出最小的非负整数k,满足至少存在一种方法的操作后所有a元素相等

思路:二分即可,对于check函数每次x都会有一个左右边界,不断缩小左右边界,x只要出现在该范围内均符合条件,若出现r>l边界的情况则直接返回false,注意二分边界,最多开到1e9,不然会炸(血的教训)。

AC code:

bool check (int k) {int l = -INF, r = INF;for (int i = 1; i <= n; i ++) {int now = k * b[i];int ll = a[i] - now, rr = a[i] + now;l = max(l, ll);r = min(r, rr);if (l > r) return false;}return true;
}void solve() {cin >> n;for (int i = 1; i <= n; i ++) cin >> a[i];for (int i = 1; i <= n; i ++) cin >> b[i];int l = 0, r = 1e9;while (l < r) {int mid = l + r >> 1;if (check(mid)) r = mid;else l = mid + 1;}cout << r << endl;
}

PS:有没有佬有A的写法QAQ

这篇关于2024 National Invitational of CCPC (Zhengzhou)(CCPC郑州邀请赛暨CCPC河南省赛)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/989067

相关文章

2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题

题库来源:安全生产模拟考试一点通公众号小程序 2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题是由安全生产模拟考试一点通提供,流动式起重机司机证模拟考试题库是根据流动式起重机司机最新版教材,流动式起重机司机大纲整理而成(含2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题参考答案和部分工种参考解析),掌握本资料和学校方法,考试容易。流动式起重机司机考试技

【专题】2024飞行汽车技术全景报告合集PDF分享(附原数据表)

原文链接: https://tecdat.cn/?p=37628 6月16日,小鹏汇天旅航者X2在北京大兴国际机场临空经济区完成首飞,这也是小鹏汇天的产品在京津冀地区进行的首次飞行。小鹏汇天方面还表示,公司准备量产,并计划今年四季度开启预售小鹏汇天分体式飞行汽车,探索分体式飞行汽车城际通勤。阅读原文,获取专题报告合集全文,解锁文末271份飞行汽车相关行业研究报告。 据悉,业内人士对飞行汽车行业

高效录音转文字:2024年四大工具精选!

在快节奏的工作生活中,能够快速将录音转换成文字是一项非常实用的能力。特别是在需要记录会议纪要、讲座内容或者是采访素材的时候,一款优秀的在线录音转文字工具能派上大用场。以下推荐几个好用的录音转文字工具! 365在线转文字 直达链接:https://www.pdf365.cn/ 365在线转文字是一款提供在线录音转文字服务的工具,它以其高效、便捷的特点受到用户的青睐。用户无需下载安装任何软件,只

2024网安周今日开幕,亚信安全亮相30城

2024年国家网络安全宣传周今天在广州拉开帷幕。今年网安周继续以“网络安全为人民,网络安全靠人民”为主题。2024年国家网络安全宣传周涵盖了1场开幕式、1场高峰论坛、5个重要活动、15场分论坛/座谈会/闭门会、6个主题日活动和网络安全“六进”活动。亚信安全出席2024年国家网络安全宣传周开幕式和主论坛,并将通过线下宣讲、创意科普、成果展示等多种形式,让广大民众看得懂、记得住安全知识,同时还

2024/9/8 c++ smart

1.通过自己编写的class来实现unique_ptr指针的功能 #include <iostream> using namespace std; template<class T> class unique_ptr { public:         //无参构造函数         unique_ptr();         //有参构造函数         unique_ptr(

论文翻译:arxiv-2024 Benchmark Data Contamination of Large Language Models: A Survey

Benchmark Data Contamination of Large Language Models: A Survey https://arxiv.org/abs/2406.04244 大规模语言模型的基准数据污染:一项综述 文章目录 大规模语言模型的基准数据污染:一项综述摘要1 引言 摘要 大规模语言模型(LLMs),如GPT-4、Claude-3和Gemini的快

免费也能高质量!2024年免费录屏软件深度对比评测

我公司因为客户覆盖面广的原因经常会开远程会议,有时候说的内容比较广需要引用多份的数据,我记录起来有一定难度,所以一般都用录屏工具来记录会议内容。这次我们来一起探索有什么免费录屏工具可以提高我们的工作效率吧。 1.福晰录屏大师 链接直达:https://www.foxitsoftware.cn/REC/  录屏软件录屏功能就是本职,这款录屏工具在录屏模式上提供了多种选项,可以选择屏幕录制、窗口

论文翻译:ICLR-2024 PROVING TEST SET CONTAMINATION IN BLACK BOX LANGUAGE MODELS

PROVING TEST SET CONTAMINATION IN BLACK BOX LANGUAGE MODELS https://openreview.net/forum?id=KS8mIvetg2 验证测试集污染在黑盒语言模型中 文章目录 验证测试集污染在黑盒语言模型中摘要1 引言 摘要 大型语言模型是在大量互联网数据上训练的,这引发了人们的担忧和猜测,即它们可能已

轻松录制每一刻:探索2024年免费高清录屏应用

你不会还在用一些社交工具来录屏吧?现在的市面上有不少免费录屏的软件了。别看如软件是免费的,它的功能比起社交工具的录屏功能来说全面的多。这次我就分享几款我用过的录屏工具。 1.福晰录屏大师 链接直达:https://www.foxitsoftware.cn/REC/  这个软件的操作方式非常简单,打开软件之后从界面设计就能看出来这个软件操作的便捷性。界面的设计简单明了基本一打眼你就会轻松驾驭啦

梳理2024年,螺丝钉们爱用的3款剪辑软件

这年头,视频到处都是,就跟天上的星星一样数不清。不管你是公司里的新面孔,还是职场上的老狐狸,学会怎么剪视频,就好比找到了赢的秘诀。不管是给上司汇报工作,展示你的产品,还是自己搞点小视频记录生活,只要是剪辑得漂亮,肯定能一下子吸引大家的目光,让人记得你。咱们今天就来侃侃现在超火的三款视频剪辑工具,尤其是PR剪辑,你肯定听说过,这货在剪辑界可是大名鼎鼎,用它剪视频,既专业又麻利。 NO1. 福昕轻松