美团2024年秋招第一场笔试【算法】个人题解
在牛客刷到了，随便看下哈，部分题可能有更优做法（懒得想了 or 想不出来）。
小美的因子查询
小美对偶数因子很感兴趣，她将进行 次询问，每次都会给出一个正整数 ，请你告诉她 是否存在至少一个偶数因子。也就是说 是否存在某个因子是偶数。
题解：判断 是否为偶数即可，单组查询复杂度 。
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define endl '\n'
constexpr i64 Mod = 1000000007;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void solve() {
int n;
cin >> n;
cout << ((~n & 1) ? "YES" : "NO") << endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
小美的密码
小美准备登录美团，需要输入密码，小美忘记了密码，只记得密码可能是 个字符串中的一个。小美会按照密码的长度从小到大依次尝试每个字符串，对于相同长度的字符串，小美随机尝试，并且相同的密码只会尝试一次。小美想知道，她最少需要尝试多少次才能登录成功，最多需要尝试多少次才能登录成功。小美不会重新尝试已经尝试过的字符串。成功登录后会立即停止尝试。
题解：暴力统计每种长度的字符串有多少，然后累加即可，注意去重。复杂度 。
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define endl '\n'
constexpr i64 Mod = 1000000007;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void solve() {
int n;
cin >> n;
string s;
cin >> s;
vector<int> len(1005, 0);
map<string, bool> mp;
while (n--) {
string a;
cin >> a;
if (mp.count(a)) {
continue;
}
len[a.size()]++;
mp[a] = true;
}
int x = 0, y = 0;
for (int i = 1; i < s.size(); i++) {
x += len[i];
y += len[i];
}
x++;
y += len[s.size()];
cout << x << " " << y << endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
小美的数组删除
小美有一个长度为 的数组 ，他可以对数组进行如下操作：
● 删除第一个元素 ，同时数组的长度减一，花费为 。
● 删除整个数组，花费为 。
小美想知道将 数组全部清空的最小代价是多少，请你帮帮他吧。
题解：问题在于求解区间 ，这个东西做法很多，我用的是可持久化线段树，建树后暴力枚举即可。单组复杂度 。
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define endl '\n'
constexpr i64 Mod = 1000000007;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
constexpr int N = 2e5 + 5;
int tot = 0;
struct node {
int ls, rs;
int v;
} seg[N * 24];
int rt[N], a[N];
void pushup(int k) {
seg[k].v = min(seg[seg[k].ls].v, seg[seg[k].rs].v);
}
int modify(int old, int l, int r, int pos, int v) {
int p = ++tot;
seg[p] = seg[old];
if (l == r) {
seg[p].v = v;
return p;
}
int mid = (l + r) >> 1;
if (pos <= mid) {
seg[p].ls = modify(seg[old].ls, l, mid, pos, v);
} else {
seg[p].rs = modify(seg[old].rs, mid + 1, r, pos, v);
}
pushup(p);
return p;
}
int query(int p, int l, int r, int pos) {
if (l == r) {
return l;
}
int mid = (l + r) >> 1;
if (seg[seg[p].ls].v < pos) {
return query(seg[p].ls, l, mid, pos);
} else {
return query(seg[p].rs, mid + 1, r, pos);
}
}
void solve() {
int n;
i64 k, x;
cin >> n >> k >> x;
for (int i = 1; i <= n; i++) {
cin >> a[i];
rt[i] = modify(rt[i - 1], 0, n, a[i], i);
}
i64 ans = 1LL * query(rt[n], 0, n, 1) * k;
for (int i = 2; i <= n; i++) {
i64 cur = 1LL * (i - 1) * x;
cur += 1LL * query(rt[n], 0, n, i) * k;
ans = min(ans, cur);
}
i64 cur = 1LL * n * x;
ans = min(ans, cur);
cout << ans << endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
小美和大富翁
小美在玩《大富翁》游戏，游戏中有 个城市排成一排，编号从 到 , 第 个城市上有一个数字 , 表示到达第 个城市可以获得 枚金币。
每一轮开始时小美会获得四张卡牌，分别可以跳跃 、、、 个城市，例如小美可以从城市 跳跃 个城市到达城市 。当小美使用完这 张卡牌后，会开启新的一轮。
初始时，小美拥有 枚金币，在任意时刻，小美的金币数量都必须大于等于 , 小美想知道她从第 个城市出发，到达第 个城市最多可以获得多少枚金币。
题解：这题显然是个 ，由于跳跃的方式一共只有四种，考虑状态压缩，将跳跃方式用四位二进制表示，该位为 表示已经使用过对应的卡牌。设 表示跳到第 个点时，使用卡牌的情况为 时可以获得的最多的金币数量。对应的转移是比较简单的，分为两种情况：之前未使用过这张卡牌，或者已经使用了所有卡牌并开启了新的一轮。复杂度 。
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define endl '\n'
constexpr i64 Mod = 1000000007;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void solve() {
int n;
cin >> n;
vector<i64> g(n + 1);
for (int i = 1; i <= n; i++) {
cin >> g[i];
}
vector<vector<i64>> dp(n + 1, vector<i64> (1 << 4, -1));
dp[0][0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < 4; j++) {
if (i < j + 1) {
continue;
}
for (int k = 0; k < (1 << 4); k++) {
if (!(k & (1 << j)) && dp[i - (j + 1)][k] >= 0) {
dp[i][k | (1 << j)] = max(dp[i][k | (1 << j)], dp[i - (j + 1)][k] + g[i]);
} else if (k == (1 << 4) - 1 && dp[i - (j + 1)][k] >= 0) {
dp[i][1 << j] = max(dp[i][1 << j], dp[i - (j + 1)][k] + g[i]);
}
}
}
}
i64 ans = -1;
for (int i = 0; i < (1 << 4); i++) {
ans = max(ans, dp[n][i]);
}
cout << ans << endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
小美的彩带
小美的彩带是由一条长度为 的彩带一直无限循环得到的，彩带的每一个位置都有一个颜色，用 表示。因此当 时， 。
小美每次会从左往后或从右往左剪一段长度为 的彩带，她想知道她每次剪下来的彩带有多少种颜色。
题解：这题的题面写的非常垃圾，主要注意两个问题： 前一次操作对后一次操作可能是有影响的，也就是操作之间不是独立的。 从左往后剪的起点是最左端，从右往左剪的起点是最右端。
注意到这两点后就比较简单了，求区间内有多少种不同的数，也是经典问题，不用多说，直接套个可持久化线段树。复杂度 。
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define endl '\n'
constexpr i64 Mod = 1000000007;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
constexpr int N = 4e5 + 5;
struct node{
int l, r, num;
}tree[N * 100];
int S = 0;
int root[N], a[N], nxt[N];
map<int, int> mp;
void update(int &x, int y, int l, int r, int dex) {
x = ++S;
tree[x] = tree[y];
tree[x].num++;
if (l == r) {
return;
}
int mid = (l + r) >> 1;
if (dex <= mid) {
update(tree[x].l, tree[y].l, l, mid, dex);
} else {
update(tree[x].r, tree[y].r, mid + 1, r, dex);
}
}
int query(int x, int y, int l, int r, int xx, int yy) {
if (xx <= l && r <= yy) {
return tree[y].num - tree[x].num;
}
int mid = (l + r) >> 1;
int res = 0;
if (xx <= mid) {
res += query(tree[x].l, tree[y].l, l, mid, xx, yy);
} if (yy > mid) {
res += query(tree[x].r, tree[y].r, mid + 1, r, xx, yy);
}
return res;
}
void solve() {
int n, q;
cin >> n >> q;
n *= 2;
for (int i = 1; i <= n / 2; i++) {
cin >> a[i];
a[n / 2 + i] = a[i];
}
mp.clear();
for (int i = n; i >= 1; i--) {
if (!mp.count(a[i])) {
nxt[i] = n + 1;
} else {
nxt[i] = mp[a[i]];
}
mp[a[i]] = i;
}
for (int i = 1; i <= n; i++) {
update(root[i], root[i - 1], 1, n + 1, nxt[i]);
}
int l = 1, r = n;
while (q--) {
string x;
int y;
cin >> x >> y;
auto ask = [&](int u, int v) -> int {
return query(root[u - 1], root[v], 1, n + 1, v + 1, n + 1);
};
if (x == "L") {
if (l + y - 1 > n) {
int ans = ask(1, n / 2);
cout << ans << endl;
} else {
int ans = ask(l, l + y - 1);
cout << ans << endl;
}
y %= n;
l = l + y;
if (l > n / 2) {
l -= n / 2;
}
if (l > n / 2) {
l -= n / 2;
}
assert(l >= 1 && l <= n / 2);
} else {
if (r - y + 1 < 1) {
int ans = ask(1, n / 2);
cout << ans << endl;
} else {
int ans = ask(r - y + 1, r);
cout << ans << endl;
}
y %= n;
r = r - y;
if (r <= n / 2) {
r += n / 2;
}
if (r <= n / 2) {
r += n / 2;
}
assert(r > n / 2 && r <= n);
}
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
类似资料：