0929字节笔试ak

字节的复活赛都输了，感觉身边拿字节offer都没走笔试程序，寄！

1：给定一个数组，使用双端队列按照顺序存（每次可以放到头或者尾），放完后双端队列能否非降序排列。

模拟+贪心：题目要求非降序，每次放的判断跟队列头尾比较就行，每次都要满足比头小或者比尾大。

n=(1e5)，O(n)

#include "bits/stdc++.h"
using namespace std;
int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        int n;
        scanf("%d", &n);
        deque<int> dq;
        bool flag = true;
        while (n--)
        {
            int tmp;
            scanf("%d", &tmp);
            if (flag)
            {
                if (dq.empty())
                    dq.push_back(tmp);
                else if (dq.front() >= tmp)
                    dq.push_front(tmp);
                else if (dq.back() <= tmp)
                    dq.push_back(tmp);
                else
                    flag = false;
            }
        }
        if (flag)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
    return 0;
}

2：给定n，从1开始，每a天执行一件事，每b天执行一件事，每c天执行一件事。问有多少天干了至少2件事。

三个集合相交：（a∩b）∪（a∩c）∪（b∩c）-2(a∩b∩c)

n=(1e5)，O(n)

#include "bits/stdc++.h"
using namespace std;
int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        int n, a, b, c;
        scanf("%d %d %d %d", &n, &a, &b, &c);
        int ab = a * b / gcd(a, b);
        int ac = a * c / gcd(a, c);
        int bc = b * c / gcd(b, c);
        int abc = ab * c / gcd(ab, c);
        int sum = 0;
        sum += n / ab;
        sum += n / ac;
        sum += n / bc;
        sum -= 2 * (n / abc);
        printf("%d\n", sum);
    }
    return 0;
}

3：给一个数组a(从1开始，每个元素都是[1,n]),可以从i到(i+1)和(i-1)，开销是1。i到(i+a[i])，开销是abs(a[i]-a[i+a[i]))。从1开始，求到每个点的最小开销。

Dijkstra：抽象成图，跑一遍Dijkstra即可（太久没写最短路了，调了快50分钟）

n=(2e5)，m是图中边的数目，该题m=3n=O(n)。O(mlog(m))=O(nlog(n))

#include "bits/stdc++.h"
using namespace std;
int main()
{
    int n;
    scanf("%d", &n);
    vector<int> arr(n + 1, 0);
    vector<int> dis(n + 1, n);
    vector<set<pair<int, int>>> edges(n + 1);
    for (int i = 1; i <= n; i++)
        scanf("%d", &arr[i]);
    for (int i = 1; i <= n; i++)
    {
        int j = i - 1;
        if (j >= 1)
            edges[i].insert(make_pair(j, 1));
        j = i + 1;
        if (j <= n)
            edges[i].insert(make_pair(j, 1));
        j = i + arr[i];
        if (j <= n)
            edges[i].insert(make_pair(j, abs(arr[i] - arr[j])));
    }
    auto dijkstra = [&](int s)
    {
        vector<bool> vis(n + 1, false);
        dis[s] = 0;
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>
            pq;
        pq.push(make_pair(dis[s], s));
        while (!pq.empty())
        {
            auto top = pq.top();
            pq.pop();
            int d = top.first, u = top.second;
            if (vis[u])
                continue;
            vis[u] = true;
            for (auto iter : edges[u])
            {
                int v = iter.first, w = iter.second;
                if (dis[v] > d + w)
                {
                    dis[v] = d + w;
                    pq.push(make_pair(dis[v], v));
                }
            }
        }
    };
    dijkstra(1);
    for (int i = 1; i <= n; i++)
        printf("%d ", dis[i]);
    return 0;
}

4：给一个数组a，只有一个最大值的子数组称为完美子数组。求完美子数组的个数

复杂二分：从大到小遍历，每次遍历当前值的所有位置，用二分找到该位置能组成的完美子数组个数（左边prev(lower_bound）,右边upper_bound)

n=(1e5)。O(nlog(n))

#include "bits/stdc++.h"
using namespace std;
using ll = long long;
int main()
{
    int n;
    scanf("%d", &n);
    vector<int> arr(n, 0);
    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);
    ll ans = 0;
    map<int, set<int>> ump;
    set<int> st;
    for (int i = 0; i < n; i++)
        ump[arr[i]].insert(i);
    for (auto iter = ump.rbegin(); iter != ump.rend(); iter++)
    {
        for (auto index : iter->second)
            st.insert(index);
        for (auto index : iter->second)
        {
            auto l_iter = st.lower_bound(index);
            auto r_iter = st.upper_bound(index);
            int l = index, r = index;
            if (l_iter == st.begin())
                l = index + 1;
            else
                l = index - *(--l_iter);
            if (r_iter == st.end())
                r = n - index;
            else
                r = *r_iter - index;
            ans += ll(l) * r;
        }
    }
    cout << ans << endl;
    return 0;
}

带哨兵节点的版本

#include "bits/stdc++.h"
using namespace std;
using ll = long long;
int main()
{
    int n;
    scanf("%d", &n);
    vector<int> arr(n, 0);
    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);
    ll ans = 0;
    map<int, set<int>> ump;
    set<int> st;
    // 哨兵节点
    st.insert(-1);
    st.insert(n);
    for (int i = 0; i < n; i++)
        ump[arr[i]].insert(i);
    for (auto iter = ump.rbegin(); iter != ump.rend(); iter++)
    {
        for (auto index : iter->second)
            st.insert(index);
        for (auto index : iter->second)
            ans += ll(index - *(--st.lower_bound(index))) * (*st.upper_bound(index) - index);
    }
    cout << ans << endl;
    return 0;
}