3 月 15 日测试题解()-其他
3 月 15 日测试题解()
3 月 15 日测试题解
这学校的评测机我是真的吐了，\(\text{380pts} \rightarrow \text{300pts}\)，电脑速度跟 BZOJ 有的一拼。
一句话总结：简单，过于简单，但是在练习读题能力上十分有用。
T1 挂分的原因是 在读入 \(3 \times 5 \times 10^5\) 的数据情况下超时了，而 T2 纯纯自己傻逼，T3 跟 T4 又是因为这台奇快无比的评测机 T 了 \(\text{60pts}\)。
std::cin我还能做出什么评价呢？等我退役之后一定要给学校搭一台好一点的服务器之类的当评测机。
T1
题意
一个长度为 \(s\) 的区间与 \(n\) 个操作，初始区间内每个值都赋为 \(1\)，每次操作给出三个整数 \(l\)，\(r\) 与 \(t\)，表示将 \([l, r]\) 内的数修改为 \(t\)，求最后得到的区间和。
\(s \le 2 \times 10^9\)，\(n \le 5 \times 10^5\)。保证给出的区间没有重叠。
思路
\(\text{100pts}\)
因为保证了给出的区间没有重叠，简单模拟即可，没有什么思维难度。初始化 \(ans = s\)，然后每次修改让 \(ans\) 加上 \((r – l + 1) \times (t – 1)\) 就做完了。
但是这道题的数据离谱到了在明确强调没有区间重叠的情况后，第 2 ~ 3 个测试点仍然出现了重叠情况，虽然我没有因此挂分，但是我还是很想问问验题人：你自认为你是一个合格的验题人吗？这种如此简单的数据都不愿意写程序检验一下，我真的不知道要这种验题人有什么用。
为什么我知道这道题数据有问题呢？因为我旁边的老哥写的是 ODT。
代码
\(\text{100pts}\)
#include <bits/stdc++.h>
#include <iostream>
using i64 = long long;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
int s, n;
std::cin >> s >> n;
i64 ans = s;
for (int i = 1; i <= n; i++) {
i64 l, r, t;
std::cin >> l >> r >> t;
ans += (r - l + 1) * (t - 1);
}
std::cout << ans << "\n";
return 0;
}
T2
题意
经典求最大矩形面积题。
\(n \le 10^5\)，\(m \le 50\)，其中 \(n\) 是列数，\(m\) 是每列最高的高度。
思路
\(\text{100pts}\)
单调栈做一下就完了。
代码
\(\text{100pts}\)
#include <bits/stdc++.h>
using i64 = long long;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
int n;
std::cin >> n;
std::vector<int> a(n + 1);
for (int i = 1; i <= n; i++) {
std::cin >> a[i];
}
std::vector<int> s(1, 0);
int ans = 0;
for (int i = 1; i <= n; i++) {
while (s.size() != 1 && a[s[s.size() - 1]] >= a[i]) {
s.pop_back();
}
s.push_back(i);
for (int j = 1; j <= s.size() - 1; j++) {
ans = std::max(ans, a[s[j]] * (s[s.size() - 1] - s[j - 1]));
}
}
std::cout << ans << "\n";
return 0;
}
T3
题意
有两支足球队，分别有 \(n\) 个人与 \(m\) 个人，你属于那只 \(n\) 个人的，给出每个人的坐标以及球门的坐标，射门的时间为球员与人的距离乘以二，传球的时间为两个球员之间的距离，但是若两个球员之间有另一支球队的人，也就是说三人位于同一直线上且中间的人是对方球队的，则无法传球，现在问你射门的最短时间是多少。
\(n \le 300\)，\(m \le 100\)。
思路
\(\text{100pts}\)
这一类问题都是可以归约到最短路上的。
我们把每个坐标都看成一个点，建图，考虑一下非法情况，然后直接跑最短路即可。由于这道题规模不大，最短路用 Floyd 跑一下就行了。时间复杂度为 \(O(n^2 m + n^3)\)。
判非法就枚举一下然后算一下斜率就好了，记得判斜率不存在。
代码
\(\text{100pts}\)
#include <bits/stdc++.h>
#include <algorithm>
#include <vector>
#include <iostream>
#include <cmath>
using i64 = long long;
using f80 = long double;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
static const f80 EPS = 1e-7;
int n, m;
std::pair<int, int> door;
std::cin >> door.first >> door.second >> n >> m;
std::vector<std::pair<int, int>> a(n), b(m);
for (auto &i : a) {
std::cin >> i.first >> i.second;
}
for (auto &i : b) {
std::cin >> i.first >> i.second;
}
a.push_back(door);
auto getDis = [&](int i, int j) {
return std::hypot(a[i].first - a[j].first, a[i].second - a[j].second);
};
std::vector<std::vector<f80>> dis(n + 1, std::vector<f80>(n + 1, 1e18));
for (int i = 0; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
bool flg = true;
for (int k = 0; k < m; k++) {
if (b[k].first < std::min(a[i].first, a[j].first)) {
continue;
}
if (b[k].first > std::max(a[i].first, a[j].first)) {
continue;
}
if (b[k].second < std::min(a[i].second, a[j].second)) {
continue;
}
if (b[k].second > std::max(a[i].second, a[j].second)) {
continue;
}
auto getK = [&](std::pair<int, int> p, std::pair<int, int> q) {
int x1 = p.first, x2 = q.first;
int y1 = p.second, y2 = q.second;
if (x1 == x2) {
return f80(-1);
}
return f80(y1 - y2) / (x1 - x2);
};
if (getK(a[i], a[j]) == -1) {
if (a[i].first == b[k].first) {
flg = false;
break;
}
} else {
if (fabs(getK(b[k], a[i]) - getK(b[k], a[j])) <= EPS) {
flg = false;
break;
}
}
}
if (flg) {
dis[i][j] = dis[j][i] = getDis(i, j) * (j == n ? 2 : 1);
}
}
}
for (int k = 0; k <= n; k++) {
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) {
dis[i][j] = std::min(dis[i][j], dis[i][k] + dis[k][j]);
}
}
}
std::cout << i64(std::round(dis[0][n])) << "\n";
return 0;
}
T4
题意
一个高度为 \(n\) 的塔，每层都是一个正方形且第 \(i\) 层边长为 \((n – i + 1)\)。第 \(i\) 层的第 \(j\) 行第 \(k\) 列的节点 \((i, j, k)\) 有一个权值 \(t_{i, j, k}\)，表示经过这个节点所需的时间。
每个节点可以按如下方法拓展：
- 拓展至同一层的四联通的节点中。
- 拓展至上一层的 \((i + 1, j, k)\)，\((i + 1, j + 1, k + 1)\)，\((i + 1, j + 1, k)\) 或 \((i + 1, j, k + 1)\) 节点中。
此外，还有 \(m\) 条暗道 \((i_s, j_s, k_s, i_t, j_t, k_t, w)\)，表示可以花费 \(w\) 直接从 \((i_s, j_s, k_s)\) 直接走到 \((i_t, j_t, k_t)\)。
你现在从 \((1, 1, 1)\) 开始走，问走到 \((n, 1, 1)\) 的最短时间是多少。
对于 \(50\%\) 的数据，\(n \le 5\)；
对于 \(100\%\) 的数据，\(n \le 100\)，\(m \le 50\)。
思路
\(\text{50pts}\)
考虑直接爆搜，时间复杂度为 \(O(n^8)\) 上下。
不过同机房有个老哥写爆搜加几个玄学剪枝过了 \(\text{90pts}\)，而我因为学校所拥有的 Fastest CPU In The World 而 T 了 3 个点，果然还是建议验题人自裁呢。
\(\text{100pts}\)
还是利用图论建模的思想，考虑给每个坐标重新编号，在能够拓展的节点之间连边，再把点权转成边权，然后跑一遍最短路就好了。
但是这个图是稠密的，最短路可能要写 SPFA 之类的，不过我在 Luogu 上用 Dijkstra 跑过了。
事实上当然也可以写记忆化搜索，时间复杂度更为优秀。
个人认为讲的再多不如一份写得清楚的代码，所以有关建图的细节建议直接看代码，不仅更加高效，而且能够提升代码的阅读能力。
代码
\(\text{100pts}\)
#include <bits/stdc++.h>
#include <vector>
#include <algorithm>
#include <queue>
#include <iostream>
using i64 = long long;
struct Graph {
const int INF = 0x3f3f3f3f;
int n, m;
std::vector<std::vector<std::pair<int, int>>> e;
std::vector<int> dis;
std::vector<bool> vis;
Graph(int n, int m = 0) {
this->n = n;
this->m = m;
e.resize(n);
dis.resize(n);
vis.resize(n);
return;
}
void add(int u, int v, int w) {
e[u].emplace_back(v, w);
return;
}
int dijkstra(int s, int t) {
dis.assign(n, INF);
vis.assign(n, false);
dis[s] = 0;
std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> q;
q.emplace(0, s);
while (!q.empty()) {
int u = q.top().second;
q.pop();
if (vis[u]) {
continue;
}
vis[u] = true;
for (auto i : e[u]) {
int v = i.first, w = i.second;
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
q.emplace(dis[v], v);
}
}
}
return dis[t];
}
};
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
int n, m;
std::cin >> n >> m;
Graph G(n * (n + 1) * (2 * n + 1) / 6 + 50);
int cnt = 0;
std::vector<std::vector<std::vector<int>>> mp(n + 1), t(n + 1);
for (int k = 1; k <= n; k++) {
int len = n - k + 1;
mp[k].resize(len, std::vector<int>(len));
t[k].resize(len, std::vector<int>(len));
for (int i = 0; i < len; i++) {
for (int j = 0; j < len; j++) {
mp[k][i][j] = ++cnt;
std::cin >> t[k][i][j];
}
}
}
std::vector<std::vector<int>> d1 = {{0, 0}, {1, 1}, {1, 0}, {0, 1}};
std::vector<std::vector<int>> d2 = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
for (int k = 1; k <= n; k++) {
int len = n - k + 1;
for (int i = 0; i < len; i++) {
for (int j = 0; j < len; j++) {
if (k != 1) {
for (auto p : d1) {
int dx = i + p[0], dy = j + p[1];
G.add(mp[k - 1][dx][dy], mp[k][i][j], t[k - 1][dx][dy]);
}
}
for (auto p : d2) {
int dx = i + p[0], dy = j + p[1];
if (dx < 0 || dy < 0 || dx >= len || dy >= len) {
continue;
}
G.add(mp[k][i][j], mp[k][dx][dy], t[k][i][j]);
}
}
}
}
for (int i = 1; i <= m; i++) {
int sfl, sx, sy, tfl, tx, ty, ti;
std::cin >> sfl >> sx >> sy >> tfl >> tx >> ty >> ti;
G.add(mp[sfl][sx - 1][sy - 1], mp[tfl][tx - 1][ty - 1], ti + t[sfl][sx - 1][sy - 1]);
}
std::cout << G.dijkstra(mp[1][0][0], mp[n][0][0]) + t[n][0][0] << "\n";
return 0;
}
3 月 15 日测试题解
这学校的评测机我是真的吐了，\(\text{380pts} \rightarrow \text{300pts}\)，电脑速度跟 BZOJ 有的一拼。
一句话总结：简单，过于简单，但是在练习读题能力上十分有用。
T1 挂分的原因是 在读入 \(3 \times 5 \times 10^5\) 的数据情况下超时了，而 T2 纯纯自己傻逼，T3 跟 T4 又是因为这台奇快无比的评测机 T 了 \(\text{60pts}\)。
std::cin我还能做出什么评价呢？等我退役之后一定要给学校搭一台好一点的服务器之类的当评测机。
T1
题意
一个长度为 \(s\) 的区间与 \(n\) 个操作，初始区间内每个值都赋为 \(1\)，每次操作给出三个整数 \(l\)，\(r\) 与 \(t\)，表示将 \([l, r]\) 内的数修改为 \(t\)，求最后得到的区间和。
\(s \le 2 \times 10^9\)，\(n \le 5 \times 10^5\)。保证给出的区间没有重叠。
思路
\(\text{100pts}\)
因为保证了给出的区间没有重叠，简单模拟即可，没有什么思维难度。初始化 \(ans = s\)，然后每次修改让 \(ans\) 加上 \((r – l + 1) \times (t – 1)\) 就做完了。
但是这道题的数据离谱到了在明确强调没有区间重叠的情况后，第 2 ~ 3 个测试点仍然出现了重叠情况，虽然我没有因此挂分，但是我还是很想问问验题人：你自认为你是一个合格的验题人吗？这种如此简单的数据都不愿意写程序检验一下，我真的不知道要这种验题人有什么用。
为什么我知道这道题数据有问题呢？因为我旁边的老哥写的是 ODT。
代码
\(\text{100pts}\)
#include <bits/stdc++.h>
#include <iostream>
using i64 = long long;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
int s, n;
std::cin >> s >> n;
i64 ans = s;
for (int i = 1; i <= n; i++) {
i64 l, r, t;
std::cin >> l >> r >> t;
ans += (r - l + 1) * (t - 1);
}
std::cout << ans << "\n";
return 0;
}
T2
题意
经典求最大矩形面积题。
\(n \le 10^5\)，\(m \le 50\)，其中 \(n\) 是列数，\(m\) 是每列最高的高度。
思路
\(\text{100pts}\)
单调栈做一下就完了。
代码
\(\text{100pts}\)
#include <bits/stdc++.h>
using i64 = long long;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
int n;
std::cin >> n;
std::vector<int> a(n + 1);
for (int i = 1; i <= n; i++) {
std::cin >> a[i];
}
std::vector<int> s(1, 0);
int ans = 0;
for (int i = 1; i <= n; i++) {
while (s.size() != 1 && a[s[s.size() - 1]] >= a[i]) {
s.pop_back();
}
s.push_back(i);
for (int j = 1; j <= s.size() - 1; j++) {
ans = std::max(ans, a[s[j]] * (s[s.size() - 1] - s[j - 1]));
}
}
std::cout << ans << "\n";
return 0;
}
T3
题意
有两支足球队，分别有 \(n\) 个人与 \(m\) 个人，你属于那只 \(n\) 个人的，给出每个人的坐标以及球门的坐标，射门的时间为球员与人的距离乘以二，传球的时间为两个球员之间的距离，但是若两个球员之间有另一支球队的人，也就是说三人位于同一直线上且中间的人是对方球队的，则无法传球，现在问你射门的最短时间是多少。
\(n \le 300\)，\(m \le 100\)。
思路
\(\text{100pts}\)
这一类问题都是可以归约到最短路上的。
我们把每个坐标都看成一个点，建图，考虑一下非法情况，然后直接跑最短路即可。由于这道题规模不大，最短路用 Floyd 跑一下就行了。时间复杂度为 \(O(n^2 m + n^3)\)。
判非法就枚举一下然后算一下斜率就好了，记得判斜率不存在。
代码
\(\text{100pts}\)
#include <bits/stdc++.h>
#include <algorithm>
#include <vector>
#include <iostream>
#include <cmath>
using i64 = long long;
using f80 = long double;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
static const f80 EPS = 1e-7;
int n, m;
std::pair<int, int> door;
std::cin >> door.first >> door.second >> n >> m;
std::vector<std::pair<int, int>> a(n), b(m);
for (auto &i : a) {
std::cin >> i.first >> i.second;
}
for (auto &i : b) {
std::cin >> i.first >> i.second;
}
a.push_back(door);
auto getDis = [&](int i, int j) {
return std::hypot(a[i].first - a[j].first, a[i].second - a[j].second);
};
std::vector<std::vector<f80>> dis(n + 1, std::vector<f80>(n + 1, 1e18));
for (int i = 0; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
bool flg = true;
for (int k = 0; k < m; k++) {
if (b[k].first < std::min(a[i].first, a[j].first)) {
continue;
}
if (b[k].first > std::max(a[i].first, a[j].first)) {
continue;
}
if (b[k].second < std::min(a[i].second, a[j].second)) {
continue;
}
if (b[k].second > std::max(a[i].second, a[j].second)) {
continue;
}
auto getK = [&](std::pair<int, int> p, std::pair<int, int> q) {
int x1 = p.first, x2 = q.first;
int y1 = p.second, y2 = q.second;
if (x1 == x2) {
return f80(-1);
}
return f80(y1 - y2) / (x1 - x2);
};
if (getK(a[i], a[j]) == -1) {
if (a[i].first == b[k].first) {
flg = false;
break;
}
} else {
if (fabs(getK(b[k], a[i]) - getK(b[k], a[j])) <= EPS) {
flg = false;
break;
}
}
}
if (flg) {
dis[i][j] = dis[j][i] = getDis(i, j) * (j == n ? 2 : 1);
}
}
}
for (int k = 0; k <= n; k++) {
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) {
dis[i][j] = std::min(dis[i][j], dis[i][k] + dis[k][j]);
}
}
}
std::cout << i64(std::round(dis[0][n])) << "\n";
return 0;
}
T4
题意
一个高度为 \(n\) 的塔，每层都是一个正方形且第 \(i\) 层边长为 \((n – i + 1)\)。第 \(i\) 层的第 \(j\) 行第 \(k\) 列的节点 \((i, j, k)\) 有一个权值 \(t_{i, j, k}\)，表示经过这个节点所需的时间。
每个节点可以按如下方法拓展：
- 拓展至同一层的四联通的节点中。
- 拓展至上一层的 \((i + 1, j, k)\)，\((i + 1, j + 1, k + 1)\)，\((i + 1, j + 1, k)\) 或 \((i + 1, j, k + 1)\) 节点中。
此外，还有 \(m\) 条暗道 \((i_s, j_s, k_s, i_t, j_t, k_t, w)\)，表示可以花费 \(w\) 直接从 \((i_s, j_s, k_s)\) 直接走到 \((i_t, j_t, k_t)\)。
你现在从 \((1, 1, 1)\) 开始走，问走到 \((n, 1, 1)\) 的最短时间是多少。
对于 \(50\%\) 的数据，\(n \le 5\)；
对于 \(100\%\) 的数据，\(n \le 100\)，\(m \le 50\)。
思路
\(\text{50pts}\)
考虑直接爆搜，时间复杂度为 \(O(n^8)\) 上下。
不过同机房有个老哥写爆搜加几个玄学剪枝过了 \(\text{90pts}\)，而我因为学校所拥有的 Fastest CPU In The World 而 T 了 3 个点，果然还是建议验题人自裁呢。
\(\text{100pts}\)
还是利用图论建模的思想，考虑给每个坐标重新编号，在能够拓展的节点之间连边，再把点权转成边权，然后跑一遍最短路就好了。
但是这个图是稠密的，最短路可能要写 SPFA 之类的，不过我在 Luogu 上用 Dijkstra 跑过了。
事实上当然也可以写记忆化搜索，时间复杂度更为优秀。
个人认为讲的再多不如一份写得清楚的代码，所以有关建图的细节建议直接看代码，不仅更加高效，而且能够提升代码的阅读能力。
代码
\(\text{100pts}\)
#include <bits/stdc++.h>
#include <vector>
#include <algorithm>
#include <queue>
#include <iostream>
using i64 = long long;
struct Graph {
const int INF = 0x3f3f3f3f;
int n, m;
std::vector<std::vector<std::pair<int, int>>> e;
std::vector<int> dis;
std::vector<bool> vis;
Graph(int n, int m = 0) {
this->n = n;
this->m = m;
e.resize(n);
dis.resize(n);
vis.resize(n);
return;
}
void add(int u, int v, int w) {
e[u].emplace_back(v, w);
return;
}
int dijkstra(int s, int t) {
dis.assign(n, INF);
vis.assign(n, false);
dis[s] = 0;
std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> q;
q.emplace(0, s);
while (!q.empty()) {
int u = q.top().second;
q.pop();
if (vis[u]) {
continue;
}
vis[u] = true;
for (auto i : e[u]) {
int v = i.first, w = i.second;
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
q.emplace(dis[v], v);
}
}
}
return dis[t];
}
};
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
int n, m;
std::cin >> n >> m;
Graph G(n * (n + 1) * (2 * n + 1) / 6 + 50);
int cnt = 0;
std::vector<std::vector<std::vector<int>>> mp(n + 1), t(n + 1);
for (int k = 1; k <= n; k++) {
int len = n - k + 1;
mp[k].resize(len, std::vector<int>(len));
t[k].resize(len, std::vector<int>(len));
for (int i = 0; i < len; i++) {
for (int j = 0; j < len; j++) {
mp[k][i][j] = ++cnt;
std::cin >> t[k][i][j];
}
}
}
std::vector<std::vector<int>> d1 = {{0, 0}, {1, 1}, {1, 0}, {0, 1}};
std::vector<std::vector<int>> d2 = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
for (int k = 1; k <= n; k++) {
int len = n - k + 1;
for (int i = 0; i < len; i++) {
for (int j = 0; j < len; j++) {
if (k != 1) {
for (auto p : d1) {
int dx = i + p[0], dy = j + p[1];
G.add(mp[k - 1][dx][dy], mp[k][i][j], t[k - 1][dx][dy]);
}
}
for (auto p : d2) {
int dx = i + p[0], dy = j + p[1];
if (dx < 0 || dy < 0 || dx >= len || dy >= len) {
continue;
}
G.add(mp[k][i][j], mp[k][dx][dy], t[k][i][j]);
}
}
}
}
for (int i = 1; i <= m; i++) {
int sfl, sx, sy, tfl, tx, ty, ti;
std::cin >> sfl >> sx >> sy >> tfl >> tx >> ty >> ti;
G.add(mp[sfl][sx - 1][sy - 1], mp[tfl][tx - 1][ty - 1], ti + t[sfl][sx - 1][sy - 1]);
}
std::cout << G.dijkstra(mp[1][0][0], mp[n][0][0]) + t[n][0][0] << "\n";
return 0;
}