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 1→A→B→C→D→1,可以发现其中 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 1→A→B→C→D→1,假设枚举点 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假期计划 先思考暴力做法,题目需要找到四个不相同的景点,那我们就枚举这四个景点,判断它们之间的距离是否符合条件,条件是任意两个点之间的距离是否大于 k k k,所以我们需要求出任意两点之间的距离。常用…...
为什么要学习大模型?AI在把传统软件当早餐吃掉?
前言 上周末在推特平台上有一篇写在谷歌文档里的短文,在国外的科技/投资圈得到了非常广泛的浏览,叫做 The End of Software(软件的终结), 作者 Chris Paik 是位于纽约市的风险投资基金 Pace Capital 的创始合伙人&…...
全流程Python编程、机器学习与深度学习实践技术应用
近年来,人工智能领域的飞速发展极大地改变了各个行业的面貌。当前最新的技术动态,如大型语言模型和深度学习技术的发展,展示了深度学习和机器学习技术的强大潜力,成为推动创新和提升竞争力的关键。特别是PyTorch,凭借其…...
pWnos1.0 靶机渗透 (Perl CGI 的反弹 shell 利用)
靶机介绍 来自 vulnhub 主机发现 ┌──(kali㉿kali)-[~/testPwnos1.0] …...
jquery on() 函数绑定无效
on 前面的元素必须在页面加载的时候就存在于 dom 里面。动态的元素或者样式等,可以放在 on 的第二个参数里面。jQuery on() 方法是官方推荐的绑定事件的一个方法。使用 on() 方法可以给将来动态创建的动态元素绑定指定的事件,例如 append 等。 <div …...
数字化转型与企业创新的双向驱动
数字化转型与企业创新的双向驱动 在全球化的竞争环境中,数字化转型已成为企业保持竞争力的重要手段。未来几年,随着信息技术的进一步发展,数字化转型将不仅限于IT部门,而是深入到企业的各个业务层面,推动创新和效率的…...
[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 数据库中,表压缩是一项重要的功能,旨在优化存储空间和提高性能。Oracle 提供了多种表压缩技术,以适应不同的应用场景和需求。以下是 Oracle 数据库中表压缩的实现方式和特点: 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:颠覆性的文本生成视频技术详解
近年来,生成式AI技术的发展迅猛,尤其是在文本生成图像、文本生成视频等领域。Meta公司近期推出的MovieGen AI,以其强大的文本生成视频能力震撼了整个AI行业。本文将详细解读Meta MovieGen AI的核心技术、功能特性及其在实际应用中的潜力。 一…...
个人文章合集 - 前端相关
前端:简述表单提交前如何进行数据验证 前端:项目一个html中如何引入另一个html? 前端:一张图快速记忆CSS所有属性 前端:三个CSS预处理器(框架)-Sass、LESS 和 Stylus的比较 前端:基于Java角度理解nodejs/np…...
R语言的下载、安装及环境配置(RstudioVSCode)
0x01 R语言篇 一、软件介绍 R for Windows是一个免费的用于统计计算和统计制图的优秀工具,是R语言开发工具。它拥有数据存储和处理系统、数组运算工具(其向量、矩阵运算方面功能尤其强大)、完整连贯的统计分析工具、优秀的统计制图等功能。…...
解决使用重载后的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是链路追踪框架,用于在微服务架构下开发,各个微服务之…...
最具有世界影响力的人颜廷利:全球著名哲学家思想家起名大师
颜廷利教授,这位源自济南唐王镇的杰出人物,不仅是中国当代最杰出的国学大师之一,更是将传统文化与现代科技巧妙结合的先锋。他积极推崇以人工智能技术为辅助的国学研究方法,为这一古老领域注入了新的活力和时代表达。 除了在学术…...
Ubuntu22.04 Docker 国内安装最靠谱教程
目前docker在国内安装常存在众所周知的网络问题,如果安装过程如果从官网地址安装以及安装之后从官网要拉取镜像都存在问题。这篇文章主要针对这两个问题总结最靠谱的docker安装教程。 1. docker安装 1.1 系统环境概述 Ubuntu 22.04linux内核版本 6.8(…...
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/世界模型之间是什么关系,对自动驾驶的意义是什么?
什么是大模型 人工智能大模型(Artificial Intelligence Large Model,简称AI大模型)是指具有庞大的参数规模和复杂程度的机器学习模型。通常指的是参数量非常大、数据量非常大的深度学习模型。 大模型通常由数百万到数十亿的参数组成&#x…...
17岁孩子开发AI应用,4个月入百万,人人都是AI产品经理的时代快来了
随着AI时代的到来叠加经济下行,越来越多的独立开发者梦想着实现年入百万的壮举。 近日,这种小概率事件正在发生。 17岁高中生做了个AI APP,短短四个月销售额达100 万美元。 小伙儿Zach Yadegari(下面暂称小扎克)在X…...
Django一分钟:DRF ViewSet烹饪指南,创建好用的视图集
本文将介绍django视图集的内部实现,并带你重写部分代码自己组装强大且趁手的视图集,以满足自定义的业务需求,避免编写大量重复代码。 一、基础知识 Django Rest framework框架允许你将一组相关视图的逻辑组合到一个类中,也就是我…...
SciencePlots——绘制论文中的图片
文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了:一行…...
Admin.Net中的消息通信SignalR解释
定义集线器接口 IOnlineUserHub public interface IOnlineUserHub {/// 在线用户列表Task OnlineUserList(OnlineUserList context);/// 强制下线Task ForceOffline(object context);/// 发布站内消息Task PublicNotice(SysNotice context);/// 接收消息Task ReceiveMessage(…...
江苏艾立泰跨国资源接力:废料变黄金的绿色供应链革命
在华东塑料包装行业面临限塑令深度调整的背景下,江苏艾立泰以一场跨国资源接力的创新实践,重新定义了绿色供应链的边界。 跨国回收网络:废料变黄金的全球棋局 艾立泰在欧洲、东南亚建立再生塑料回收点,将海外废弃包装箱通过标准…...
微服务商城-商品微服务
数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...
使用 SymPy 进行向量和矩阵的高级操作
在科学计算和工程领域,向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能,能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作,并通过具体…...
视觉slam十四讲实践部分记录——ch2、ch3
ch2 一、使用g++编译.cpp为可执行文件并运行(P30) g++ helloSLAM.cpp ./a.out运行 二、使用cmake编译 mkdir build cd build cmake .. makeCMakeCache.txt 文件仍然指向旧的目录。这表明在源代码目录中可能还存在旧的 CMakeCache.txt 文件,或者在构建过程中仍然引用了旧的路…...
return this;返回的是谁
一个审批系统的示例来演示责任链模式的实现。假设公司需要处理不同金额的采购申请,不同级别的经理有不同的审批权限: // 抽象处理者:审批者 abstract class Approver {protected Approver successor; // 下一个处理者// 设置下一个处理者pub…...
Bean 作用域有哪些?如何答出技术深度?
导语: Spring 面试绕不开 Bean 的作用域问题,这是面试官考察候选人对 Spring 框架理解深度的常见方式。本文将围绕“Spring 中的 Bean 作用域”展开,结合典型面试题及实战场景,帮你厘清重点,打破模板式回答,…...
如何配置一个sql server使得其它用户可以通过excel odbc获取数据
要让其他用户通过 Excel 使用 ODBC 连接到 SQL Server 获取数据,你需要完成以下配置步骤: ✅ 一、在 SQL Server 端配置(服务器设置) 1. 启用 TCP/IP 协议 打开 “SQL Server 配置管理器”。导航到:SQL Server 网络配…...
高考志愿填报管理系统---开发介绍
高考志愿填报管理系统是一款专为教育机构、学校和教师设计的学生信息管理和志愿填报辅助平台。系统基于Django框架开发,采用现代化的Web技术,为教育工作者提供高效、安全、便捷的学生管理解决方案。 ## 📋 系统概述 ### 🎯 系统定…...
