“卓见杯”郑州轻工业大学第十五届程序设计大赛暨河南省高校邀请赛题解

🕗 发布于 2024-04-14 09:09 算法 c++ 图论

题目链接

3-11题的题解均已写完

C 最大的数 — 贪心

首先n个点有n条边必然有环，因此可以无限制的加数，又因为题目要求最大不超过1e9，所以答案一定是9位数
如果把形成的环缩点的话就会变成拓扑序列，首先要找到数字最大的那几个点，把他们入队，然后遍历他们的下一个点，找到下一个点里的最大值，再把等于最大值的下一个点入队，这样贪心一定能得到最优解，循环9次，即可找到最大的那个9位数

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

signed main()
{
int n; cin >> n;
vector<int> e(n + 1), val(n + 1);
vector<vector<int>> pos(10);
// 由题意可知每个点只有一条出边 
 for(int i = 1, x; i <= n; i ++) cin >> e[i];
// pos记录值为 i 的 点有哪些 
for(int i = 1; i <= n; i ++){
cin >> val[i];
pos[val[i]].push_back(i);
}

vector<int> res, can[10];
// 找出最大的所有点作为出发点 
int maxv = 0;
for(int i = 9; i >= 0; i --) 
if(pos[i].size()) {
maxv = i;
can[1] = pos[i];
break;
}
res.push_back(maxv);
for(int i = 1; i <= 8; i ++){
maxv = 0;
// 找出目前所到的点的下一个的最大值 
for(auto x : can[i]) maxv = max(maxv, val[e[x]]);
for(auto x : can[i]){
// 找出等于这个最大值的下一个点，作为下一次遍历的开始 
if(val[e[x]] == maxv)
can[i + 1].push_back(e[x]);
}
res.push_back(maxv);
}
for(auto x : res) cout << x;
}

D 兔子爱吃胡萝卜—01背包

题意可转化为给一个长度为m的数组，求取出数组中的若干个数，使其和为n的倍数
如果只是凑出n的话就是最经典的01背包，变为n的倍数就要多加一个取模

f[i][j]状态表示为：前i个数，可以凑出模n后的数j
状态计算：分为当前第i个数取还是不取
取： f[i][(j + a[i]) % n] |= f[i - 1][j]
不取：f[i][j] |= f[i - 1][j]

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

int f[1010][1010] = {0};
int a[1010] = {0};
int n, m;
signed main()
{
cin >> n >> m;
for(int i = 1; i <= m; i ++) cin >> a[i], a[i] %= n;
for(int i = 1; i <= m; i ++)
{
f[i][a[i]] = 1;
for(int j = 0; j < n; j ++)
{
f[i][(j + a[i]) % n] |= f[i - 1][j];
f[i][j] |= f[i - 1][j];
}
}
if(f[m][0]) cout << "YES" << '\n';
else cout << "NO" << '\n';
}

E 小Z的难题—小模拟签到

从后往前遍历，把最后连续的z全变成a
找到第一个不是z的加1

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
signed main()
{
int n; cin >> n;
string s; cin >> s;
bool f = true;
for(int i = n - 1; i >= 0; i --)
if(s[i] == 'z') s[i] = 'a';
else{
s[i] ++;
f = false;
break;
}
if(f) cout << "No solution";
else cout << s;
}

F 莫比乌斯最大值isUsefulAlgorithm—枚举+思维

注：这里gcd指最大公约数
需要注意a，b数组每个值小于1e5，直接枚举gcd，然后枚举gcd的倍数即可
枚举gcd时如果a，b数组还有公约数，根据贪心，一定会枚举到更大的公约数，把答案更新
调和级数，复杂度是Onlogn

#include <iostream>
#include <vector>
using namespace std;
#define int long long
int a[100010], b[100010];
signed main()
{
int n, x; cin >> n;
for(int i = 1; i <= n; i ++) cin >> x, a[x] = 1;
for(int i = 1; i <= n; i ++) cin >> x, b[x] = 1;
int res = 0;
for(int i = 1; i <= 100000; i ++)
{
int maxa = 0, maxb = 0;
for(int j = i; j <= 100000; j += i)
{
if(a[j]) maxa = j;
if(b[j]) maxb = j; 
}
res = max(res, maxa * maxb * i);
}
cout << res;
}

G 爆米花 — 简单数学签到

总爆米花数为(1+n)*n/2，合并次数为n-1，所以减去n-1即可

#include <iostream>
using namespace std;
signed main()
{
int n; cin >> n;
cout << (long long)(n + 1) * n / 2 - (n - 1);
}

H what’s 莫比乌斯最大值—模拟+贪心

每次把问的问题放在哈希表里，问的问题字符串可能是另一个问题的前缀串
因此在处理回答字符串的时候，直接枚举，贪心找出最长的问题，放到回答问题的哈希表中
然后不断更新

#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;

signed main()
{
int n; cin >> n;
unordered_set<string> ques, ans;
for(int i = 1; i <= n; i ++)
{
string s; cin >> s;
if(s == "what's") cin >> s, ques.insert(s);
else
{
string tmp = "", maxl = ""; 
for(int i = 0; i < s.size(); i ++)
{
tmp += s[i];
if(ques.count(tmp) && !ans.count(tmp)) maxl = tmp;
}
if(maxl.size()) ans.insert(maxl);
}
}
cout << ans.size();
}

I 神奇的花—大模拟

详细请看代码注释

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
#define int long long
int st, ed;
int mon[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
vector<int> runy; // 预处理存的闰年
vector<int> set0;// 每次连续两天闭合置零的位置
vector<int> vec;// 下雨天数对应的数字
// 判断是否是闰年
bool is_run(int x) {
if(x % 400 == 0) return true;
if((x % 4 == 0) && (x % 100)) return true;
return false;
}
// 将年月日转换为数字
int cal(int y, int m, int d) {
auto x = upper_bound(runy.begin(), runy.end(), y - 1);
// 闰年的天数 
int runcnt = x - runy.begin();
int sum = runcnt + (y - 1) * 365;

if(is_run(y)) mon[2] = 29;
else mon[2] = 28;
for(int i = 1; i < m; i ++) sum += mon[i];
sum += d;
return sum;
}
//计算出【l, r】这个区间中开放的时间
int cal_day(int l, int r) {
int ll = l, rr = r;
int sum = 0;
// 将左区间不完整7天的地方 更新到完整7天的位置
while((l % 7) && (l <= r)) {
sum ++;
l ++;
}
//完整7天，除以7，然后乘6
int t = (r - l) / 7;
sum += t * 6;
//更新到最后一段不完整区间位置
l += t * 7 + 1;
// 枚举右区间不完整7天的位置
for(int i = l; i <= r; i ++)
if(i % 7) sum ++;
// 减去 这段时间中包含下雨天数
for(auto x : vec) if(x >= ll && x <= rr) sum --;
return sum;
}

signed main() {

for(int i = 1; i <= 2000000; i ++) if(is_run(i))runy.push_back(i);
int y, m, d;
scanf("%lld-%lld-%lld", &y, &m, &d);
st = cal(y, m, d);
scanf("%lld-%lld-%lld", &y, &m, &d);
ed = cal(y, m, d) - st + 1;
int k;
cin >> k;
for(int i = 0; i < k; i ++) {
scanf("%lld-%lld-%lld", &y, &m, &d);
vec.push_back(cal(y, m, d) - st + 1);
}
st = 1;
sort(vec.begin(), vec.end());
// 去除下雨天超过 结束时间的数
while(vec.back() > ed) vec.pop_back();
//处理出连续2天需要置零的位置，set0存的是连续天数的第二天
for(int i = 0; i < vec.size(); i ++) {
if(i + 1 < vec.size() && vec[i] + 1 == vec[i + 1]) set0.push_back(vec[i + 1]);
if(vec[i] % 7 == 1) set0.push_back(vec[i]);
if(vec[i] % 7 == 6) set0.push_back(vec[i] + 1);
}
vec.erase(unique(vec.begin(),vec.end()), vec.end());
sort(set0.begin(), set0.end());
set0.erase(unique(set0.begin(),set0.end()), set0.end());

int pre = 1;
int res = 0;
for(int i = 0; i < set0.size(); i ++) {
res = max(res, cal_day(pre, set0[i] - 2));
pre = set0[i] + 1;
}
res = max(res, cal_day(pre, ed));
cout << res;
}

J 售卖车票—贪心+维护区间

贪心：枚举左端点，对于左端点相同的区间，优先选择右端点比较小的
枚举左端点时维护一个该点被sum个区间占用了，如果sum>k，则从堆里找出右端点最大的去除，直到sum<=k
枚举过l这个左端点后，就可以把以l为右端点区间数的从sum删除掉了，这些区间一定没问题了，加到答案res中
具体看代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
#define int long long
vector<int> g[200010];
int cnt[200010];
priority_queue<int> q;
signed main() 
{
int n, m, k; cin >> n >> m >> k;
for(int i = 1; i <= m; i ++)
{
int l, r; cin >> l >> r;
g[l].push_back(r);
} 
int res = 0, sum = 0;
for(int l = 1; l <= n; l ++)
{
for(auto r : g[l])
{
sum ++;
cnt[r] ++;
q.push(r);
}
while(sum > k)
{
cnt[q.top()] --;
q.pop();
sum --;
}
sum -= cnt[l];
res += cnt[l];
}
cout << res;
}

K Alice and Bob—模拟

有效的距离只有1000，所以先用字符串读入落点，用函数判断是否出靶，如果没出靶就算一下xx+yy
如果都没出靶就比一下xx+yy谁小即可

#include <iostream>
#include <cstring>
using namespace std;
#define int long long

bool check(string sx, string sy, int &dis)
{
if(sx.size() > 6 || sy.size() > 6) return true;
if(sx[0] == '-') sx = sx.substr(1);
if(sy[0] == '-') sy = sy.substr(1);

int x = stoi(sx), y = stoi(sy);
dis = x * x + y * y;
return dis > 1000000;
}

signed main() 
{
string x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
int dis1 = 0, dis2 = 0;
bool c1 = check(x1, y1, dis1);
bool c2 = check(x2, y2, dis2);
if(c1 && c2) cout << "Draw";
else if(c1) cout << "Bob";
else if(c2) cout << "Alice";
else
{
if(dis1 == dis2) cout << "Draw";
else if(dis1 < dis2) cout << "Alice";
else cout << "Bob";
}
}

原文地址：https://blog.csdn.net/qq_51282224/article/details/129963558

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：数学建模 | 灰色预测原理及python实现
下一篇：科研学习|论文解读——基于旅游知识图谱的游客偏好挖掘和决策支持（IPM，2023）

MoneyPrinterTurbo - AI自动生成高清短视频
MoneyPrinterTurbo是一款基于AI大模型的开源软件，旨在通过一键操作帮助用户自动生成高清短视频。只需提供一个视频主题或 **关键词** ，就可以全自动生成视频文案、视频素材、视频字幕、
阅读更多2024-11-18
跨平台WPF框架Avalonia教程五
在 Avalonia 11 之前，控件主题是使用标准样式创建的。然而，这种方法存在一个根本性的问题：一旦样式被应用到控件上，就没有办法移除它。因此，如果你想为特定的控件实例或用户界面（UI）部分更改
阅读更多2024-11-18
Linux 下网络套接字(Socket) 与udp和tcp 相关接口
Linux下套接字的介绍与使用
阅读更多2024-11-18
react 中 useReducer Hook 作用
useState`是最基本的状态管理钩子。`useReducer`提供了一种更可预测的状态管理方式。
阅读更多2024-11-18
【自学笔记】推荐系统
（Retrieval）步骤的目的是从庞大的候选集合中快速筛选出一小部分最有可能满足用户需求的项目。这样做可以简化梯度计算，更显著的变化是，如果人没有为任何样本打分，那代入TA的初始参数。我们需要做的是
阅读更多2024-11-18
【jvm】方法区是否存在GC
6.在Hotspot虚拟机中，方法区对应的是持久代（PermGen space，在JDK 8及之后被元空间Metaspace取代），尽管持久代上的GC较少，但并不代表完全没有。2.在JVM（Java虚
阅读更多2024-11-18
2411rust,异步函数
2411rust,异步函数
阅读更多2024-11-18
用 Python 从零开始创建神经网络（八）：梯度、偏导数和链式法则
在我们继续编写我们的神经网络代码之前，最后两个需要解决的难题是梯度和偏导数的相关概念。我们到目前为止解决的导数案例都是函数中只有一个独立变量的情况——也就是说，结果完全依赖于xx（在我们的案例中）。然
阅读更多2024-11-18
深度学习之One Stage目标检测算法2
YOLO（You Only Look Once: Unified, Real-Time Object Detection）是one-stage detection的开山之作。之前的物体检测方法首先需要
阅读更多2024-11-18
TCP协议的代理IP是什么？
对于需要大量数据传输和高效通信的场景，代理IP技术提供了至关重要的支持。TCP协议作为互联网通信中最基础和最常用的协议之一，与代理IP技术的结合成为了许多企业和开发者进行网络操作时不可或缺的一部分。那
阅读更多2024-11-18