Ligh0x74's Blog

2023-10-09发表2023-10-09更新语言 / Java1 分钟读完 (大约134个字)

JDK-8299339 : HashMap merge and compute methods can cause odd resizing pathologies

贴一下去年发现的 Bug，嘿嘿。

导致 Bug 的示例代码如下：

public class Main {
    public static void main(String[] args) {
        Map<Integer, Integer> map = new HashMap<>(2);

        map.merge(1, 1, Integer::sum);
        map.merge(2, 1, Integer::sum);

        map.forEach((k, v) -> {
            map.merge(k, -1, Integer::sum);
            System.out.println(k);
        });
    }
}

Java Bug DataBase 链接，里面比较详细的讨论了发生的问题，由于当时急着发出去，我的评论有点乱，而且是中文翻译为英文的，有点拉。

2023-10-09发表2023-10-09更新算法 / Codeforces7 分钟读完 (大约1115个字)

Codeforces Round 902 (Div. 2, based on COMPFEST 15 - Final Round)

Goals of Victory

所有效率之和等于零。

public static void solve() {
    int n = io.nextInt(), sum = 0;
    for (int i = 0; i < n - 1; i++) {
        sum += io.nextInt();
    }
    io.println(-sum);
}

Helmets in Night Light

贪心选择最小花费的通知，注意维护已经被通知的下标，根据该下标判断是否需要加 \(p\)，并且如果某个人通知其他人的成本大于 \(p\)，则他不会通知其他人。发现大佬的解法好简单，取一个最小值，维护一个剩余人数即可。

public static void solve() {
    int n = 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[n];
    for (int i = 0; i < n; i++) {
        b[i] = io.nextInt();
    }

    var aux = new Integer[n];
    for (int i = 0; i < n; i++) {
        aux[i] = i;
    }
    Arrays.sort(aux, (i, j) -> b[i] - b[j]);

    long ans = p;
    int r = n - 1;
    for (int i : aux) {
        int x = Math.min(r, a[i]);
        ans += (long) x * Math.min(p, b[i]);
        r -= x;
    }
    io.println(ans);
}

Joyboard

分类讨论，注意被 \(n\) 整除的数。

public static void solve() {
    int n = io.nextInt(), m = io.nextInt(), k = io.nextInt();
    if (k == 3) io.println(Math.max(0, m - n - m / n + 1));
    else if (k == 2) io.println(m / n + Math.min(n - 1, m));
    else if (k == 1) io.println(1);
    else io.println(0);
}

Effects of Anti Pimples

很容易的想到计算选择每个索引位置，能够得到的最大分数，时间复杂度为 \(O(n\log{n})\)。然后计算每个位置有多少种方案，比赛时我以为选择一个索引位置，默认就选择了它的所有倍数位置，导致不会做。其实只要排序，然后每个位置的方案数就是它左边的数选或不选的方案数，这样可以保证不会重复计算，所以~~快速幂~~计算方案数（可以在遍历的时候计算方案数），再乘以得分累加到答案即可。

private static final int MOD = 998244353;

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

    dp[0] = Integer.MAX_VALUE;
    for (int i = 1; i <= n; i++) {
        for (int j = 2 * i; j <= n; j += i) {
            dp[i] = Math.max(dp[i], dp[j]);
        }
    }

    Arrays.sort(dp);
    long ans = 0L, pow = 1L;
    for (int i = 0; i < n; i++) {
        ans = (ans + dp[i] * pow) % MOD;
        pow = pow * 2 % MOD;
    }
    io.println(ans);
}

Autosynthesis

方法一：内向基环树

对于每个 \(i\)，建立一条从 \(i\) 指向 \(a_{i}\) 的边，最终会得到多个内向基环树。规则一：入度为零的节点不会被选择；规则二：如果一个节点的所有入度节点都被选择，那么它不会被选择；规则三：如果一个节点不被选择，那么它指向的节点会被选择。（以上规则可以使用拓扑序 + 染色法实现）

如图，数组为 \([2,3,4,5,6,3,3,4]\)，剩余索引 \([1,5,7,8]\)，剩余元素 \([2,6,3,4]\)，选择索引 \([2,6,3,4]\)。应用规则一，得出索引 \([1,7,8]\) 不被选择；应用规则三，得出索引 \([2,3,4]\) 被选择；应用规则二，得出索引 \([5]\) 不被选择；应用规则三，得出索引 \([6]\) 被选择。

特殊情况，如果内向基环树没有环外节点，无法应用上述规则，那么需要单独对环交替染色，若此时环的长度为奇数，则没有解，其他情况均有解。也就是说，当且仅当内向基环树没有环外节点，且环的长度为奇数时，无解。

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

    int[] in = new int[n];
    for (int i = 0; i < n; i++) {
        in[a[i]]++;
    }

    // 拓扑序染色（-1 表示不选择，1 表示选择）
    int[] col = new int[n];
    Queue<Integer> q = new LinkedList<>();
    for (int i = 0; i < n; i++) {
        if (in[i] == 0) {
            q.offer(i);
            col[i] = -1;
        }
    }
    while (!q.isEmpty()) {
        int x = q.poll(), y = a[x];
        if (col[y] != 0) continue;
        if (--in[y] == 0 || col[x] == -1) {
            q.offer(y);
            col[y] = -col[x];
        }
    }

    // 单独处理没有环外节点的基环树
    for (int i = 0; i < n; i++) {
        if (col[i] != 0) continue;
        int j = i, pre = -1;
        while (col[j] == 0) {
            col[j] = -pre;
            pre = col[j];
            j = a[j];
        }
        if (col[j] == pre) {
            io.println(-1);
            return;
        }
    }

    List<Integer> ans = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        if (col[i] == -1) ans.add(a[i] + 1);
    }
    io.println(ans.size());
    for (int x : ans) {
        io.print(x + " ");
    }
    io.println();
}

方法二：外向基环树

好像有建立外向基环树的解法，没时间看，在此。

2023-10-09发表2023-10-09更新算法 / LeetCode6 分钟读完 (大约828个字)

第 366 场力扣周赛

分类求和并作差

数学性质，\([1,n]\) 中能被 \(m\) 整除的数有 \(\lfloor \frac{n}{m}\rfloor\) 个。

class Solution {
    public int differenceOfSums(int n, int m) {
        return (1 + n) * n / 2 - (1 + (n / m)) * (n / m) * m;
    }
}

最小处理时间

排序 + 贪心。

class Solution {
    public int minProcessingTime(List<Integer> processorTime, List<Integer> tasks) {
        Collections.sort(processorTime);
        Collections.sort(tasks, (a , b) -> b - a);
        int n = processorTime.size(), ans = 0;
        for (int i = 0; i < n; i++) {
            ans = Math.max(ans, processorTime.get(i) + tasks.get(i * 4));
        }
        return ans;
    }
}

执行操作使两个字符串相等

方法一：动态规划

今天脑子有点笨啊，本来做出来了，但是我将 dp 的初始值设置为 Integer.MAX_VALUE，将 dfs 不满足条件时的返回值也设置为该值，而判断是否记忆化的条件也设置为该值，所以所有不满足条件的方案都没有记忆化上。

我经常会写出从上到下记忆化的代码，但是每次都比从下到上的记忆化慢，经过分析，原因如下：从下到上的记忆化，只要该节点计算过，就会直接返回；而从上到下的记忆化，只有在当前节点的值比记忆化的值大时，才会直接返回，也就是说，这样的代码只会将所有大于记忆化的值的方案给剪枝掉，所有小于记忆化的值的方案会重复计算。

class Solution {
    public int minOperations(String s1, String s2, int x) {
        int n = s1.length();
        int[][][] dp = new int[n][n + 1][2];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n + 1; j++) {
                Arrays.fill(dp[i][j], -1);
            }
        }
        int ans = dfs(0, 0, 0, s1, s2, x, dp);
        return ans >= (int) 1e9 ? -1 : ans;
    }

    private int dfs(int i, int c, int r, String s1, String s2, int x, int[][][] dp) {
        if (i == s1.length()) {
            if (c % 2 == 0 && r == 0) {
                return -c / 2 * x;
            }
            return (int) 1e9;
        }
        if (dp[i][c][r] != -1) return dp[i][c][r];
        int res = 0;
        if ((s1.charAt(i) == s2.charAt(i)) == (r == 0)) {
            res = dfs(i + 1, c, 0, s1, s2, x, dp);
        } else {
            res = dfs(i + 1, c + 1, 0, s1, s2, x, dp) + x;
            res = Math.min(res, dfs(i + 1, c, 1, s1, s2, x, dp) + 1);
        }
        return dp[i][c][r] = res;
    }
}

方法二：动态规划

时间复杂度 \(O(n)\)，空间复杂度 \(O(1)\) 的解法，其实比赛时第一眼差不多就想到这种解法，但是没有细想。

class Solution {
    public int minOperations(String s1, String s2, int x) {
        int n = s1.length();
        int pre = -1, cnt = 0;
        int dp0 = (int) 1e9, dp1 = 0;
        for (int i = 0; i < n; i++) {
            if (s1.charAt(i) != s2.charAt(i)) {
                cnt ^= 1;
                int t = dp1;
                dp1 = Math.min(dp1 + (cnt == 1 ? x : 0), dp0 + i - pre);
                dp0 = t;
                pre = i;
            }
        }
        return cnt == 1 ? -1 : dp1;
    }
}

对数组执行操作使平方和最大

挺简单一道题，T3 卡太久，脑子短路没时间做这题。对于每一位，每次操作其实就是交换两个数之间的 \(0\) 和 \(1\)，我们应该总是把 \(1\) 交换到更大的数上，这样平方和最大。所以统计每一位的 \(1\) 的个数，贪心的组合成最大的数，然后取平方加入答案即可。

class Solution {
    private static final int MOD = (int) 1e9 + 7;

    public int maxSum(List<Integer> nums, int k) {
        int[] cnt = new int[30];
        for (int x : nums) {
            for (int i = 0; i < 30; i++) {
                cnt[i] += x >> i & 1;
            }
        }

        long ans = 0L;
        while (k-- != 0) {
            int x = 0;
            for (int i = 0; i < 30; i++) {
                if (cnt[i] > 0) {
                    cnt[i]--;
                    x |= 1 << i;
                }
            }
            ans = (ans + (long) x * x) % MOD;
        }

        return (int) ans;
    }
}