今日头条后端编程题

#include <bits/stdc++.h>
using namespace std;

int n, m, c;

vector<int> colors[20008];
int win[1008];

int solution() {
    unordered_set<int> cc;
    memset(win, 0, sizeof win);
    for (int i = 0; i < m; ++i) {
        for (int c : colors[i]) {
            win[c]++;
            if (win[c] > 1)
                cc.emplace(c);
        }
    }
    for (int i = 1; i < n; ++i) {
        for (int c : colors[i-1])
            win[c]--;
        for (int c : colors[i+m-1]) {
            win[c]++;
            if (win[c] > 1)
                cc.emplace(c);
        }
    }
    return cc.size();
}

int main() {
    // freopen("in.txt", "r", stdin);
    int num, c;
    while (~scanf("%d%d%d", &n, &m, &c)) {
        for (int i = 0; i < n; ++i) {
            colors[i].clear();
            colors[i+n].clear();
            scanf("%d", &num);
            while (num--) {
                scanf("%d", &c);
                colors[i].emplace_back(c);
                colors[i+n].emplace_back(c);
            }
        }
        printf("%d\n", solution());
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

constexpr int MAXN = 300008;

struct Node {
    unordered_map<int, int> cnts;
    int l, r;
} nodes[MAXN];

int n, q;
int ks[MAXN];

void build(int b, int e, int root) {
    nodes[root].l = b, nodes[root].r = e;
    if (e - b <= 10) { //防止爆内存。。。
        for (int i = b; i <= e; ++i) {
            nodes[root].cnts[ks[i]]++;
        }
        return ;
    }
    int lc = root << 1;
    int rc = lc | 1;
    int mid = b + (e - b >> 1);
    build(b, mid, lc);
    build(mid+1, e, rc);
    if (nodes[lc].cnts.empty()) {
        for (int i = b; i <= mid; ++i) {
            nodes[root].cnts[ks[i]]++;
        }
    } else {
        for (auto p : nodes[lc].cnts) {
            nodes[root].cnts[p.first] += p.second;
        }
    }
    if (nodes[rc].cnts.empty()) {
        for (int i = mid+1; i <= e; ++i) {
            nodes[root].cnts[ks[i]]++;
        }
    } else {
        for (auto p : nodes[rc].cnts) {
            nodes[root].cnts[p.first] += p.second;
        }
    }
}

int query(int l, int r, int k, int root) {
    if (r - l <= 10) {
        int cnt = 0;
        for (int i = l; i <= r; ++i) {
            if (ks[i] == k)
                cnt++;
        }
        return cnt;
    }
    if (l == nodes[root].l && r == nodes[root].r)
        return nodes[root].cnts[k];
    int m = nodes[root].l + (nodes[root].r - nodes[root].l >> 1);
    int lc = root << 1;
    int rc = lc | 1;
    if (r <= m) return query(l, r, k, lc);
    else if (l > m) return query(l, r, k, rc);
    else return query(l, m, k, lc) + query(m+1, r, k, rc);
}

int main() {
    // freopen("in.txt", "r", stdin);
    int l, r, k;
    while (~scanf("%d", &n)) {
        for (int i = 1; i <= n; ++i)
            scanf("%d", ks + i);
        build(1, n, 1);
        scanf("%d", &q);
        while (q--) {
            scanf("%d%d%d", &l, &r, &k);
            printf("%d\n", query(l, r, k, 1));
        }
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int m;
string s;
vector<int> axis[32];

void preprocess() {
    for (int i = 0; i < s.size(); ++i) {
        axis[s[i]-'a'].emplace_back(i);
    }
}

int solution(char ch) {
    int idx = ch - 'a';
    int n = axis[idx].size();
    int maxi = 1;
    for (int i = 0; i < n; ++i) {
        int con = 1;
        int cur = 0;
        int lc = i, rc = n - 1 - i;
        int la = axis[idx][i] - 1, ra = axis[idx][i] + 1;
        int left = i - 1, right = i + 1;
        while (true) {
            int a = m + 1, b = m + 1;
            if (left >= 0 && lc > 0) {
                a = la - axis[idx][left];
            }
            if (right < n && rc > 0) {
                b = axis[idx][right] - ra;
            }
            if (min(a, b) + cur > m) break;
            if (a < b) {
                la--;
                lc--;
                left--;
            } else {
                ra++;
                rc--;
                right++;
            }
            con++;
            cur += min(a, b);
        }
        maxi = max(maxi, con);
    }
    return maxi;
}

int main() {
    // freopen("in.txt", "r", stdin);
    while (cin >> s >> m) {
        vector<pair<int, char>> v(32, make_pair(0, ' '));
        for (int i = 0; i < 26; ++i)
            axis[i].clear();
        for (char ch : s) {
            v[ch-'a'].first++;
            v[ch-'a'].second = ch;
        }
        sort(v.begin(), v.end());
        preprocess();
        int s = 1;
        for (auto it = v.rbegin(); it != v.rend(); ++it) {
            if (s >= it->first)
                break;
            s = solution(it->second);
        }
        cout << s << '\n';
    }
    return 0;
}