This week's competition is jointly signed by AutoX. As the first week's competition in the new year, the topic is quite interesting. It's a good choice for brainstorming.

Knowledge points involved: greed, topological sorting, dynamic programming, graph data mining

5967. Check that all A precedes B

Given A string containing only A and B, judge whether all characters A appear before character B

Problem solution

It is easy to conclude that the string that matches the meaning of the question is either a AB.. Type B, or b Type B, just mark with a flag

// cpp
class Solution {
public:
    bool checkString(string s) {
        bool flag = false;
        for (int i = 0; i < s.length(); ++i) {
            if (s[i] == 'b') flag = true;
            else if (flag && s[i] == 'a') return false;
        }
        return true;
    }
};

5968. Number of laser beams in banks

Given n 01 strings with length m, for two adjacent strings, any two 1s can form a laser beam, and the number of all laser beams can be calculated

Problem solution

First process the number of 1 contained in each string, and eliminate the string without 1

Then the two adjacent values can be multiplied, and the sum is the answer

// cpp
class Solution {
public:
    int numberOfBeams(vector<string>& bank) {
        vector<int> vec;
        for (auto& i: bank) {
            int cnt = 0;
            for (auto& j: i) if (j == '1') cnt++;
            if (cnt) vec.push_back(cnt);
        }
        int ans = 0;
        for (int i = 0; i < static_cast<int>(vec.size()) - 1; ++i) {
            ans += vec[i] * vec[i + 1];
        }
        return ans;
    }
};

5969. Destruction of asteroids

There is a planet with mass m and n planets with mass a_{i} You can arrange the asteroids in any order and let the planets collide with them. The collision condition is m\geq a_{i} At the same time, after the collision, due to the attraction effect, the mass of the planet needs to be added with a_{i} Can you judge whether planets can crash all asteroids?

Data specification 1\leq n,\ m,\ a_{i}\leq 10^5

Problem solution

In consideration of greed, we select the largest planet not exceeding m among the remaining asteroids and take it out to collide with the planet, so as to ensure that the mass of the planet is locally the largest and will not fall in the wind in the subsequent collision

An ordered set sum can be used to store data, find the colliding planets and delete them. Time complexity \ mathcal{O}(n\log n)

// cpp
class Solution {
public:
    bool asteroidsDestroyed(int m, vector<int>& a) {
        typedef long long LL;
        multiset<LL> st(a.begin(), a.end());
        LL sum = m;
        int n = static_cast<int>(a.size());
        for (int i = 0; i < n; ++i) {
            auto x = st.upper_bound(sum);
            if (x == st.begin()) return false;
            x--;
            sum += (*x);
            st.erase(x);
        }
        return true;
    }
};

It can also be absorbed from the smallest, and the code is simpler

// cpp
class Solution {
public:
    bool asteroidsDestroyed(int m, vector<int>& a) {
        sort(a.begin(), a.end());
        typedef long long LL;
        LL sum = m;
        for (int i = 0; i < static_cast<int>(a.size()); ++i) {
            if (sum < a[i]) return false;
            sum += a[i];
        }
        return true;
    }
};

5970. Maximum number of employees attending meetings

There are n employees, and each employee has a favorite object (not himself)

There is an infinite round table. If an employee sits next to his favorite object, he will attend the meeting

How many employees attend the meeting at most?

Data specification 1\leq n\leq 10^5

Problem solution

Considering mapping, we find the following properties

• Each point has one and only one exit edge
• No self ring

In fact, this is the concept of base ring tree. Each point has and has only one edge, which is called base ring inward tree; If each point has only one edge, it is called a base ring extrovert tree

However, no matter what graph theory model, the algorithms used are basically search, topological sorting, shortest path and dynamic programming

By analysis, there are only two cases that can be served

• End to end ring
• There is a binary ring locally, and a chain is pulled down on both sides of the ring

We can use topological sorting to do a graph mining, and finally only rings will remain on the subgraph

1 -- 2 -- 3     5 -- 6
 \       /
  \     /       7 --- 8
   \   /         \   /
     4             9

In the process of topological sorting, we can make dynamic planning according to the topological order and calculate the maximum number of dependencies of each employee. In this way, when counting the answers in the second case, we can directly add the length of the longest chain

Time and space complexity is \ mathcal{O}(n)

// cpp
class Solution {
public:
    int maximumInvitations(vector<int>& f) {
        int n = static_cast<int>(f.size());
        vector<int> dp(n);
        vector<int> ind(n);
        for (int i = 0; i < n; ++i) {
            ind[f[i]]++;
        }
        queue<int> q;
        for (int i = 0; i < n; ++i) {
            dp[i] = 1;
            if (!ind[i]) q.push(i);
        }
        while (!q.empty()) {
            int temp = q.front(); q.pop();
            int to = f[temp];
            dp[to] = max(dp[to], dp[temp] + 1);
            ind[to]--;
            if (!ind[to]) q.push(to);
        }
        int ans1 = 0, ans2 = 0;
        vector<bool> vis(n);
        for (int i = 0; i < n; ++i) {
            if (!ind[i] || vis[i]) continue;
            if (f[f[i]] == i) {
                vis[f[i]] = true, vis[i] = true;
                ans1 += dp[f[i]] + dp[i];
            }
            else {
                int cnt = 1;
                for (int j = f[i]; j != i; j = f[j]) {
                    vis[j] = true;
                    cnt++;
                }
                ans2 = max(ans2, cnt);
            }
        }
        return max(ans1, ans2);
    }
};