3.23 总结
T1
什么宝宝题/bangbangt 。
题面有点抽象，但其实就是找到价格最小的然后再乘上一个 \(1000\) 就行了。
#include <bits/stdc++.h>
using ll = long long;
#define f first
#define s second
const int inf = (1 << 30) - 1;
const ll INF = 1ll << 62;const int N = 110;
struct node {double x, y, p;
}a[N];
double mi = 1e18;
int n;int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr), std::cout.tie(nullptr);std::cin >> a[0].x >> a[0].y, a[0].p = a[0].x / a[0].y, mi = std::min(mi, a[0].p);std::cin >> n;for (int i = 1; i <= n; i++) std::cin >> a[i].x >> a[i].y, a[i].p = a[i].x / a[i].y, mi = std::min(mi, a[i].p);std::cout << std::fixed << std::setprecision(2) << mi * 1000. << '\n';//
}
笑点：我旁边的老哥因为不会 double 输出导致 T1 没做出来。
T2
也是挺简单。
就是模拟一下，然后再对于边界取 \(\max/\min\) ，然后输出。
一个小trick：对于这种边界不确定的题，倒着存往往比正着存简单。
#include <bits/stdc++.h>
using ll = long long;
#define f first
#define s second
const int inf = (1 << 30) - 1;
const ll INF = 1ll << 62;const int N = 110;
int n, mx = -inf, mi = inf;
std::string s;
struct Map{char a[N * 2];char &operator [] (int pos) {mx = std::max(pos, mx), mi = std::min(pos, mi);return a[pos + 100];}
} map[N];int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr), std::cout.tie(nullptr);std::cin >> n >> s;int now = 0;for (int i = 0; i < n; ++i) {if (s[i] == '+') map[i][now++] = '/';else if (s[i] == '-') map[i][--now] = '\\';else map[i][now] = '_';}for (int i = mx; i >= mi; i--) for (int j = 0; j < n; ++j) {std::cout << (map[j][i] ? map[j][i] : '.');if (j == n - 1) std::cout << '\n';}
}
PS：赛时造了一个全是加的数据，看完感觉自己能当上顶富了。
T3
就是二维BFS板子再加上一维，几分钟秒了。
第三题放这题是hyw。
#include <bits/stdc++.h>
using ll = long long;
#define f first
#define s second
const int inf = (1 << 30) - 1;
const ll INF = 1ll << 62;const int N = 110;
const int dx[6] = {1, -1, 0, 0, 0, 0};
const int dy[6] = {0, 0, 1, -1, 0, 0};
const int dz[6] = {0, 0, 0, 0, 1, -1};
struct node {int x, y, z;
};
bool vis[N][N][N];
int n, sx, sy, sz, tx, ty, tz, map[N][N][N], dis[N][N][N];
std::queue<node> q;int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr), std::cout.tie(nullptr);std::cin >> n >> sx >> sy >> sz >> tx >> ty >> tz;for (int z = 1; z <= n; z++) for (int x = 1; x <= n; x++) {std::string s;std::cin >> s, s = ' ' + s;for (int y = 1; y <= n; y++) map[x][y][z] = s[y] - '0';}for (int x = 1; x <= n; x++) for (int y = 1; y <= n; y++) for (int z = 1; z <= n; z++) dis[x][y][z] = inf;dis[sx][sy][sz] = 0;q.push({sx, sy, sz});while (!q.empty()) {node u = q.front();q.pop();if (vis[u.x][u.y][u.z]) continue;vis[u.x][u.y][u.z] = true;for (int i = 0; i < 6; i++) {int nx = u.x + dx[i], ny = u.y + dy[i], nz = u.z + dz[i];if (nx < 1 || ny < 1 || nz < 1 || nx > n || ny > n || nz > n || map[nx][ny][nz]) continue;if (dis[nx][ny][nz] > dis[u.x][u.y][u.z] + 1) {dis[nx][ny][nz] = dis[u.x][u.y][u.z] + 1;q.push({nx, ny, nz});}}}std::cout << (dis[tx][ty][tz] == inf ? -1 : dis[tx][ty][tz]) << '\n';
}
T4
总感觉之前在雅礼考试做过类似的，但是好像暂时我知道的除了我和小胖，好像其他人都没印象。
总之那道题好像就也是每个学生什么时候来，什么时候走，然后有老师上课，然后还有一些其他的。
那题的做法就是按学生什么时候来排序，然后用优先队列维护学生什么时候走，然后再来一些操作。
简直跟这题有80%的相似处。
而这题做法也很简单，就是按学生什么时候来排序，然后用优先队列维护学生什么时候走，然后如果有 k 个学生就将当前最后来的和最先走到做个差值。
#include <bits/stdc++.h>
using ll = long long;
#define f first
#define s second
const int inf = (1 << 30) - 1;
const ll INF = 1ll << 62;const int N = 3e5 + 10;
int n, k;
ll ans;
std::pair<ll, ll> a[N];
std::priority_queue<ll, std::vector<ll>, std::greater<ll>> q;int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr), std::cout.tie(nullptr);std::cin >> n >> k;for (int i = 1; i <= n; i++) std::cin >> a[i].f >> a[i].s;std::sort(a + 1, a + n + 1);for (int i = 1; i <= n; i++) {q.push(a[i].s);if ((int)q.size() > k) q.pop();if ((int)q.size() == k && q.top() > a[i].f) ans = std::max(ans, q.top() - a[i].f);}std::cout << ans << '\n';
}