作业帮25暑期实习笔试
一个字符串，一个思维，一个树状数组。
- 解析http的GET请求，输入一个http的
url以及一个key，中间用空格隔开。输入key对应的value
Input:
https://www.baidu.com?id=123&age=18 id
Output:
123
Code:
#include <bits/stdc++.h>
using namespace std;
int main() {
string s, t;
bool f = false;
cin >> s >> t;
unordered_map<string, string> mp;
for (int i = 0; i < s.size(); i++) {
if (s[i] == '?') {
f = true; continue;
}
if (!f) continue;
int j = i;
while (j < s.size() && s[j] != '=') j++;
string key = s.substr(i, j - i);
i = j;
while (i < s.size() && s[i] != '&') i++;
string val = s.substr(j + 1, i - j - 1);
mp[key] = val;
}
cout << mp[t];
return 0;
}
- 给一个数组，求数组中任意三个数乘积的最大值。
Input:
1,2,-5,-6,-2,4,3
Output:
120
Code:
#include <bits/stdc++.h>
using namespace std;
int main() {
string s;
cin >> s;
vector<int> nums;
nums.clear();
int i = 0, base = 0, t = 1;
while (i < s.size() && s[i] != ',') {
if (s[i] == '-') t = -1;
else base = base * 10 + s[i] - '0';
++i;
}
nums.push_back(base * t);
for (; i < s.size(); ++i) {
while (i < s.size() && s[i] != ',') {
if (s[i] == '-') t = -1;
else base = base * 10 + s[i] - '0';
++i;
}
nums.push_back(base * t);
base = 0;
t = 1;
}
sort(nums.begin(), nums.end());
vector<int> ban;
ban.clear();
if (nums.size() <= 6) ban = nums;
else {
for (int i = 0; i < 3; ++i) ban.push_back(nums[i]);
for (int i = nums.size() - 3; i < nums.size(); ++i) ban.push_back(nums[i]);
}
int ans = -0x3f3f3f3f;
for (int i = 0; i < ban.size(); ++i)
for (int j = i + 1; j < ban.size(); ++j)
for (int k = j + 1; k < ban.size(); ++k) {
int x = ban[i], y = ban[j], z = ban[k];
ans = max(ans, x * y * z);
}
cout << ans;
return 0;
}
- 给一个长度为
n的整型数组a[i] (1 <= i <= n)表示颜色，由该数组拓展为一个无限长的彩带a，其中a[i]=a[i-n] (i>n)，a[i]表示该彩带在位置i的颜色。
- 现在给
q个操作，每个操作由一个字符c以及一个整数x组成。其中字符c为'L'或'R'，如果c='L'那么表示从左向右剪该彩带，如果c='R'那么表示从右向左剪该彩带。x表示剪下的长度。 - 求剪下的彩带里不同颜色的个数。
- 输入第一行
n和q，第二行n个数表示a[i]，接下来q行，每行一个c与x。 n, q <= 2e5
Input:
6 3
1 1 4 5 1 4
L 2
L 3
R 12
Output:
1
3
3
Hint:
初始彩带为：1 1 4 5 1 4 1 1 4 5 1 4 1 1 4 5 1 4 ... 1 1 4 5 1 4
第一次从左往右剪长度为 2，剪下的彩带为：1 1，其中不同的颜色有1个。
这时彩带为：4 5 1 4 1 1 4 5 1 4 1 1 4 5 1 4 ... 1 1 4 5 1 4
第二次从左往右剪长度为 3，剪下的彩带为：4 5 1，其中不同的颜色3个。
这时彩带为：4 1 1 4 5 1 4 1 1 4 5 1 4 ... 1 1 4 5 1 4
第三次从右往左剪长度为 12，剪下的彩带为：1 1 4 5 1 4 1 1 4 5 1 4，其中不同的颜色有3个。
这时彩带为：4 1 1 4 5 1 4 1 1 4 5 1 4 ... 1 1 4 5 1 4
Code:
#include <bits/stdc++.h>
using namespace std;
const int N = 4e5 + 10;
int n, q, a[N], mx;
int tr[N], ans[N];
struct node {
int l, r, id;
bool f;
bool operator<(const node &t) const {
return r < t.r;
}
}op[N];
int lt(int x) {
return x & -x;
}
void add(int x, int v) {
for (int i = x; i <= n; i += lt(i)) tr[i] += v;
}
int query(int x) {
int res = 0;
for (int i = x; i; i -= lt(i)) res += tr[i];
return res;
}
int main() {
scanf("%d%d", &n, &q);
unordered_map<int, bool> st;
for (int i = 1; i <= n; ++i) {
scanf("%d", a + i);
if (!st[a[i]]) {
st[a[i]] = 1;
++mx;
}
}
for (int i = n + 1; i <= 2 * n; ++i) a[i] = a[i - n];
int L = 1, R = 2 * n;
for (int i = 1; i <= q; ++i) {
char c; int x, l, r;
getchar();
scanf("%c%d", &c, &x);
op[i].id = i;
if (x >= n) op[i].f = 1;
else op[i].f = 0;
x %= n;
if (c == 'L') {
l = L, r = L + x - 1;
L = r + 1; if (L > n) L -= n;
}
else {
l = R - x + 1, r = R;
R = l - 1; if (R <= n) R += n;
}
op[i].l = l, op[i].r = r;
}
sort(op + 1, op + 1 + q);
unordered_map<int, int> pre;
int pos = 0;
for (int i = 1; i <= q; ++i) {
int l = op[i].l, r = op[i].r, id = op[i].id;
if (op[i].f) ans[id] = mx;
else {
while (pos < r) {
++pos;
if (pre[a[pos]]) add(pre[a[pos]], -1);
add(pos, 1);
pre[a[pos]] = pos;
}
ans[id] = query(r) - query(l - 1);
}
}
for (int i = 1; i <= q; ++i) printf("%d\n", ans[i]);
return 0;
}
投递饿了么等公司10个岗位 >