美团8.12笔试
挺简单的,二十多分钟ak,美滋滋。
第一题
给你一个排列 和两个数 问你这两个数在排列里是不是相邻
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; vector<int> v(n); for (auto &x : v) cin >> x; int a, b; cin >> a >> b; for (int i = 0; i < n; i++) { if (v[i] == a) { if (i - 1 >= 0 && v[i - 1] == b || i + 1 < n && v[i + 1] == b) { puts("Yes"); } else { puts("No"); } return 0; } } return 0; }
第二题
有一个环 相邻两个数有一个距离 给你两个点 问从a走到b最短距离多少
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; vector<long long> v(n); long long sum = 0; for (auto &x : v) cin >> x, sum += x; int a, b; cin >> a >> b; a--, b--; if (a > b) swap(a, b); long long now = 0; for(int i=a;i<b;i++)now+=v[i]; cout<<min(now, sum-now); return 0;
第三题
给你一个矩阵 你可以横着或者竖着把他分为两个矩阵 问这两个矩阵和的差的绝对值的最小值
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; vector<long long> a(n), b(m); long long sum = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { int x; cin >> x; a[i] += x; b[j] += x; sum += x; } } long long ans = sum; long long now = 0; for (int i = 0; i < n; i++) { now += a[i]; ans = min(ans, abs(sum - 2 * now)); } now=0; for (int i = 0; i < m; i++) { now += b[i]; ans = min(ans, abs(sum - 2 * now)); } cout<<ans; return 0; }
第四题
给你一个字符串 你要把他修改为一个矩阵 矩阵长宽乘积得是字符串长度 然后矩阵每行连接起来是原来的字符串 问这个矩阵里联通块最小值 矩阵里上下左右相邻的字符可以连通
#include <bits/stdc++.h> using namespace std; int nmove[][2] = {1, 0, 0, 1, -1, 0, 0, -1}; int cal(const vector<string>& v) { int n = v.size(); int m = v[0].size(); int ret = 0; vector<vector<bool>> vis(n, vector<bool>(m)); auto dfs = [&](auto& dfs, int x, int y, char c) { if (x < 0 || x >= n || y < 0 || y >= m || vis[x][y] || v[x][y] != c) return; vis[x][y] = true; for (int i = 0; i < 4; i++) dfs(dfs, x + nmove[i][0], y + nmove[i][1], c); }; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (vis[i][j]) continue; ret++; dfs(dfs, i,j,v[i][j]); } } return ret; } int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; string s; cin >> s; int ans = n; for (int i = 1; i <= n; i++) { if (n % i) continue; vector<string> v(i); int len = n / i; for (int j = 0; j < i; j++) { v[j] = s.substr(j * len, len); } ans = min(ans, cal(v)); } cout << ans; return 0; }
第五题
给你一棵树 树上两个白色的相邻点如果权值乘积是一个完全平方数 那就可以把他们染红 一开始所有点都是白色 问最后树里红色节点最多有多少个
#include <bits/stdc++.h> using namespace std; const int MAXN = 1e5 + 5; vector<int> g[MAXN]; long long square(long long x) { return x * x; } bool check(long long x) { long long t = sqrt(x); return square(t) == x || square(t - 1) == x || square(t + 1) == x; } int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; vector<long long> a(n); vector<long long> dp0(n); vector<long long> dp1(n); for (auto &x : a) cin >> x; for (int i = 1; i < n; i++) { int a, b; cin >> a >> b; a--,b--; g[a].push_back(b); g[b].push_back(a); } auto dfs = [&](auto &dfs, int now, int fa) -> void { for (auto x : g[now]) if (x != fa) { dfs(dfs, x, now); dp0[now] += max(dp1[x], dp0[x]); } for (auto x : g[now]) if (x != fa && check(a[now] * a[x])) { dp1[now] = max(dp1[now], dp0[now] - max(dp1[x], dp0[x]) + dp0[x] + 2); } }; dfs(dfs, 0, 0); cout << max(dp0[0], dp1[0]); return 0; }#美团信息集散地#