「考试报告」2023.5.21 模拟赛

#「考试报告」2023.5.21 模拟赛| 来源: 网络整理| 查看: 265

earth 【题目描述】

“啊，地球，我的流浪地球……” ——《流浪地球》在一条直线上，从左到右排列着 \(n\) 台地球发动机，每台发动机有着固定的位置坐标 \(A_i\) 和功率 \(P_i\)，保证 \(A_i A_i + x_i\) 的最小位置，可以二分找到。

#include using namespace std; typedef long long ll; const int N = 1e5 + 5; int n; ll A[N], p[N], x[N], dp[N]; int main() { scanf("%d", &n); for (int i = 1; i = 1; -- i) { int pos = A[i] + x[i]; if (A[i + 1] > pos) { dp[i] = dp[i + 1] + p[i]; } else { if (A[n] < pos) { dp[i] = max(dp[i + 1], p[i]); } else { int x = upper_bound(A + i, A + n + 1, pos) - A; dp[i] = max(dp[i + 1], dp[x] + p[i]); } } } printf("%lld\n", dp[1]); return 0; } graph 【题目描述】

小 \(H\) 有一张 \(n\) 个点，\(m\) 条边的无向连通图，他想从图中选出一些边，保证通过这些边 \(a\) 和 \(b\) 连通,\(c\) 和 \(d\) 连通，同时选出的边数尽量少。

【输入数据】

第一行两个整数 \(n,m\)，表示图中的边数和点数。第二行四个整数 \(a,b,c,d\)，意义如题面所述。接下来 \(m\) 行，每行两个整数 \(a,b\),表示点 \(a\) 和点 \(b\) 间有一条边。

【输出数据】

一行一个整数，表示最少需要选出的边数。

【样例输入】 5 8 3 4 1 3 2 1 3 2 4 3 5 3 4 2 1 4 5 4 2 1 【样例输出】 2 【数据范围】

对于所有数据，保证 \(1 \le a,b,c,d \le n\)；对于 \(10\%\) 的数据，\(0 < n,m \le 20\); 对于 \(30\%\) 的数据，\(0 < n,m \le 300\); 对于 \(60\%\) 的数据，\(0 < n \le 300\); 对于 \(100\%\) 的数据，\(0 < n,m \le 3000\)。

如果路径不相交，则答案为 \(a \Rightarrow b\)、\(c \Rightarrow d\) 的最短路，如果有相交的部分， \(n^2\) 枚举相交部分的起始点和终点，判断这一段是否相交，求最大值。点与点之间的最小距离，由于没有边权，可以直接设为 \(1\)，然后用 bfs 来做，\(O_{n^2}\)。堆优化的 dijkstra 也跑不过，别问我是怎么知道的。

#include using namespace std; typedef long long ll; typedef pair pli; const int N = 3010; int n, m, a, b, c, d; ll dis[N][N]; bool vis[N], e[N][N]; vector son[N]; void bfs(int s) { for (int i = 1; i

【本文地址】

公司简介

联系我们