当前位置: 首页 > news >正文

CSP-S 2022 T1假期计划

CSP-S 2022 T1假期计划

先思考暴力做法,题目需要找到四个不相同的景点,那我们就枚举这四个景点,判断它们之间的距离是否符合条件,条件是任意两个点之间的距离是否大于 k k k,所以我们需要求出任意两点之间的距离。常用的 D i j k s t r a Dijkstra Dijkstra S P F A SPFA SPFA都是单源最短路,也就是只能求一个点到其它点的距离,而 F l o y e d Floyed Floyed可以求任意两个点之间的最短路,虽然其时间复杂度是 O ( n 3 ) O(n^3) O(n3),但对于这个做法的数据范围是可以接受的。这个做法的时间复杂度为 O ( n 4 ) O(n^4) O(n4)(枚举四个景点),在 k k k较小的情况下可以通过(因为 k k k会影响到循环退出),可以拿到 55 55 55分。

#include <bits/stdc++.h>
#define A 2510using namespace std;
typedef long long ll;
int n, m, kk, x, y, dis[A][A];
ll a[A], ans;int main(int argc, char const *argv[]) {scanf("%d%d%d", &n, &m, &kk); kk++;for (int i = 2; i <= n; i++) scanf("%lld", &a[i]);memset(dis, 0x3f, sizeof dis);for (int i = 1; i <= n; i++) dis[i][i] = 0;for (int i = 1; i <= m; i++) {scanf("%d%d", &x, &y);dis[x][y] = 1; dis[y][x] = 1;}for (int k = 1; k <= n; k++)for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);for (int i = 2; i <= n; i++) {if (dis[1][i] > kk) continue;for (int j = 2; j <= n; j++) {if (i == j) continue;if (dis[i][j] > kk) continue;for (int k = 2; k <= n; k++) {if (i == k or j == k) continue;if (dis[j][k] > kk) continue;for (int l = 2; l <= n; l++) {if (i == l or j == l or k == l) continue;if (dis[k][l] > kk or dis[l][1] > kk) continue;ans = max(ans, a[i] + a[j] + a[k] + a[l]);}}}}printf("%lld\n", ans);
}

比较特殊的数据点是当 k = 0 k=0 k=0时,也就是挑选的 4 4 4个景点必须都相邻,直接通过 d f s dfs dfs搜索所有的情况,如果遍历到了家( 1 1 1号点)并且已经路过了 4 4 4个不同的节点,这就是一条可行的路径,可以更新答案。 k = 0 k=0 k=0共有 9 9 9个测试点,共 45 45 45分。

#include <bits/stdc++.h>
#define A 2510using namespace std;
int n, m, k, a[A], ans;
bool vis[A], mp[A][A];
void dfs(int now, int sum, int left) {if (now == 1 and left == 0) {ans = max(ans, sum);return;}else if (left == 0) return;for (int i = 1; i <= n; i++) {if (!mp[now][i] or vis[i]) continue;vis[i] = 1;dfs(i, sum + a[i], left - 1);vis[i] = 0;}
}int main() {cin >> n >> m >> k;for (int i = 2; i <= n; i++) cin >> a[i];while (m--) {int x, y;cin >> x >> y;mp[x][y] = 1; mp[y][x] = 1;}dfs(1, 0, 5);cout << ans << endl;
}

这个写法可以通过 k = 0 k=0 k=0的所有特殊情况,和第一个暴力结合一下,可以拿到 70 70 70分。

#include <bits/stdc++.h>
#define A 2510using namespace std;
typedef long long ll;
int n, m, kk, x, y, dis[A][A];
ll a[A], ans;
bool vis[A], mp[A][A];
void dfs(int now, ll sum, int left) {if (now == 1 and left == 0) {ans = max(ans, sum);return;}else if (left == 0) return;for (int i = 1; i <= n; i++) {if (!mp[now][i] or vis[i]) continue;vis[i] = 1;dfs(i, sum + a[i], left - 1);vis[i] = 0;}
}int main(int argc, char const *argv[]) {scanf("%d%d%d", &n, &m, &kk);if (kk == 0) {for (int i = 2; i <= n; i++) scanf("%lld", &a[i]);while (m--) {scanf("%d%d", &x, &y);mp[x][y] = 1; mp[y][x] = 1;}dfs(1, 0, 5);printf("%lld\n", ans);return 0;}kk++;for (int i = 2; i <= n; i++) scanf("%lld", &a[i]);memset(dis, 0x3f, sizeof dis);for (int i = 1; i <= n; i++) dis[i][i] = 0;for (int i = 1; i <= m; i++) {scanf("%d%d", &x, &y);dis[x][y] = 1; dis[y][x] = 1;}for (int k = 1; k <= n; k++)for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);for (int i = 2; i <= n; i++) {if (dis[1][i] > kk) continue;for (int j = 2; j <= n; j++) {if (i == j) continue;if (dis[i][j] > kk) continue;for (int k = 2; k <= n; k++) {if (i == k or j == k) continue;if (dis[j][k] > kk) continue;for (int l = 2; l <= n; l++) {if (i == l or j == l or k == l) continue;if (dis[k][l] > kk or dis[l][1] > kk) continue;ans = max(ans, a[i] + a[j] + a[k] + a[l]);}}}}printf("%lld\n", ans);
}

我们要找的一个路径是 1 → A → B → C → D → 1 1\to A\to B\to C\to D\to 1 1ABCD1,可以发现其中 A A A D D D B B B C C C有一些共同之处: A A A D D D的两端一定是起点 1 1 1和一个其它的点,由于道路是双向的,所以可以说 A A A D D D这两个点是等价的; B B B D D D的两端一定是非起点,可以说 B B B C C C这两个点是等价的。这样一来中间不同的四个点被压缩成了两个点。
用一个双重循环枚举 A A A B B B A A A B B B点的特征是 d i s [ 1 ] [ A ] < k dis[1][A]<k dis[1][A]<k d i s [ A ] [ B ] < k dis[A][B]<k dis[A][B]<k,同时满足条件的点 A A A也对应着点 D D D,点 B B B对应着点 C C C。对于所有的点 B B B,找到所有符合条件的点 A A A,符合条件的点 A A A可能有很多,我们只需要存值最大的三个就可以。

为什么是存三个点?
对于路径 1 → A → B → C → D → 1 1\to A\to B\to C\to D\to 1 1ABCD1,假设枚举点 B B B时找到了点 j j j作为 A A A点,枚举点 C C C时找到了点 k k k作为 D D D点,那么 k = j k=j k=j k = B k=B k=B都是有可能发生的,所以要存三个点以防重复。

#include <bits/stdc++.h>using namespace std;
typedef long long ll;
#define A 2510
vector<int> e[A];
ll dis[A][A], ans, a[A];
bool vis[A];
int n, m, k;
void bfs(int start) {memset(vis, 0, sizeof vis); vis[start] = 1;queue<int> q; q.push(start);while (!q.empty()) {int fr = q.front(); q.pop();for (int i = 0; i < (int)e[fr].size(); i++) {int ca = e[fr][i];if (vis[ca]) continue;vis[ca] = 1;if (dis[start][ca] > dis[start][fr] + 1) {dis[start][ca] = dis[start][fr] + 1;q.push(ca);}}}
}
set<pair<ll, int> > s[A];int main(int argc, char const *argv[]) {scanf("%d%d%d", &n, &m, &k); k++;for (int i = 2; i <= n; i++) scanf("%lld", &a[i]);while (m--) {int x, y; scanf("%d%d", &x, &y);e[x].push_back(y); e[y].push_back(x);}for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++) {dis[i][j] = INT_MAX;if (i == j) dis[i][j] = 0;}for (int i = 1; i <= n; i++) bfs(i);for (int i = 2; i <= n; i++) {for (int j = 2; j <= n; j++)if (i != j and dis[j][i] <= k and dis[1][j] <= k) {s[i].insert(make_pair(a[j], j));if (s[i].size() > 3) s[i].erase(s[i].begin());}}for (int i = 2; i <= n; i++)for (int j = 2; j <= n; j++) {if (dis[i][j] > k or i == j) continue;for (auto k : s[i]) {if (k.second == i or k.second == j) continue;for (auto l : s[j]) {if (l.second == i or l.second == j or l.second == k.second) continue;ans = max(ans, a[i] + a[j] + a[l.second] + a[k.second]);}}}cout << ans << endl;
}

相关文章:

CSP-S 2022 T1假期计划

CSP-S 2022 T1假期计划 先思考暴力做法&#xff0c;题目需要找到四个不相同的景点&#xff0c;那我们就枚举这四个景点&#xff0c;判断它们之间的距离是否符合条件&#xff0c;条件是任意两个点之间的距离是否大于 k k k&#xff0c;所以我们需要求出任意两点之间的距离。常用…...

为什么要学习大模型?AI在把传统软件当早餐吃掉?

前言 上周末在推特平台上有一篇写在谷歌文档里的短文&#xff0c;在国外的科技/投资圈得到了非常广泛的浏览&#xff0c;叫做 The End of Software&#xff08;软件的终结&#xff09;&#xff0c; 作者 Chris Paik 是位于纽约市的风险投资基金 Pace Capital 的创始合伙人&…...

全流程Python编程、机器学习与深度学习实践技术应用

近年来&#xff0c;人工智能领域的飞速发展极大地改变了各个行业的面貌。当前最新的技术动态&#xff0c;如大型语言模型和深度学习技术的发展&#xff0c;展示了深度学习和机器学习技术的强大潜力&#xff0c;成为推动创新和提升竞争力的关键。特别是PyTorch&#xff0c;凭借其…...

pWnos1.0 靶机渗透 (Perl CGI 的反弹 shell 利用)

靶机介绍 来自 vulnhub 主机发现 ┌──(kali㉿kali)-[~/testPwnos1.0] …...

jquery on() 函数绑定无效

on 前面的元素必须在页面加载的时候就存在于 dom 里面。动态的元素或者样式等&#xff0c;可以放在 on 的第二个参数里面。jQuery on() 方法是官方推荐的绑定事件的一个方法。使用 on() 方法可以给将来动态创建的动态元素绑定指定的事件&#xff0c;例如 append 等。 <div …...

数字化转型与企业创新的双向驱动

数字化转型与企业创新的双向驱动 在全球化的竞争环境中&#xff0c;数字化转型已成为企业保持竞争力的重要手段。未来几年&#xff0c;随着信息技术的进一步发展&#xff0c;数字化转型将不仅限于IT部门&#xff0c;而是深入到企业的各个业务层面&#xff0c;推动创新和效率的…...

[uni-app]小兔鲜-07订单+支付

订单模块 基本信息渲染 import type { OrderState } from /services/constants import type { AddressItem } from ./address import type { PageParams } from /types/global/** 获取预付订单 返回信息 */ export type OrderPreResult {/** 商品集合 [ 商品信息 ] */goods: …...

Oracle数据库中表压缩的实现方式和特点

Oracle数据库中表压缩的实现方式和特点 在 Oracle 数据库中&#xff0c;表压缩是一项重要的功能&#xff0c;旨在优化存储空间和提高性能。Oracle 提供了多种表压缩技术&#xff0c;以适应不同的应用场景和需求。以下是 Oracle 数据库中表压缩的实现方式和特点&#xff1a; 1…...

【C语言】基础篇

简单输出“helloword” #include<stdio.h> int main(){printf("hello world!");return 0; } 和与商 #include<stdio.h> int main(){int a,b,sum,quotient;printf("Enter two numbers:");scanf("%d %d",&a,&b);sum a b…...

Meta MovieGen AI:颠覆性的文本生成视频技术详解

近年来&#xff0c;生成式AI技术的发展迅猛&#xff0c;尤其是在文本生成图像、文本生成视频等领域。Meta公司近期推出的MovieGen AI&#xff0c;以其强大的文本生成视频能力震撼了整个AI行业。本文将详细解读Meta MovieGen AI的核心技术、功能特性及其在实际应用中的潜力。 一…...

个人文章合集 - 前端相关

前端&#xff1a;简述表单提交前如何进行数据验证 前端&#xff1a;项目一个html中如何引入另一个html&#xff1f; 前端&#xff1a;一张图快速记忆CSS所有属性 前端&#xff1a;三个CSS预处理器(框架)-Sass、LESS 和 Stylus的比较 前端&#xff1a;基于Java角度理解nodejs/np…...

R语言的下载、安装及环境配置(RstudioVSCode)

0x01 R语言篇 一、软件介绍 R for Windows是一个免费的用于统计计算和统计制图的优秀工具&#xff0c;是R语言开发工具。它拥有数据存储和处理系统、数组运算工具&#xff08;其向量、矩阵运算方面功能尤其强大&#xff09;、完整连贯的统计分析工具、优秀的统计制图等功能。…...

解决使用重载后的CustomWidget无法正常显示但原生的QWidget却能正常显示的问题

这种情况大部分都是因为没有重写paintEvent: ​#include <QPainter> #include <QStyleOption>void CustomWidget::paintEvent(QPaintEvent *) { QStyleOption opt; opt.initFrom(this); QPainter p(this); style()->drawPrimitive(QStyle::PE_Widget, &opt,…...

微服务Sleuth解析部署使用全流程

目录 1、Sleuth链路追踪 1、添加依赖 2、修改日志配置文件 3、测试 2、zipkin可视化界面 1、docker安装 2、添加依赖 3、修改配置文件 4、查看页面 5、ribbon配置 1、Sleuth链路追踪 sleuth是链路追踪框架&#xff0c;用于在微服务架构下开发&#xff0c;各个微服务之…...

最具有世界影响力的人颜廷利:全球著名哲学家思想家起名大师

颜廷利教授&#xff0c;这位源自济南唐王镇的杰出人物&#xff0c;不仅是中国当代最杰出的国学大师之一&#xff0c;更是将传统文化与现代科技巧妙结合的先锋。他积极推崇以人工智能技术为辅助的国学研究方法&#xff0c;为这一古老领域注入了新的活力和时代表达。 除了在学术…...

Ubuntu22.04 Docker 国内安装最靠谱教程

目前docker在国内安装常存在众所周知的网络问题&#xff0c;如果安装过程如果从官网地址安装以及安装之后从官网要拉取镜像都存在问题。这篇文章主要针对这两个问题总结最靠谱的docker安装教程。 1. docker安装 1.1 系统环境概述 Ubuntu 22.04linux内核版本 6.8&#xff08;…...

ceph pg rebalance

背景 1 个 osd full 超过 85% 使用率最近有大量的数据写入及数据删除操作 $ ceph osd df tree | grep osd.158 ID CLASS WEIGHT REWEIGHT SIZE RAW USE DATA OMAP META AVAIL %USE VAR PGS STATUS TYPE NAME …...

大模型/Sora/世界模型之间是什么关系,对自动驾驶的意义是什么?

什么是大模型 人工智能大模型&#xff08;Artificial Intelligence Large Model&#xff0c;简称AI大模型&#xff09;是指具有庞大的参数规模和复杂程度的机器学习模型。通常指的是参数量非常大、数据量非常大的深度学习模型。 大模型通常由数百万到数十亿的参数组成&#x…...

17岁孩子开发AI应用,4个月入百万,人人都是AI产品经理的时代快来了

随着AI时代的到来叠加经济下行&#xff0c;越来越多的独立开发者梦想着实现年入百万的壮举。 近日&#xff0c;这种小概率事件正在发生。 17岁高中生做了个AI APP&#xff0c;短短四个月销售额达100 万美元。 小伙儿Zach Yadegari&#xff08;下面暂称小扎克&#xff09;在X…...

Django一分钟:DRF ViewSet烹饪指南,创建好用的视图集

本文将介绍django视图集的内部实现&#xff0c;并带你重写部分代码自己组装强大且趁手的视图集&#xff0c;以满足自定义的业务需求&#xff0c;避免编写大量重复代码。 一、基础知识 Django Rest framework框架允许你将一组相关视图的逻辑组合到一个类中&#xff0c;也就是我…...

装饰模式(Decorator Pattern)重构java邮件发奖系统实战

前言 现在我们有个如下的需求&#xff0c;设计一个邮件发奖的小系统&#xff0c; 需求 1.数据验证 → 2. 敏感信息加密 → 3. 日志记录 → 4. 实际发送邮件 装饰器模式&#xff08;Decorator Pattern&#xff09;允许向一个现有的对象添加新的功能&#xff0c;同时又不改变其…...

Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)

文章目录 1.什么是Redis&#xff1f;2.为什么要使用redis作为mysql的缓存&#xff1f;3.什么是缓存雪崩、缓存穿透、缓存击穿&#xff1f;3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...

QMC5883L的驱动

简介 本篇文章的代码已经上传到了github上面&#xff0c;开源代码 作为一个电子罗盘模块&#xff0c;我们可以通过I2C从中获取偏航角yaw&#xff0c;相对于六轴陀螺仪的yaw&#xff0c;qmc5883l几乎不会零飘并且成本较低。 参考资料 QMC5883L磁场传感器驱动 QMC5883L磁力计…...

SCAU期末笔记 - 数据分析与数据挖掘题库解析

这门怎么题库答案不全啊日 来简单学一下子来 一、选择题&#xff08;可多选&#xff09; 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘&#xff1a;专注于发现数据中…...

Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具

文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...

基础测试工具使用经验

背景 vtune&#xff0c;perf, nsight system等基础测试工具&#xff0c;都是用过的&#xff0c;但是没有记录&#xff0c;都逐渐忘了。所以写这篇博客总结记录一下&#xff0c;只要以后发现新的用法&#xff0c;就记得来编辑补充一下 perf 比较基础的用法&#xff1a; 先改这…...

Nuxt.js 中的路由配置详解

Nuxt.js 通过其内置的路由系统简化了应用的路由配置&#xff0c;使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...

uniapp微信小程序视频实时流+pc端预览方案

方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度​WebSocket图片帧​定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐​RTMP推流​TRTC/即构SDK推流❌ 付费方案 &#xff08;部分有免费额度&#x…...

如何理解 IP 数据报中的 TTL?

目录 前言理解 前言 面试灵魂一问&#xff1a;说说对 IP 数据报中 TTL 的理解&#xff1f;我们都知道&#xff0c;IP 数据报由首部和数据两部分组成&#xff0c;首部又分为两部分&#xff1a;固定部分和可变部分&#xff0c;共占 20 字节&#xff0c;而即将讨论的 TTL 就位于首…...

【Java学习笔记】BigInteger 和 BigDecimal 类

BigInteger 和 BigDecimal 类 二者共有的常见方法 方法功能add加subtract减multiply乘divide除 注意点&#xff1a;传参类型必须是类对象 一、BigInteger 1. 作用&#xff1a;适合保存比较大的整型数 2. 使用说明 创建BigInteger对象 传入字符串 3. 代码示例 import j…...