作业帮25暑期实习笔试

一个字符串，一个思维，一个树状数组。

1. 解析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;
}

2. 给一个数组，求数组中任意三个数乘积的最大值。 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;
}

3. 给一个长度为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;
}