CSP-S 2022 T1假期计划

devtools/2024/10/4 7:22:25/

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;
}

http://www.ppmy.cn/devtools/120475.html

相关文章

如何让虚拟机与本地电脑使用同一个ip

让虚拟机与本地电脑使用同一个IP地址并不是一个简单的操作&#xff0c;因为通常每个设备在网络中都有其唯一的IP地址。不过&#xff0c;有几种方法可以让虚拟机与本地电脑在某些特定情况下“共享”相同的IP地址。以下是一些常见的解决方案&#xff1a; 1. 使用桥接网络&#x…

NVIDIA Hopper 架构深入

在 2022 年 NVIDIA GTC 主题演讲中,NVIDIA 首席执行官黄仁勋介绍了基于全新 NVIDIA Hopper GPU 架构的全新 NVIDIA H100 Tensor Core GPU。 文章目录 前言一、NVIDIA H100 Tensor Core GPU 简介二、NVIDIA H100 GPU 主要功能概述1. 新的流式多处理器 (SM) 具有许多性能和效率…

【JVM】垃圾回收机制(GC)之引用计数和可达性分析

1. 引用计数 这种思想方法&#xff0c;并没有在 JVM 中使用&#xff0c;但是广泛应用于其他主流语言的垃圾回收机制中&#xff08;Python、PHP&#xff09;。 《深入理解 Java 虚拟机》中谈到了引用计数&#xff0c;就导致有些面试官还是会问 给每个对象安排一个额外的空间&am…

誉天Linux云计算课程学什么?为什么保障就业?

一个IT工程师相当于干了哪些职业? 其中置顶回答生动而形象地描绘道&#xff1a; 一个IT工程师宛如一个超级多面手&#xff0c;相当于——加班狂程序员测试工程师实施工程师网络工程师电工装卸工搬运工超人。 此中酸甜苦辣咸&#xff0c;相信很多小伙伴们都深有体会。除了典…

Unity3D播放GIF图片使用Animation来制作动画

系列文章目录 unity工具 文章目录 系列文章目录👉前言👉一、下载GIF动图,用PS制作导出帧动画图片👉二、使用Animation制作动画👉三、脚本控制动画播放👉壁纸分享👉总结👉前言 unity播放gif图片,本身是不支持的,但是可以使用其他方法来实现, 1.有一种使用System…

IP与网关的关系

在计算机网络中&#xff0c;IP地址和网关是两个重要的概念&#xff0c;它们在网络通信中起着关键作用。理解这两者之间的关系&#xff0c;有助于更好地管理和配置网络。 什么是IP地址&#xff1f; IP地址&#xff08;Internet Protocol Address&#xff09;是分配给网络中每个…

城市空间设计对居民生活质量的影响:构建宜居城市的蓝图

在快节奏的现代生活中&#xff0c;城市不仅是经济活动的中心&#xff0c;更是人们生活、工作、休闲的综合载体。本文旨在深入探讨城市空间设计如何通过科学规划、人性化考量以及生态融合&#xff0c;为居民打造更加宜居、和谐的生活环境。 1. 促进社区互动与归属感 城市空间设…

RabbitMQ的高级特性-TTL

TTL(Time to Live, 过期时间), 即过期时间. RabbitMQ可以对消息和队列设置TTL.当消息到达存活时间之后, 还没有被消费, 就会被⾃动清除 设置消息的TTL&#xff1a; ①设置队列的TTL&#xff0c;队列中所有的消息都有相同的过期时间 …