Ligh0x74's Blog

2023-09-27发表2023-09-27更新算法 / Codeforces4 分钟读完 (大约595个字)

Increasing Sequence

模拟，注意最后答案要减一。

public static void solve() {
    int n = io.nextInt();
    int[] a = new int[n];
    for (int i = 0; i < n; i++) {
        a[i] = io.nextInt();
    }

    int b = 1;
    for (int i = 0; i < n; i++) {
        if (b == a[i]) b += 2;
        else b += 1;
    }
    io.println(b - 1);
}

Sets and Union

比赛时写复杂了，就是枚举不选哪个数，使用位运算会很简单。

public static void solve() {
    int n = io.nextInt();

    long xor = 0L;
    long[] s = new long[n];
    for (int i = 0; i < n; i++) {
        int k = io.nextInt();
        for (int j = 0; j < k; j++) {
            s[i] |= 1L << io.nextInt();
        }
        xor |= s[i];
    }

    int ans = 0;
    for (int i = 1; i <= 50; i++) {
        if ((xor >> i & 1) != 1) continue;
        long res = 0L;
        for (int j = 0; j < n; j++) {
            if ((s[j] >> i & 1) != 1) {
                res |= s[j];
            }
        }
        ans = Math.max(ans, Long.bitCount(res));
    }
    io.println(ans);
}

Card Game

思维题，没想出来。不管前两张牌如何操作，都必定可以拿到之后的所有正数牌，然后对前两张牌分类讨论即可。

public static void solve() {
    int n = io.nextInt();
    int[] a = new int[n];
    for (int i = 0; i < n; i++) {
        a[i] = io.nextInt();
    }
    long ans = 0L;
    for (int i = 2; i < n; i++) {
        ans += Math.max(0, a[i]);
    }
    ans += Math.max(0, a[0] + Math.max(0, n > 1 ? a[1] : 0));
    io.println(ans);
}

Tree XOR

很典的换根 DP，因为第三题花费太长时间，导致差几分钟 AC。只要相邻的两个节点值不相同，它们就需要做一次操作。先以一个节点为根做 DFS，并记录所有节点的子树大小，和以该节点为根的成本。然后再做一次 DFS，换根计算代价的差值。（比赛时犯蠢，在换根的过程中打印答案，但是遍历不能保证从 \(1\) 到 \(n\) 的顺序，所以是错的）

private static long[] ans;
private static int[] value, sz;
private static List<Integer>[] g;

public static void solve() {
    int n = io.nextInt();
    value = new int[n];
    for (int i = 0; i < n; i++) {
        value[i] = io.nextInt();
    }
    g = new List[n];
    Arrays.setAll(g, k -> new ArrayList<>());
    for (int i = 0; i < n - 1; i++) {
        int u = io.nextInt() - 1, v = io.nextInt() - 1;
        g[u].add(v);
        g[v].add(u);
    }
    sz = new int[n];
    ans = new long[n];
    dfs1(0, -1);
    dfs2(0, -1);
    for (int i = 0; i < n; i++) {
        io.print(ans[i] + " ");
    }
    io.println();
}

private static void dfs1(int x, int fa) {
    sz[x] = 1;
    for (int y : g[x]) {
        if (y == fa) continue;
        dfs1(y, x);
        sz[x] += sz[y];
        ans[0] += (long) sz[y] * (value[x] ^ value[y]);
    }
}

private static void dfs2(int x, int fa) {
    for (int y : g[x]) {
        if (y == fa) continue;
        ans[y] = ans[x] + (long) (sz[0] - sz[y] - sz[y]) * (value[x] ^ value[y]);
        dfs2(y, x);
    }
}

2023-09-27发表2023-09-27更新算法 / LeetCode3 分钟读完 (大约464个字)

第 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};
    }
}

2023-09-27发表2023-09-27更新算法 / AtCoder3 分钟读完 (大约401个字)

AtCoder Beginner Contest 321

321-like Checker

模拟。

public static void solve() {
    int n = io.nextInt();
    String s = String.valueOf(n);
    for (int i = 0; i < s.length() - 1; i++) {
        if (s.charAt(i) <= s.charAt(i + 1)) {
            io.println("No");
            return;
        }
    }
    io.println("Yes");
}

Cutoff

比赛时是暴力做的，赛后这个 \(O(1)\) 还想了半天。不多解释，代码还是比较好理解的。

public static void solve() {
    int n = io.nextInt(), x = io.nextInt();
    int min = 101, max = -1, sum = 0;
    for (int i = 0; i < n - 1; i++) {
        int t = io.nextInt();
        sum += t;
        min = Math.min(min, t);
        max = Math.max(max, t);
    }
    int t = x - (sum - min - max);
    if (t > max) {
        io.println(-1);
    } else {
        io.println(t <= min ? 0 : t);
    }
}

321-like Searcher

原来是使用十个二进制位来表示对应数字是否存在，通过暴力枚举算出所有可能的数，最后排序获取对应的位置即可，真的没想到。

public static void solve() {
    int k = io.nextInt();
    List<Long> ans = new ArrayList<>();
    for (int i = 2; i < 1 << 10; i++) {
        long x = 0L;
        for (int j = 9; j >= 0; j--) {
            if ((i >> j & 1) == 1) {
                x = x * 10 + j;
            }
        }
        ans.add(x);
    }
    Collections.sort(ans);
    io.println(ans.get(k - 1));
}

二分，状态真差，把加法和乘法混淆了。

public static void solve() {
    int n = io.nextInt(), m = io.nextInt(), p = io.nextInt();
    int[] a = new int[n];
    for (int i = 0; i < n; i++) {
        a[i] = io.nextInt();
    }
    int[] b = new int[m];
    for (int i = 0; i < m; i++) {
        b[i] = io.nextInt();
    }
    Arrays.sort(b);
    long[] sum = new long[m + 1];
    for (int i = 0; i < m; i++) {
        sum[i + 1] = sum[i] + b[i];
    }
    long ans = 0L;
    for (int i = 0; i < n; i++) {
        int x = p - a[i];
        int lo = 0, hi = m - 1;
        while (lo <= hi) {
            int mid= lo + (hi - lo) / 2;
            if (b[mid] <= x) lo = mid + 1;
            else hi = mid - 1;
        }
        ans += ((long) lo * a[i] + sum[lo]) + (long) (m - lo) * p;
    }
    io.println(ans);
}