第 364 场力扣周赛

最大二进制奇数

模拟。

class Solution {
public:
    string maximumOddBinaryNumber(string s) {
        int n = s.size(), cnt = 0;
        for (char c : s) {
            if (c == '1') cnt++;
        }
        string ans;
        for (int i = 0; i < n - 1; i++) {
            if (i < cnt - 1) ans.push_back('1');
            else ans.push_back('0');
        }
        ans.push_back('1');
        return ans;
    }
};

美丽塔 I

同下。

美丽塔 II

枚举以每个位置作为山顶，可以得到的最大高度和。通过使用单调栈 + 前后缀分解，可以 \(O(n)\) 的时间算出答案。

class Solution {
public:
    long long maximumSumOfHeights(vector<int>& maxHeights) {
        int n = maxHeights.size();
        vector<long long> left(n + 1), right(n + 1);
        stack<int> stk;
        stk.push(-1);
        for (int i = 0; i < n; i++) {
            while (stk.size() > 1 && maxHeights[stk.top()] > maxHeights[i]) stk.pop();
            left[i + 1] = left[stk.top() + 1] + 1LL * maxHeights[i] * (i - stk.top());
            stk.push(i);
        }
        stk = stack<int>();
        stk.push(n);
        for (int i = n - 1; i >= 0; i--) {
            while (stk.size() > 1 && maxHeights[stk.top()] > maxHeights[i]) stk.pop();
            right[i] = right[stk.top()] + 1LL * maxHeights[i] * (stk.top() - i);
            stk.push(i);
        }
        long long ans = 0;
        for (int i = 0; i < n; i++) {
            ans = max(ans, left[i] + right[i]);
        }
        return ans;
    }
};

统计树中的合法路径数目

树型 DP，对于每个节点，计算以该节点为根的子树中，经过该节点的有效路径数，我们只需要维护子树中不包含质数的路径数和只包含一个质数的路径数。

class Solution {
    private static final int N = (int) 1e5;
    private static final boolean[] np = new boolean[N + 1];

    static {
        np[0] = np[1] = true;
        for (int i = 2; i <= N / i; i++) {
            if (!np[i]) {
                for (int j = i; j <= N / i; j++) {
                    np[j * i] = true;
                }
            }
        }
    }

    long ans = 0L;

    public long countPaths(int n, int[][] edges) {
        List<Integer>[] g = new List[n + 1];
        Arrays.setAll(g, k -> new ArrayList<>());
        for (int[] e : edges) {
            g[e[0]].add(e[1]);
            g[e[1]].add(e[0]);
        }
        dfs(1, 0, g);
        return ans;
    }

    private int[] dfs(int x, int fa, List<Integer>[] g) {
        int zero = 0, one = 0;
        if (np[x]) zero = 1;
        else one = 1;

        for (int y : g[x]) {
            if (y == fa) continue;
            int[] t = dfs(y, x, g);
            ans += (long) zero * t[1] + (long) one * t[0];
            if (np[x]) {
                zero += t[0];
                one += t[1];
            } else {
                one += t[0];
            }
        }
        return new int[]{zero, one};
    }
}