geeksforgeeks选题

2023-04-30 | 阅读：次

===

Index

区间内匹配括号对数量
好数组需要的最少删除元素数量
s到t波浪路径最短路
使字符串相等的最少预处理操作次数
从s到t经过中间节点的最短路径
连通图中的k个节点
重排字符串
乘积数组第k大数
q次操作后可能的字符串数量
循环字符串插入

区间内匹配括号对数量

geeks link

输入括号字符串s(长度n)，和m个区间询问，每个询问给定区间[l,r]，返回长度为m的数组ans，ans[i]表示第i个询问的区间内平衡括号对数。

1 <= n, m <= 1e5
0 <= l <= r < n

分析

线段树维护区间内平衡括号对数v，剩余未匹配的左括号树l和未匹配的右括号数r，时间复杂度 O(n + mlog(n))

struct S {
    int v, l, r, siz;
};
S op(S x, S y) {
    if (x.siz == 0) return y;
    if (y.siz == 0) return x;
    int t = min(x.l, y.r);
    return S{x.v + y.v + t, x.l + y.l - t, x.r + y.r - t, x.siz + y.siz};
}
S e() {
    return S{};
}
vector<int> getQuery(string &s, vector<vector<int>> &qs) {
    int n = s.size(), m = qs.size();
    vector<S> a(n);
    for (int i = 0; i < n; ++i) {
        int l = s[i] == '(' ? 1 : 0, r = l ^ 1;
        a[i] = {0, l, r, 1};
    }
    SegTree<S, op, e> seg(a);
    vector<int> ans(m);
    for (int i = 0; i < m; ++i) {
        ans[i] = seg.get(qs[i][0], qs[i][1] + 1).v;
    }
    return ans;
}

好数组需要的最少删除元素数量

geeks link

如果对于数组中任意a[i], 存在 j!=i，使得 a[i]+a[j] 等于某个2的整数次幂，则称数组是好的，给定数组a，求使得数组变好，最少需要删除多少个元素。

1 <= n <= 1e5
1 <= a[i] < 2^31

int minimumRemoval(vector<int> &a) {
    int n = a.size(), ans = 0;
    unordered_map<int, int> mp;
    for (int &x : a) 
        mp[x]++;

    for (int i = 0; i < n; ++i) {
        bool need = 1;
        for (int j = 0; j < 31; ++j) {
            int x = (1 << j) - a[i];
            if (mp.count(x) && (mp[x] > 1 || mp[x] == 1 && x != a[i])) {
                need = 0;
                break;
            }
        }
        ans += need;
    }
    return ans;
}

s到t波浪路径最短路

geeks link

n个点m条边的连通图，求从s到t的最短路，假设从s到t经过的边的权重为 e1,e2,..,ek，这些权重需要满足 e1 > e2 < e3 > e4 <... 或者 e1 < e2 > e3 < e4 > ...。如果没有这样的路径 返回-1

1 <= n <= 4e4
1 <= m <= 1e5
1 <= w[i] <= 1e5

template<typename T>
struct Dijkstra {
    using pi = pair<T,int>;
    vector<vector<pi> > inc, dec;
    int n;

    Dijkstra(int N) : n(N), inc(N), dec(N) {}

    void add_edge(int x, int y, T w) {
        inc[x].emplace_back(w, y);
        inc[y].emplace_back(w, x);
        dec[x].emplace_back(-w, y);
        dec[y].emplace_back(-w, x);
    }

    T calc(int s, int t) {
        priority_queue<pair<pi, pi>> q; 
        for (int i = 0; i < n; ++i) {
            sort(inc[i].begin(), inc[i].end());
            sort(dec[i].begin(), dec[i].end());
        }
        vector<T> d(n, T(-1));
        q.push({ {0,0}, {0, s} });
        vector<int> p1(n), p2(n);
        while (!q.empty()) {
            auto [c, u] = q.top().first;
            auto [w, v] = q.top().second;
            q.pop();
            if (d[v] == T(-1) || d[v] > -c) d[v] = -c;
            if (d[t] != T(-1)) break;
            if (u) {
                for (int i = p1[v]; i < inc[v].size(); ++i) {
                    auto t = inc[v][i];
                    if (w > t.first) 
                        q.push({ {c-t.first, 0}, t});
                    else {
                        p1[v] = i;
                        break;
                    }
                }
            } else {
                for (int i = p2[v]; i < dec[v].size(); i++) {
                    auto t = dec[v][i];
                    if (w < -t.first) 
                        q.push({ {c+t.first, 1}, {-t.first, t.second} });
                    else {
                        p2[v] = i;
                        break;
                    }
                }
            }
        }
        return d[t];
    }

};

long long getMinPath(int n, int s, int t, vector<vector<int>> &es) {
    Dijkstra<long long> d(n);
    for (auto &e : es) {
        d.add_edge(e[0], e[1], (long long)e[2]);
    }
    return d.calc(s, t);
}

使字符串相等的最少预处理操作次数

geeks link

给定两个字符串s,t, 每次预处理可以选择s中任意字符，将其替换为任意字符，求所需的最少预处理次数，使得预处理后，可以通过以下操作使s和t相等。

交换 s[i],t[i]
交换 s[i] s[n - 1 - i]
交换 t[i], t[n - 1 - i]
1 <= n <= 1e5

int minPreOps(string &s, string &t) {
    int n = s.size(), ans = (n & 1 and s[n / 2] != t[n / 2]);
    for (int i = 0, j = n - 1; i < j; i++, j--) {
        map<char, int> mp;
        mp[s[i]]++; mp[s[j]]++;
        mp[t[i]]++; mp[t[j]]++;
        int m = mp.size();
        if (m == 4) ans += 2;
        else if (m == 3) {
            ans += 1 + (s[i] == s[j]);
        } else if (m == 2) {
            ans += mp[s[i]] != 2;
        }
    }
    return ans;
}

从s到t经过中间节点的最短路径

geeks link

给定无向带权图,求从s到t，必须经过节点u的最短路径。n, m <= 1e5

template<typename T>
struct Dijkstra {
    using E = pair<T, int>;
    int n;
    vector<vector<E>> g;    // cost, to
    Dijkstra(int N) : n(N), g(N) {}

    void add_edge(int u, int v, T cost) {
        g[u].emplace_back(cost, v);
    }

    void add_bidir_edge(int u, int v, T cost) {
        add_edge(u, v, cost);
        add_edge(v, u, cost);
    }

    vector<T> dijkstra(int s) {  // unreachable : -1
        vector<T> d(n, T(-1)); 
        priority_queue<E, vector<E>, greater<E>> q;
        d[s] = 0;
        q.emplace(0, s);
        while (!q.empty()) {
            auto [cost, u] = q.top();
            q.pop();
            if (d[u] < cost) continue;
            for (auto &[c, v] : g[u]) {
                if (d[v] == T(-1) || d[u] + c < d[v]) {
                    d[v] = d[u] + c;
                    q.emplace(d[v], v);
                }
            }
        } 
        return d;
    }
};

long long minPathNode(int n, int s, int t, int u, vector<vector<int>> &es) {
    Dijkstra<long long> d(n);
    for (auto &e : es) {
        d.add_bidir_edge(e[0], e[1], e[2]);
    }
    auto ds = d.dijkstra(s);
    auto dt = d.dijkstra(t);
    auto du = d.dijkstra(u);
    long long ans = -1;
    for (int i = 0; i < n; ++i) {
        if (ds[i] == - 1 || dt[i] == -1 || du[i] == -1) continue;
        if (ans == -1 || ans > ds[i] + dt[i] + du[i]) {
            ans = ds[i] + dt[i] + du[i];
        }
    }
    return ans;
}

连通图中的k个节点

geeks link

n个节点的连通图，返回一个不超过n/2的节点集合s，s中每个节点满足，至少和一个不在s中的节点相连。

n, m <= 2e5

分析

奇偶分层，如果奇数层节点少，返回奇数层，否则返回偶数层。

vector<int> connectNode(int n, vector<vector<int>> &es) {
    vector<vector<int>> g(n);
    for (auto & e : es) {
        g[e[0]].push_back(e[1]);
        g[e[1]].push_back(e[0]);
    }
    vector<int> f[2];

    queue<int> q;
    vector<int> d(n, -1);
    d[0] = 0;
    q.push(0);
    while (q.size()) {
        int u = q.front();
        q.pop();
        f[d[u]].push_back(u);
        for (int v : g[u]) if (d[v] == -1) {
            d[v] = d[u] ^ 1;
            q.push(v);
        }
    }
    return f[0].size() < f[1].size() ? f[0] : f[1];
}

重排字符串

geeks link

给定长度为n的字符串s，重排字符串，使得对于任意的质数p<=N,及任意 1<=i<=n/p 满足 s[p]=s[p*i], 如果无解，返回空串。

string rearrange(string &s) {
    int n = s.size(), cnt = 0, mx = 0;
    vector<int> p(n + 1, 1);
    for (int i = 2, j = n / 2; i <= j; ++i) {
        if (p[i]) 
            for (int j = 1; i * j <= n; ++j) {
                if (p[i * j]) cnt++;
                p[i * j] = 0;
            }
    }
    vector<int> a(26);
    for (int i = 0; i < n; ++i) {
        a[s[i] - 'a']++;
    }
    char c;
    for (int i = 0; i < 26; ++i) {
        if (a[i] > mx) {
            mx = a[i], c = 'a' + i;
        }
    }
    if (mx < cnt) return "";
    string t = "";
    for (int i = 0; i < n; ++i) {
        if (s[i] != c) t += s[i];
    }
    for (int i = 0; i < n; ++i) {
        if (p[i + 1]) {
            if (t.size() > 0) {
                s[i] = t.back(); t.pop_back();
            } else {
                s[i] = c, mx--;
            }
        } else {
            s[i] = c, mx--;
        }
    }
    return s;
}

乘积数组第k大数

geeks link

给定长为n的数组a和整数k，返回乘积数组的第k大数。乘积数组是由所有 a[i]*a[j] 0 <= i < j < n构成的长度为数组n*(n-1)/2的数组。

1 <= n <= 1e5
-1e9 <= n <= 1e9
1 <= k <= n*(n-1)/2

long long kthMulArr(vector<int> &a, long long k) {
    vector<int> pos, neg;
    for (int &x : a) {
        if (x >= 0) pos.push_back(x);
        else neg.push_back(x);
    }
    int n = pos.size(), m = neg.size();
    sort(pos.begin(), pos.end());
    sort(neg.begin(), neg.end());

    auto chk = [&](long long x) {
        long long cnt = 0;
        for (int i = n - 1, p = 0; i >= 0; --i) {
            while (p < n && pos[i] * 1ll * pos[p] <= x) p++;
            cnt += min(p, i);
        }
        for (int i= 0, p = m - 1; i < m; ++i) {
            while (p >= 0 && neg[i] * 1ll * neg[p] <= x) p--;
            cnt += min(m - 1 - p, m - 1 - i);
        }
        for (int i = m - 1, p = n - 1; i >= 0; --i) {
            while (p >= 0 && neg[i] * 1ll * pos[p] <= x) p--;
            cnt += n - 1 - p;
        }
        return cnt >= k;
    };

    long long l = -1e18, r = 1e18, ans = 0;
    while (l <= r) {
        long long md = (l + r) / 2;
        if (chk(md)) {
            ans = md, r = md - 1;
        } else l = md + 1;
    }
    return ans;
}

q次操作后可能的字符串数量

geeks link

给一个n和q次操作，每次操作给定l,r，含义是字符串的s[l..r]为回文子串，求满足所有q次操作的字符串可能数目，字符串小写字符组成，模1e9+7.

1 <= n <= 2000
1 <= q <= 2e5
0 <= l <= r < n

分析

并查集维护每个中心的最长回文半径，merge 对应位置，如果最终由k个集合，则数量为26的k次方。时间复杂度 O(n*n + q)

int strCnt(int n, vector<vector<int>> &querys) {
    DSU d(n);
    vector<int> a(2 * n), vis(n);
    for (auto &q : querys) {
        int l = q[0], r = q[1];
        a[l + r] = max(a[l + r], r - l); 
    }
    for (int i = 0; i < 2 * n; ++i) {
        if (a[i] == 0) continue;
        int l, r;
        if (a[i]& 1) l = i / 2 - a[i] / 2, r = i / 2 + a[i] / 2 + 1;
        else l = i / 2 - a[i] / 2, r = i / 2 + a[i] / 2;
        while (l < r) {
            d.merge(l, r);
            l++, r--;
        }

    }
    for (int i = 0; i < n; ++i) {
        vis[d.get(i)] = 1;
    }
    int cnt = 0;
    for (int i = 0; i < n; ++i) {
        if (vis[i]) cnt++;
    }

    return mint(26).pow(cnt).val();
}

循环字符串插入

geeks link

给定字符串s和整数k，返回一个字符串t，t中每个字符由s中每个字符按顺序插入获得，将t认为是一个循环字符串，每一个字符插入在上一个字符向右旋转k个位置。

1 <= k <= n <= 2000

string rotatekins(string &s, int k) {
    int n = s.size(), lst = -1, p;
    string t;
    for (int i = 0; i < n; ++i) {
        if (i <= 1) {
            t += s[i];
            lst = i + 1;
        } else {
            p = (lst + k) % (i);
            if (p == 0) p = i;
            t.insert(t.begin() + p, s[i]);
            lst =  p + 1;
        }
    }
    return t;
}