美团笔试 - 技术方向 0322 题解
T1
求完全由轴对称字母
AHIMOTUVWXY构成的回文串数量。
- 数据范围
，直接
暴力枚举区间判断。
- 按非轴对称字母分段，每一段单独
manacher统计回文串数量，。
#include <bits/stdc++.h>
using namespace std;
const int N = 105;
char s[N];
set<char> st = {'A', 'H', 'I', 'M', 'O', 'T', 'U', 'V', 'W', 'X', 'Y'};
int main() {
scanf("%s", s + 1);
int n = strlen(s + 1), cnt = 0;
for (int l = 2; l <= n; ++l) {
for (int i = 1; i + l - 1 <= n; ++i) {
int f = 1;
for (int j = 1; j <= l; ++j)
if (!st.count(s[i + j - 1])) {
f = 0;
break;
}
if (!f) continue;
for (int j = 1; j * 2 <= l; ++j)
if (s[i + j - 1] != s[i + l - j]) {
f = 0;
break;
}
cnt += f;
}
}
printf("%d\n", cnt);
return 0;
}
T2
给定一个排列
，求对子区间排序后，子区间中位数位置不变的子区间数量。
枚举中位数的位置，从中间同时向左右扩展，统计比 大/小的数的数量，如果相等，说明当前子区间满足题意，
。由于
，所以可以通过。
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n, ans = 0;
scanf("%d", &n);
vector<int> a(n);
for (auto &x : a) scanf("%d", &x);
for (int i = 0; i < n; ++i) {
int l = 0, r = -2;
for (int j = 0; i - j >= 0 && i + j < n; ++j) {
(a[i - j] < a[i] ? l : r)++;
(a[i + j] < a[i] ? l : r)++;
ans += l == r;
}
}
printf("%d\n", ans);
}
int main() {
int t;
scanf("%d", &t);
while (t--) solve();
return 0;
}
T3
在
到
的数轴上，有一个初始位置为
的机器人。给定一个指令序列
，指令集由 L（向左移动，若在
。
- 注意到，最终的答案一定是形如
，即一个大区间套小区间，小区间部分答案为
交替，大区间的剩余部分为连续的
- 维护两个区间的端点
，其中
。
- 先不考虑任何冲突，对于每个指令：
L：全部左移，即全；
R：全部右移，即全；
?：- 如果
，即没有连续
- 如果
，说明存在连续
，此时
会左移，但是
会右移；
- 对于
和
的讨论同理。
- 如果
- 考虑在什么情况下会产生连续
，即当前指令为
?且，可以理解为最左边的
；
- 考虑如何处理冲突，定义修正函数
：
- 以上操作的执行均满足
的条件，不会产生区间冲突；
- 区间端点可能超出
：直接对所有区间端点进行修正即可；
- 可能会出现
的情况：直接令
即可。
- 以上操作的执行均满足
- 时间复杂度
- 特别注意，题目没说
，虽然样例都是这样的（笔试的时候因为这个卡
卡了一个小时）。
- 题外话：从笔试题的角度来说，这题确实考得非常难了，而且如果不继续想一下性质，直接用大量
if-else条件处理所有情况，写起来考虑各种边界条件会非常麻烦。
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int n, k; string s;
cin >> n >> k >> s;
int sL = k, sR = k, L = k, R = k;
for (auto c : s) {
switch (c) {
case 'L':
--sL, --L, --R, --sR;
break;
case 'R':
++sL, ++L, ++R, ++sR;
break;
default:
sL < L ? ++L : --L;
sR > R ? --R : ++R;
--sL, ++sR;
break;
}
auto f = [&](int &x) {
x = min(n, max(1, x));
};
if (L < 1 && 1 < R) L = 2;
if (R > n && n > L) R = n - 1;
f(sL), f(sR), f(L), f(R);
if (L > R) L = R;
}
string ans(n, '0');
for (int i = sL; i < L; ++i) ++ans[i - 1];
for (int i = L; i <= R; i += 2) ++ans[i - 1];
for (int i = R + 1; i <= sR; ++i) ++ans[i - 1];
cout << ans << '\n';
return 0;
}
当然，如果你真的想所有情况 if-else 判断一下，这种代码我也有。
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int n, k; string s;
cin >> n >> k >> s;
int L = k, R = k, sL = k, sR = k;
for (auto c : s) {
if (c == 'L') {
if (sL > 1)
--sL, --L, --R, --sR;
else if (sL < L)
--L, --R, --sR;
else if (L + 1 < R)
--R, --sR, ++L;
else if (sR > 1)
--sR;
} else if (c == 'R') {
if (sR < n)
++sL, ++L, ++R, ++sR;
else if (R < sR)
++L, ++R, ++sL;
else if (L + 1 < R)
++L, ++sL, --R;
else if (sL < n)
++sL;
} else {
if (sL == L && L > 1)
--L, --sL;
else if (sL < L)
sL = max(sL - 1, 1), ++L;
else if (L < n)
++L;
if (sR == R && R < n)
++R, ++sR;
else if (R < sR)
sR = min(sR + 1, n), --R;
else if (R > 1)
--R;
L = min(n, max(1, L));
R = min(n, max(1, R));
if (L > R)
L = R;
}
// assert(0 <= sL);
// assert(sL <= L);
// assert(L <= R);
// assert(R <= sR);
// assert(sR < n);
// printf("%d %d %d %d\n", sL, L, R, sR);
}
string ans(n, '0');
for (int i = sL; i < L; ++i) ans[i - 1] = '1';
for (int i = L; i <= R; i += 2) ans[i - 1] = '1';
for (int i = R + 1; i <= sR; ++i) ans[i - 1] = '1';
cout << ans << '\n';
return 0;
}
再附赠一个对拍程序。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 5;
string bf(int n, int k, string s) {
bitset<N> bs;
bs[k] = 1;
for (auto c : s) {
// string ans(n, '0');
// for (int i = 0; i < n; ++i)
// ans[i - 1] = bs[i] + '0';
// cout << ans << endl;
int L = bs[1], R = bs[n];
switch (c) {
case 'L':
bs = bs >> 1;
if (L)
bs[1] = 1;
break;
case 'R':
bs = bs << 1;
if (R)
bs[n] = 1;
break;
default:
bs = (bs << 1) | (bs >> 1);
if (L)
bs[1] = 1;
if (R)
bs[n] = 1;
break;
}
bs[0] = bs[n + 1] = 0;
}
string ans(n, '0');
for (int i = 1; i <= n; ++i)
ans[i - 1] += bs[i];
return ans;
}
string solve1(int n, int k, string s) {
int L = k, R = k, sL = k, sR = k;
for (auto c : s) {
if (c == 'L') {
if (sL > 1)
--sL, --L, --R, --sR;
else if (sL < L)
--L, --R, --sR;
else if (L + 1 < R)
--R, --sR, ++L;
else if (sR > 1)
--sR;
} else if (c == 'R') {
if (sR < n)
++sL, ++L, ++R, ++sR;
else if (R < sR)
++L, ++R, ++sL;
else if (L + 1 < R)
++L, ++sL, --R;
else if (sL < n)
++sL;
} else {
if (sL == L && L > 1)
--L, --sL;
else if (sL < L)
sL = max(sL - 1, 1), ++L;
else if (L < n)
++L;
if (sR == R && R < n)
++R, ++sR;
else if (R < sR)
sR = min(sR + 1, n), --R;
else if (R > 1)
--R;
L = min(n, max(1, L));
R = min(n, max(1, R));
if (L > R)
L = R;
}
// assert(0 <= sL);
// assert(sL <= L);
// assert(L <= R);
// assert(R <= sR);
// assert(sR < n);
// printf("%d %d %d %d\n", sL, L, R, sR);
}
string ans(n, '0');
for (int i = sL; i < L; ++i) ans[i - 1] = '1';
for (int i = L; i <= R; i += 2) ans[i - 1] = '1';
for (int i = R + 1; i <= sR; ++i) ans[i - 1] = '1';
return ans;
}
string solve2(int n, int k, string s) {
// scanf("%d%d%s", &n, &k, s);
int sL = k, sR = k, L = k, R = k;
for (auto c : s) {
switch (c) {
case 'L':
--sL, --L, --R, --sR;
break;
case 'R':
++sL, ++L, ++R, ++sR;
break;
default:
sL < L ? ++L : --L;
sR > R ? --R : ++R;
--sL, ++sR;
break;
}
auto f = [&](int &x) { x = min(n, max(1, x)); };
if (L < 1 && 1 < R) L = 2;
if (R > n && n > L) R = n - 1;
f(sL), f(sR), f(L), f(R);
if (L > R) L = R;
}
string ans(n, '0');
for (int i = sL; i < L; ++i) ++ans[i - 1];
for (int i = L; i <= R; i += 2) ++ans[i - 1];
for (int i = R + 1; i <= sR; ++i) ++ans[i - 1];
return ans;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
// int n, k;
// string s;
// cin >> n >> k >> s;
// cout << solve2(n, k, s) << endl;
// return 0;
// For random number generation
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// cout << t << endl;
auto check = [&](int n, int k, string s) {
static int tc = 0;
// For verification: compare bf and solve
string bf_ans = bf(n, k, s);
string ans1 = solve1(n, k, s);
string ans2 = solve2(n, k, s);
cout << "Test case " << ++tc << ": ";
if (bf_ans != ans1 || bf_ans != ans2) {
cout << "Mismatch found!" << endl;
cout << n << " " << k << endl;
cout << s << endl;
cout << "bf: " << bf_ans << endl;
cout << "solve1: " << ans1 << endl;
cout << "solve2: " << ans1 << endl;
exit(0);
} else {
cout << "OK" << endl;
}
};
// Number of test cases
// Generate all possible sequences for small inputs
function<void(int, int, int, string &, int)> generateAllSequences =
[&](int n, int k, int len, string &s, int pos) {
if (pos == len) {
check(n, k, s);
return;
}
// Try all three possible instructions
s[pos] = 'L';
generateAllSequences(n, k, len, s, pos + 1);
s[pos] = 'R';
generateAllSequences(n, k, len, s, pos + 1);
s[pos] = '?';
generateAllSequences(n, k, len, s, pos + 1);
};
// For small values, test all possible combinations
for (int n = 1; n <= 5; ++n) {
for (int k = 1; k <= n; ++k) {
for (int len = 1; len <= 5; ++len) {
string s(len, ' ');
generateAllSequences(n, k, len, s, 0);
}
}
}
int tot = 3000; // You can adjust this
for (int tc = 0; tc < tot; ++tc) {
// Generate random n, k and length of string
int n = rng() % N + 1; // Random n between 1 and 10^6
int k = rng() % n + 1; // Random k between 1 and n
int len = rng() % N + 1; // Random length between 1 and 10^6
// Generate random instruction sequence
string s;
for (int i = 0; i < len; ++i) {
int cmd = rng() % 3;
if (cmd == 0)
s += 'L';
else if (cmd == 1)
s += 'R';
else
s += '?';
}
check(n, k, s);
}
return 0;
}
投递美团等公司10个岗位