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

第 366 场力扣周赛

分类求和并作差

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

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

最小处理时间

排序 + 贪心。

1
2
3
4
5
6
7
8
9
10
11
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 不满足条件时的返回值也设置为该值，而判断是否记忆化的条件也设置为该值，所以所有不满足条件的方案都没有记忆化上。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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)\) 的解法，其实比赛时第一眼差不多就想到这种解法，但是没有细想。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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\) 的个数，贪心的组合成最大的数，然后取平方加入答案即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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;
    }
}
发表更新算法 / LeetCode6 分钟读完 (大约863个字)

第 365 场力扣周赛

有序三元组中的最大值 I

同下。

有序三元组中的最大值 II

方法一：枚举 j

比赛时第一想法是枚举 \(j\)，然后取左边和右边的最大值计算答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public long maximumTripletValue(int[] nums) {
        int n = nums.length;
        int[] pre = new int[n + 1];
        int[] suf = new int[n + 1];
        for (int i = 0; i < n; i++) {
            pre[i + 1] = Math.max(pre[i], nums[i]);
        }
        for (int i = n - 1; i >= 0; i--) {
            suf[i] = Math.max(suf[i + 1], nums[i]);
        }
        long ans = 0L;
        for (int j = 1; j < n - 1; j++) {
            ans = Math.max(ans, (long) (pre[j] - nums[j]) * suf[j + 1]);
        }
        return ans;
    }
}

方法二：枚举 k

参考灵神的题解，可以枚举 \(k\)，使空间复杂度降为 \(O(1)\)。主要想法就是枚举时，维护前缀最大差值。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public long maximumTripletValue(int[] nums) {
        long ans = 0;
        int maxDiff = 0, preMax = 0;
        for (int x : nums) {
            ans = Math.max(ans, (long) maxDiff * x);
            maxDiff = Math.max(maxDiff, preMax - x);
            preMax = Math.max(preMax, x);
        }
        return ans;
    }
}

无限数组的最短子数组

比赛时思路很快出来，但是实现的时候漏掉一些边界条件，导致 WA 多次，本来有机会进第一页的。比较直接的想法是枚举起始位置，然后利用前缀和二分结束的位置，如果满足条件就记入答案。也可以使用哈希表来优化，避免二分。这里贴一下灵神的滑动窗口解法，时间复杂度 \(O(n)\)，空间复杂度 \(O(1)\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int minSizeSubarray(int[] nums, int target) {
        int n = nums.length;
        long sum = 0L, pre = 0L;
        for (int x : nums) sum += x;
        int q = (int) (target / sum), r = (int) (target % sum);
        int lo = 0, hi = 0, ans = Integer.MAX_VALUE;
        while (hi < 2 * n) {
            pre += nums[hi++ % n];
            while (pre > r) {
                pre -= nums[lo++ % n];
            }
            if (pre == r) {
                ans = Math.min(ans, hi - lo);
            }
        }
        return ans == Integer.MAX_VALUE ? -1 : ans + q * n;
    }
}

有向图访问计数

看完题目就知道是内向基环树，直接修改上次的代码，轻松通过，本题是上次的简化版。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
    public int[] countVisitedNodes(List<Integer> edges) {
        int n = edges.size();
        // 建立环外节点的反向边
        int[] in = new int[n];
        List<Integer>[] reverse = new List[n];
        Arrays.setAll(reverse, r -> new ArrayList<>());
        for (int i = 0; i < n; i++) {
            in[edges.get(i)]++;
            reverse[edges.get(i)].add(i);
        }
        // 拓扑序去除环外节点
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (in[i] == 0) q.add(i);
        }
        while (!q.isEmpty()) {
            int x = q.poll();
            if (--in[edges.get(x)] == 0) {
                q.offer(edges.get(x));
            }
        }
        // 记录每个节点在哪个环
        int[] cirNum = new int[n];
        boolean[] vis = new boolean[n];
        List<Integer> circles = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (!vis[i] && in[i] != 0) {
                int cnt = 0;
                for (int cur = i; !vis[cur]; cur = edges.get(cur)) {
                    vis[cur] = true;
                    cirNum[cur] = circles.size();
                    cnt++;
                }
                circles.add(cnt);
            }
        }
        // 对环内的每个节点向环外进行 dfs
        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            if (in[i] != 0) dfs(i, reverse, in, circles.get(cirNum[i]), ans);
        }
        return ans;
    }
    
    private void dfs(int x, List<Integer>[] reverse, int[] in, int len, int[] ans) {
        ans[x] = len;
        for (int y : reverse[x]) {
            if (in[y] != 0) continue;
            dfs(y, reverse, in, len + 1, ans);
        }
    }
}

有个非常简单的写法，参考题解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public int[] countVisitedNodes(List<Integer> edges) {
        int n = edges.size();
        int[] ans = new int[n];
        int[] vis = new int[n];
        for (int i = 0; i < n; i++) {
            if (ans[i] == 0) {
                int cnt = 0, cirLen = 0, totLen = 0, pos = i;
                while (vis[pos] == 0) {
                    vis[pos] = ++cnt;
                    pos = edges.get(pos);
                }
                if (ans[pos] == 0) {
                    cirLen = cnt - vis[pos] + 1;
                    totLen = cnt;
                } else {
                    totLen = cnt + ans[pos];
                }
                pos = i;
                while (ans[pos] == 0) {
                    ans[pos] = Math.max(totLen--, cirLen);
                    pos = edges.get(pos);
                }
            }
        }
        return ans;
    }
}
发表更新算法 / Codeforces5 分钟读完 (大约718个字)

Codeforces Round 901 (Div. 2)

Jellyfish and Undertale

每个工具对答案的贡献为 \(\min(a-1,x_{i})\)，并且答案可能会爆 \(long\)，状态好差，WA 两次。

1
2
3
4
5
6
7
8
public static void solve() {
    int a = io.nextInt(), b = io.nextInt(), n = io.nextInt();
    long ans = b;
    for (int i = 0; i < n; i++) {
        ans += Math.min(a - 1, io.nextInt());
    }
    io.println(ans);
}

Jellyfish and Game

数学题。当 \(k\bmod 2=1\) 时，先手会得到 \(\min(0,maxb-mina)\)；反之，后手此时必然有最小价值的苹果 \(\min(mina,minb)\)，而先手此时会有最大价值的苹果 \(\max(maxa,maxb)\)，做一次交换即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public static void solve() {
    int n = io.nextInt(), m = io.nextInt(), k = io.nextInt();

    long suma = 0L;
    int mina = Integer.MAX_VALUE, maxa = Integer.MIN_VALUE;
    for (int i = 0; i < n; i++) {
        int x = io.nextInt();
        suma += x;
        mina = Math.min(mina, x);
        maxa = Math.max(maxa, x);
    }

    int minb = Integer.MAX_VALUE, maxb = Integer.MIN_VALUE;
    for (int i = 0; i < m; i++) {
        int x = io.nextInt();
        minb = Math.min(minb, x);
        maxb = Math.max(maxb, x);
    }

    if (k % 2 == 1) {
        io.println(suma + Math.max(0, maxb - mina));
    } else {
        io.println(suma + Math.max(0, maxb - mina) - Math.max(maxa, maxb) + Math.min(mina, minb));
    }
}

Jellyfish and Green Apple

完了，官方解法看不懂，下面是我的解法，就是一直乘二求余，贪心的拆分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static void solve() {
    int n = io.nextInt(), m = io.nextInt();

    int x = n % m, y = m / gcd(n, m);
    if ((y & (y - 1)) != 0) {
        io.println(-1);
        return;
    }

    long ans = 0L;
    while (x != 0) {
        ans += x;
        x *= 2;
        x %= m;
    }
    io.println(ans);
}

private static int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

下面是官解，大概懂了。\(\frac{a}{b}\) 表示最终每个人得到的苹果价值的小数部分（可以表示为 \(\sum_{i\in S}\frac{1}{2^{i}}\)），因为 \(b\) 必须是二的幂，所以 \(a\) 中 \(1\) 的个数就表示这个人所需的最小苹果片数（就是集合 \(S\) 中元素的个数），乘以 \(m\) 就表示最后总共的苹果片数，然后减去最开始的 \(n\) 片就是需要进行操作的次数（因为每次操作会增加 \(1\) 片）。（这个题解很详细，提供了另一种视角）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static void solve() {
    int n = io.nextInt(), m = io.nextInt();

    n %= m;
    int x = gcd(n, m), a = n / x, b = m / x;
    if ((b & (b - 1)) != 0) {
        io.println(-1);
    } else {
        io.println((long) Integer.bitCount(a) * m - n);
    }
}

private static int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

Jellyfish and Mex

其实是很简单的动态规划，但就是动不起来啊。定义 \(dp[i]\) 为将 \(MEX\) 变为 \(i\) 需要的最小代价，然后从大到小转移即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
private static final int N = 5001;

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

    int mex = 0;
    while (cnt[mex] > 0) mex++;
    long[] dp = new long[mex + 1];
    Arrays.fill(dp, Long.MAX_VALUE);
    dp[mex] = 0;
    for (int i = mex - 1; i >= 0; i--) {
        for (int j = i + 1; j <= mex; j++) {
            dp[i] = Math.min(dp[i], dp[j] + (long) (cnt[i] - 1) * j + i);
        }
    }
    io.println(dp[0]);
}
关注我

链接

分类

最新文章

归档

标签

Debugging2
Draft1
Hexo1

链接

×