美团笔试4.8(5/5 附题面)
题面在代码里
A. 换座位
简单模拟换完新座位是什么样子，跟原来的座位对比一下，难度在于读题。
#include<bits/stdc++.h>
#define debug(x) std::cerr << "debug: " << x << '\n';
#define all(x) x.begin(), x.end()
using pii = std::pair<int, int>;
using i64 = long long;
using vi = std::vector<int>;
using vp = std::vector<pii>;
using vl = std::vector<i64>;
std::string s[205][205], change[205][205];
void solve(int cas) {
int n, m, a;
std::cin >> n >> m >> a;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
std::cin >> s[i][j];
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int r = (i - 1 + n) % n, c = (j - 1 + m) % m;
change[i][j] = s[r][c];
std::cerr << change[i][j];
}
std::cerr << '\n';
}
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
for (int k = 0; k < a; k++) {
if (s[i][j][k] ^ change[i][j][k]) {
++ans;
}
}
}
}
std::cout << ans << '\n';
}
int main() {
int T = 1;
//std::cin >> T;
while (T--) {
solve(T);
}
return 0;
}
/*
小团班级的座位排成了 n 行（行从 1 到 n 编号），共有 m 个大列（大列从 1 到 m 编号），每个大列中有 a 个小列（小列从 1 到 a 编号），大列与大列之间有一个过道。小团的班级每周会换一次座位，首先所有同学都换到后一行，最后一行的同学换到第一行，然后所有同学都移动到自己右边的那个大列的相同小列上，在最右大列的同学移动到最左大列。换句话说，对于坐在第 i<n 行的同学，新位置在第 i+1 行，如果 i=n，那么新位置在第一行；对于坐在第 j<m 大列的同学，新位置在第 j+1 大列，如果 j=m，那么新位置在第一大列；对于坐在第 k 小列的同学，新位置仍然在第 k 小列。
小团的学校最近换了一批学生桌椅。这批学生桌椅的优点在于可以调节桌子的高度，一些同学调整了桌子高度，但是另一些没有。这样换座就变得麻烦了起来，如果一位调整了桌子高度的同学换到了未调整桌子高度同学的位置，他就会调整新位置的桌子到他想要的高度，而一位没有调整桌子高度的同学换到了调整过桌子高度同学的位置，他也会调整新位置的桌子高度，使其恢复原高度。
现在小团的班级要进行换座位了，给出换座位前班级所有桌子的情况，小团想知道，换一次位置后，有多少同学需要重新调整桌子高度。
输入描述
输入第一行包含三个数 n, m, a，意义如题目所示。
接下来 n 行，每行 m 个长度为 a 的 01 字符串，表示目前小团班上的桌子情况。其中 0 表示这个位置未调节桌子高度，1 表示已调节桌子高度。
对于全部数据，1 ≤ n, m ≤ 200, n × m ≥ 2, 1 ≤ a ≤ 5。
输出描述
输出一行一个整数，表示换座位后有多少同学需要重新调整桌子高度。
样例输入
3 3 2
01 10 00
10 00 11
01 00 00
样例输出
8
*/
B. 最长路径
在树上，要切掉一条边，那么原图被划分成两颗子树，以u, v为根在两个子树里找距离最远的点。
#include<bits/stdc++.h>
#define debug(x) std::cerr << "debug: " << x << '\n';
#define all(x) x.begin(), x.end()
using pii = std::pair<int, int>;
using i64 = long long;
using vi = std::vector<int>;
using vp = std::vector<pii>;
using vl = std::vector<i64>;
vi G[100005];
int dist[100005], res = 0;
void dfs(int u, int par) {
res = std::max(res, dist[u]);
for (auto v : G[u]) {
if (v == par) {
continue;
}
dist[v] = dist[u] + 1;
dfs(v, u);
}
}
void solve(int cas) {
int n;
std::cin >> n;
for (int i = 2; i <= n; i++) {
int fa;
std::cin >> fa;
G[fa].emplace_back(i);
G[i].emplace_back(fa);
}
int from, to;
int ans = 1;
std::cin >> from >> to;
dfs(from, to);
ans += res;
res = 0;
dfs(to, from);
ans += res;
std::cout << ans << '\n';
}
int main() {
int T = 1;
//std::cin >> T;
while (T--) {
solve(T);
}
return 0;
}
/*
题目描述：
有一棵 n 个节点的树，有一条边被选定。小美想知道对于所有经过这条选定边的所有树上简单路径，最长的那条有多长。一条简单的路径的长度指这条简单路径上的边的个数。
输入描述
第一行一个整数 n，表示树的节点个数。
第二行 n-1 个整数，第 i 个整数 pi 表示节点 i+1 和 pi 之间有一条边相连。
第三行两个整数 x, y，表示这条选定的边。保证这条边一定是树上的一条边。
对于全部数据，2 ≤ n ≤ 1e5, 1 ≤ pi ≤ n, 1 ≤ x, y ≤ n, x ≠ y。保证输入数据正确描述一棵树，并且 (x, y) 是树上的一条边。
输出描述
输出一行，一个整数，表示所有经过选定边的树上简单路径中，最长的那条的长度。
样例输入
7
1 2 3 4 5 3
3 7
样例输出
4
*/
C. 水果分配
简单dp，假设当前考虑到第 i 个水果，那么上一个行程果篮的位置为 j，只需要求出区间[j + 1, i] 的最大值和最小值即可，转移式为 dp[i] = min(dp[i], dp[j] +cal(j + 1, i).
做这道题的时候有个小插曲，一开始看到的时间限制是3s，后面好像后台偷偷把时间改成1s了。因为我不会背 st 表怎么写，所以写了个线段树时间复杂度O(nmlogn) 超时了，用两个 cache 去存查询过的点记忆化也不行，最后直接暴力求以 i 为起点，j 为终点的最大值，最小值。正确写法应该是开 1e4 个 vector，每个 vector 的大小都是 m，但是我开了1e8的数组，好像编译器帮我优化了那些没用到的空间..
#include<bits/stdc++.h>
#define debug(x) std::cerr << "debug: " << x << '\n';
#define all(x) x.begin(), x.end()
using pii = std::pair<int, int>;
using i64 = long long;
using vi = std::vector<int>;
using vp = std::vector<pii>;
using vl = std::vector<i64>;
int A[10005];
i64 dp[10005];
int cache_max[10005][10005], cache_min[10005][10005];
//std::unordered_map<int, int> cache_min[10005];
// class SegTree {
// private:
// struct Node {
// int l, r, Max, Min;
// };
// std::vector<Node> t;
// public:
// SegTree(int n) {
// t.resize(4 * n + 1);
// }
// void push_up(int rt) {
// t[rt].Max = std::max(t[rt << 1].Max, t[rt << 1 | 1].Max);
// t[rt].Min = std::min(t[rt << 1].Min, t[rt << 1 | 1].Min);
// }
// void build(int rt, int l, int r) {
// t[rt].l = l, t[rt].r = r;
// if (l == r) {
// t[rt].Max = t[rt].Min = A[l];
// return ;
// }
// int mid = (t[rt].l + t[rt].r) >> 1;
// build(rt << 1, l, mid);
// build(rt << 1 | 1, mid + 1, r);
// push_up(rt);
// }
// int query_max(int rt, int ql, int qr) {
// if (cache_max[ql].count(qr)) {
// return cache_max[ql][qr];
// }
// if (ql <= t[rt].l and qr >= t[rt].r) {
// return t[rt].Max;
// }
// int mid = (t[rt].l + t[rt].r) >> 1;
// if (ql > mid) {
// return query_max(rt << 1 | 1, ql, qr);
// }
// if (qr <= mid) {
// return query_max(rt << 1, ql, qr);
// }
// return std::max(query_max(rt << 1, ql, qr), query_max(rt << 1 | 1, ql, qr));
// }
// int query_min(int rt, int ql, int qr) {
// if (cache_min[ql].count(qr)) {
// return cache_min[ql][qr];
// }
// if (ql <= t[rt].l and qr >= t[rt].r) {
// return t[rt].Min;
// }
// int mid = (t[rt].l + t[rt].r) >> 1;
// if (ql > mid) {
// return query_min(rt << 1 | 1, ql, qr);
// }
// if (qr <= mid) {
// return query_min(rt << 1, ql, qr);
// }
// return std::min(query_min(rt << 1, ql, qr), query_min(rt << 1 | 1, ql, qr));
// }
// };
void solve(int cas) {
int n, m, s;
std::cin >> n >> m >> s;
for (int i = 1; i <= n; i++) {
std::cin >> A[i];
dp[i] = 1e18;
}
for (int i = 1; i <= n; i++) {
int max_obj = 0, min_obj = 1e9;
for (int j = i; j <= n; j++) {
max_obj = std::max(max_obj, A[j]);
min_obj = std::min(min_obj, A[j]);
cache_max[i][j] = max_obj;
cache_min[i][j] = min_obj;
}
}
// SegTree T(n);
dp[0] = 0;
// T.build(1, 1, n);
auto cal = [&](int l, int r) {
// auto Max = T.query_max(1, l, r), Min = T.query_min(1, l, r);
// cache_max[l][r] = Max;
// cache_min[l][r] = Min;
auto Max = cache_max[l][r], Min = cache_min[l][r];
int k = r - l + 1;
return 1LL * k * ((Max + Min) / 2) + s;
};
for (int i = 1; i <= n; i++) {
for (int last = std::max(i - m, 0); last <= i - 1; last++) {
dp[i] = std::min(dp[i], dp[last] + cal(last + 1, i));
}
}
std::cout << dp[n] << '\n';
}
int main() {
int T = 1;
//std::cin >> T;
while (T--) {
solve(T);
}
return 0;
}
/*
小美不干外卖配送了，转行开了一家水果店。
一天她接到了一个大单，客户订购了 n 个水果，并且要求打包成多个果篮，一个果篮最多装 m 个水果。
为了包装方便，水果按从 1 到 n 编号，同一个果篮里装的水果编号必须是连续的。果篮的成本与容积成线性关系。为了估计容积，小美简单地用样本中点估计了一下。具体来说，假设一个果篮中装的最大的水果体积是 u，最小的是 v，那么这个果篮的成本就是 k × floor((u+v)/2) + s，其中 k 是果篮中装入水果的个数，s 是一个常数，floor(x) 是下取整函数，比如 floor(3.8)=3, floor(2)=2。
客户并没有规定果篮的数量，但是希望果篮的成本越小越好，毕竟买水果就很贵了。请求出小美打包这 n 个水果所用的最小花费。
输入描述
第一行三个正整数 n, m, s。意义如题面所示。
第二行 n 个正整数 a1, a2, ..., an，表示每个水果的体积。
对于全部数据，1 ≤ n ≤ 1e4, 1 ≤ m ≤ 1e3, m ≤ n, 1 ≤ ai, s ≤ 1e4。
输出描述
输出一个整数，表示打包这 n 个水果果篮的最小成本。
样例输入
6 4 3
1 4 5 1 4 1
样例输出
21
*/
D. 地雷
考虑先对每个点求离他最近的地雷的距离，然后类似于 Dijkstra 的做法跑个 dp 就行了。
#include<bits/stdc++.h>
#define debug(x) std::cerr << "debug: " << x << '\n';
#define all(x) x.begin(), x.end()
using pii = std::pair<int, int>;
using i64 = long long;
using vi = std::vector<int>;
using vp = std::vector<pii>;
using vl = std::vector<i64>;
int X[405], Y[405];
int dist[505][505], dp[505][505];
bool vis[505][505];
int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
void solve(int cas) {
int n, m, k;
std::cin >> n >> m >> k;
memset(dist, 0x3f, sizeof(dist));
for (int i = 1; i <= k; i++) {
std::cin >> X[i] >> Y[i];
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
for (int u = 1; u <= k; u++) {
int distance = std::abs(i - X[u]) + std::abs(j - Y[u]);
dist[i][j] = std::min(dist[i][j], distance);
}
}
}
int _x1, _y1, _x2, _y2;
std::cin >> _x1 >> _y1 >> _x2 >> _y2;
std::priority_queue<std::tuple<int, int, int> > que;
que.emplace(dist[_x1][_y1], _x1, _y1);
dp[_x1][_y1] = dist[_x1][_y1];
while (!que.empty()) {
auto [cost, x, y] = que.top();
que.pop();
if (vis[x][y]) {
continue;
}
vis[x][y] = true;
for (int i = 0; i < 4; i++) {
int nx = x + dir[i][0], ny = y + dir[i][1];
if (nx <= 0 or ny <= 0 or nx > n or ny > m) {
continue;
}
if (!vis[nx][ny] and dp[nx][ny] < std::min(dist[nx][ny], dp[x][y])) {
dp[nx][ny] = std::min(dist[nx][ny], dp[x][y]);
que.emplace(dp[nx][ny], nx, ny);
}
}
}
std::cout << dp[_x2][_y2] << '\n';
}
int main() {
int T = 1;
//std::cin >> T;
while (T--) {
solve(T);
}
return 0;
}
/*
题目描述：
有一片 n × m 大小的网格，共 n 行 m 列，其中行和列都用从 1 开始的整数编号，网格中有 k 个格子中埋有地雷。我们记第 a 行第 b 列的格子为 (a, b)。小美现在位于 (x1, y1)，她想要移动到 (x2, y2) 处。小美每次移动可以移动到与她所处格子的相邻的一格中，形式化地说，如果小美位于 (x, y)，则小美可以移动到 (x-1, y), (x+1, y), (x, y-1), (x, y+1) 的格子之一，但小美不能移动到网格之外。
小美想要在移动过程中，离这些地雷越远越好，而不是走最短路径。这里定义两个格子之间的距离为曼哈顿距离，即格子 (a, b) 和 (c, d) 之间的距离是 |a-c|+|b-d|。小美想知道，移动中与地雷之间距离的最小值最大可能是多少。请注意，如果无论小美如何移动，都会进入一个有地雷的格子的话，这个最大可能值为 0。
输入描述
第一行三个整数 n, m, k，分别表示网格的行数，列数和地雷个数。
接下来 k 行，每行两个整数 p, q，表示一个地雷放置在格子 (p, q) 中。任意两地雷的放置位置不同。
接下来一行四个整数 x1, y1, x2, y2，表示小美的出发位置和目的位置。保证小美的出发位置和目的位置上没有地雷。
对于全部数据，1 ≤ n, m ≤ 500, n × m ≥ 3, 1 ≤ k ≤ min{n × m-2, 400}, 1 ≤ p, x1, x2 ≤ n, 1 ≤ q, y1, y2 ≤ m, (x1, y1) ≠ (x2, y2)，保证 (x1, y1) 和 (x2, y2) 中没有地雷，并且一个格子中最多放置一个地雷。
输出描述
输出一行一个整数，表示移动过程中与地雷之间距离的最小值的可能最大值。
样例输入
5 6 2
2 1
2 3
1 1 5 1
样例输出
1
3 3 9
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
1 1 3 3
*/
E. 划分彩色树
感觉跟 B 题差不多，因为求的是有多少条边能满足条件，不妨枚举边，先预处理子树下RGB三种颜色的个数就可以了。
#include<bits/stdc++.h>
#define debug(x) std::cerr << "debug: " << x << '\n';
#define all(x) x.begin(), x.end()
using pii = std::pair<int, int>;
using i64 = long long;
using vi = std::vector<int>;
using vp = std::vector<pii>;
using vl = std::vector<i64>;
int tot;
vi G[100005];
char color[100005];
struct Edge {
int u, v;
} edge[100005];
int szR[100005], szG[100005], szB[100005];
void dfs(int u, int par) {
szR[u] = color[u] == 'R';
szG[u] = color[u] == 'G';
szB[u] = color[u] == 'B';
for (auto v : G[u]) {
if (v == par) {
continue;
}
dfs(v, u);
szR[u] += szR[v];
szG[u] += szG[v];
szB[u] += szB[v];
}
}
void solve(int cas) {
int n;
std::cin >> n;
for (int i = 2; i <= n; i++) {
int fa;
std::cin >> fa;
++tot;
edge[tot].u = i, edge[tot].v = fa;
G[i].emplace_back(fa);
G[fa].emplace_back(i);
}
std::string s;
std::cin >> s;
s = ' ' + s;
int R = 0, G = 0, B = 0;
for (int i = 1; i <= n; i++) {
color[i] = s[i];
R += color[i] == 'R';
G += color[i] == 'G';
B += color[i] == 'B';
}
dfs(1, 0);
int ans = 0;
for (int i = 1; i <= tot; i++) {
int u = edge[i].u, v = edge[i].v;
if (szR[u] and szG[u] and szB[u]) {
if (R - szR[u] > 0 and G - szG[u] > 0 and B - szB[u] > 0) {
++ans;
}
}
}
std::cout << ans << '\n';
}
int main() {
int T = 1;
//std::cin >> T;
while (T--) {
solve(T);
}
return 0;
}
/*
题目描述：
有一棵 n 个节点的树，树上每个点都有红绿蓝三种颜色中的一种。定义一棵树是多彩的，当且仅当这棵树同时存在一个红色节点，一个蓝色节点和一个绿色节点。
保证最初这棵树是多彩的，现在要砍掉这棵树的某一条边，请问有多少种砍法，使得砍完之后形成的两棵树都是多彩的。
输入描述
第一行一个整数 n，表示节点个数。
第二行 n-1 个整数 p2, p3, ..., pn，pi 表示树上 i 和 pi 两点之间有一条边。保证给出的一定是一棵树。
第三行一个长度为 n 的字符串，第 i 个字符表示第 i 个节点的初始颜色。其中 R 表示红色，G 表示绿色，B 表示蓝色。保证字符串只由这三种大写字母构成。
对于全部数据，3≤n≤1e5。
输出描述
输出一行，一个正整数，表示答案。
样例输入
7
1 2 3 1 5 5
GBGRRBB
样例输出
1
*/
#美团4.8笔试##美团##软件开发2023笔面经#一些比赛的题解 文章被收录于专栏
一些比赛的题解
