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

Codeforces Round 891 (Div. 3)

Array Coloring

要将数组分为奇偶性相同的两部分，那么奇数的个数一定要是偶数。

1
2
3
4
5
6
7
public static void solve() {
    int n = io.nextInt(), sum = 0;
    for (int i = 0; i < n; i++) {
        sum += io.nextInt();
    }
    io.println(sum % 2 == 0 ? "YES" : "NO");
}

Maximum Rounding

题目有点难读，其实就是大于等于 \(5\) 的数可以向前进位，并且包括自己在内的所有低位全部置为 \(0\)。

1
2
3
4
5
6
7
8
9
10
11
12
public static void solve() {
    char[] s = io.next().toCharArray();
    int n = s.length, c = 0, p = n;
    for (int i = n - 1; i > 0; i--) {
        if (s[i] >= '5') {
            s[i - 1]++;
            p = i;
        }
    }
    if (s[0] >= '5') io.println("1" + "0".repeat(n));
    else io.println(new String(s, 0, p) + "0".repeat(n - p));
}

Assembly via Minimums

对数组排序，最小值会出现 \(n - 1\) 次，次小值会出现 \(n - 2\) 次，以此类推，次大值出现 \(1\) 次，最大值出现 \(0\) 次，所以最后需要补一个最大值。

1
2
3
4
5
6
7
8
9
10
11
12
public static void solve() {
    int n = io.nextInt(), m = n * (n - 1) / 2;
    int[] b = new int[m];
    for (int i = 0; i < m; i++) {
        b[i] = io.nextInt();
    }
    Arrays.sort(b);
    for (int i = 0; i < m; i += --n) {
        io.print(b[i] + " ");
    }
    io.println(b[m - 1]);
}

Strong Vertices

将公式变形，易知 \(a_{u} - b_{u}\) 的值最大的元素是强壮的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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 max = Integer.MIN_VALUE, cnt = 0;
    for (int i = 0; i < n; i++) {
        a[i] -= io.nextInt();
        if (a[i] > max) {
            max = a[i];
            cnt = 1;
        } else if (a[i] == max) {
            cnt++;
        }
    }
    io.println(cnt);
    for (int i = 0; i < n; i++) {
        if (a[i] == max) {
            io.print(i + 1 + " ");
        }
    }
    io.println();
}

Power of Points

对于每个 \(x_{i}\) 构成的区间，\(\sum_{p=1}^{10^9}f_{p}\) 表示所有区间包含的元素的个数的和。暴力计算的时间复杂度是 \(O(n^{2})\)，但是我们可以考虑 \(x\) 从从小到大转移时，元素个数的变化量，从而使用 \(O(n\log n)\) 的时间复杂度计算出所有答案。（也可以像官解一样推公式）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static void solve() {
    int n = io.nextInt();
    long sum = 0L;
    int[] x = new int[n];
    Integer[] aux = new Integer[n];
    for (int i = 0; i < n; i++) {
        x[i] = io.nextInt();
        sum += x[i];
        aux[i] = i;
    }
    Arrays.sort(aux, (i, j) -> x[i] - x[j]);
    long[] ans = new long[n];
    ans[aux[0]] = sum -= (long) n * (x[aux[0]] - 1);
    for (int k = 1; k < n; k++) {
        sum += (long) (k - (n - k)) * (x[aux[k]] - x[aux[k - 1]]);
        ans[aux[k]] = sum;
    }
    for (long s : ans) io.print(s + " ");
    io.println();
}

Sum and Product

解方程。。因为要求是整数解，所以根号下必须是完全平方数。还有要注意 \(\Delta\) 小于零的情况，不过 Java 的开根函数在小于零的情况下会返回 NaN，转成整数就是零，在该题目的判断中不会引发问题，但还是最好特判一下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static void solve() {
    int n = io.nextInt();
    Map<Long, Integer> map = new HashMap<>();
    for (int i = 0; i < n; i++) {
        map.merge((long) io.nextInt(), 1, Integer::sum);
    }
    int q = io.nextInt();
    for (int i = 0; i < q; i++) {
        long x = io.nextInt(), y = io.nextLong();
        long d = x * x - 4 * y, s = (long) Math.sqrt(d);
        if (d < 0 || s * s != d) {
            io.print(0 + " ");
            continue;
        }
        long c1 = map.getOrDefault((x + s) / 2, 0);
        long c2 = map.getOrDefault((x - s) / 2, 0);
        if (s != 0) io.print(c1 * c2 + " ");
        else io.print(c1 * (c1 - 1) / 2 + " ");
    }
    io.println();
}

Counting Graphs

如果要在 \(u\) 和 \(v\) 之间添加一条边，那么首先要求 \(u\) 和 \(v\) 之间没有直接相连的边，并且新添加的边的权重要大于 \(w\) 小于 \(S\)，这样才能保证最小生成树是给定的树。暴力求解的时间复杂度是 \(O(n^{2})\)，我们可以利用 Kruskal 算法优化，对边按权重从小到大排序，然后在连接两个顶点时计算两棵树之间顶点连接的方案数，将所有计算结果相乘就是答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
private static final int MOD = 998244353;

public static void solve() {
    int n = io.nextInt(), S = io.nextInt();
    List<int[]> edges = new ArrayList<>();
    for (int i = 0; i < n - 1; i++) {
        int u = io.nextInt(), v = io.nextInt(), w = io.nextInt();
        edges.add(new int[]{u, v, w});
    }
    edges.sort((a, b) -> a[2] - b[2]);
    long ans = 1L;
    UnionFind uf = new UnionFind(n + 1);
    for (int[] e : edges) {
        int u = e[0], v = e[1], w = e[2];
        ans = (ans * fastPower(S - w + 1, (long) uf.size(u) * uf.size(v) - 1)) % MOD;
        uf.union(u, v);
    }
    io.println(ans);
}
发表更新算法 / LeetCode9 分钟读完 (大约1366个字)

第 357 场力扣周赛

故障键盘

方法一：暴力模拟

比赛直接暴力模拟。

1
2
3
4
5
6
7
8
9
10
class Solution {
    public String finalString(String s) {
        StringBuilder sb = new StringBuilder();
        for (char c : s.toCharArray()) {
            if (c != 'i') sb.append(c);
            else sb.reverse();
        }
        return sb.toString();
    }
}

复杂度分析

  • 时间复杂度：\(O(n^{2})\)。
  • 空间复杂度：\(O(n)\)。

方法二：双端队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public String finalString(String s) {
        int n = s.length();
        boolean reverse = false;
        Deque<Character> q = new LinkedList<>();
        for (char c : s.toCharArray()) {
            if (c == 'i') reverse = !reverse;
            else if (reverse) q.offerFirst(c);
            else q.offerLast(c);
        }
        StringBuilder sb = new StringBuilder();
        while (!q.isEmpty()) {
            if (reverse) sb.append(q.pollLast());
            else sb.append(q.pollFirst());
        }
        return sb.toString();
    }
}

复杂度分析

  • 时间复杂度：\(O(n)\)。
  • 空间复杂度：\(O(n)\)。

判断是否能拆分数组

方法一：正难则反

题目要求将数组拆分为单个元素，因为从拆分角度不太好模拟，所以可以考虑怎么将单个元素合并为整个数组。如果数组长度小于等于 \(2\)，则必定满足要求。如果数组长度大于 \(2\)，要想将所有元素合并成完整的数组，则必须有一个大于等于 \(m\) 的合并。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public boolean canSplitArray(List<Integer> nums, int m) {
        int n = nums.size();
        if (n <= 2) return true;
        for (int i = 1; i < n; i++) {
            if (nums.get(i) + nums.get(i - 1) >= m) {
                return true;
            }
        }
        return false;
    }
}

复杂度分析

  • 时间复杂度：\(O(n)\)。
  • 空间复杂度：\(O(1)\)。

找出最安全路径

纯暴力做法是使用 \(O(n^{2})\) 的时间判断当前点的的安全系数是否大于等于指定的安全系数，总时间复杂度是 \(O(n^{4}\log n)\)。而我在比赛时预处理了一下小偷的位置，最坏情况其实也是 \(O(n^{4}\log n)\)，结果通过了，我想大概是因为如果小偷的数量很多，那么 BFS 的限制就多，如果小偷的数量很少，那么 BFS 的限制就少，所以复杂度也不会真的到达最坏情况吧。比较好的做法是多源 BFS + 二分，以每个小偷为起点进行多源 BFS，标记每个位置的最小安全系数，然后在二分的 BFS 时就可以花 \(O(1)\) 的时间判断当前点是否合法。

方法一：多源 BFS + 二分

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
54
55
56
57
58
59
class Solution {
    int n;
    int[][] dis;
    int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};

    public int maximumSafenessFactor(List<List<Integer>> grid) {
        n = grid.size();
        // 以每个小偷为起点进行多源 BFS
        dis = new int[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(dis[i], -1);
        }
        Queue<int[]> q = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid.get(i).get(j) == 1) {
                    dis[i][j] = 0;
                    q.offer(new int[]{i, j});
                }
            }
        }
        while (!q.isEmpty()) {
            int[] p = q.poll();
            int x = p[0], y = p[1];
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i], ny = y + dy[i];
                if (nx < 0 || nx >= n || ny < 0 || ny >= n || dis[nx][ny] >= 0) continue;
                dis[nx][ny] = dis[x][y] + 1;
                q.offer(new int[]{nx, ny});
            }
        }
        // 二分答案
        int lo = 0, hi = Math.min(dis[0][0], dis[n - 1][n - 1]);
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (check(mid)) lo = mid + 1;
            else hi = mid - 1;
        }
        return hi;
    }

    private boolean check(int mid) {
        boolean[][] vis = new boolean[n][n];
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{0, 0});
        vis[0][0] = true;
        while (!q.isEmpty()) {
            int[] p = q.poll();
            int x = p[0], y = p[1];
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i], ny = y + dy[i];
                if (nx < 0 || nx >= n || ny < 0 || ny >= n || vis[nx][ny] || dis[nx][ny] < mid) continue;
                vis[nx][ny] = true;
                q.offer(new int[]{nx, ny});
            }
        }
        return vis[n - 1][n - 1];
    }
}

复杂度分析

  • 时间复杂度：\(O(n^{2}\log n)\)。
  • 空间复杂度：\(O(n^{2})\)。

子序列最大优雅度

方法一：贪心

刚看见题目不知道怎么做，想了想动态规划好像不太行，一个是时间复杂度不行，一个是找不到递推关系（感觉）。然后就想这个数据量，可以排序试一下，然后不知怎么就想到正确答案了。首先贪心取利润最大的 \(k\) 个元素，然后每当遇到一个未选过的类别，则用其替换之前的重复类别中的利润最小的元素，每次计算都更新答案。具体分析如下：

  • 如果第 \(k+1\) 个元素的类别是重复的，那么使用其替换之前的元素不会使优雅度变大，因为 distinct_categories 不变，并且数组元素按照利润降序排列，所以 total_profit 可能会变小或者不变。
  • 反之，我们可以尝试使用当前元素替换之前的元素：① 如果替换之前不重复的元素，那么显然不会优雅度不会变大；② 如果替换之前重复的元素，那么肯定优先选择利润最小的重复元素，distinct_categories 变大，total_profit 变小，优雅度有变大的可能。

反复执行上述操作，就一定可以遍历到最优的情况。比赛时代码很乱，赛后参考了灵神的代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public long findMaximumElegance(int[][] items, int k) {
        int n = items.length;
        long ans = 0, sum = 0;
        Arrays.sort(items, (a, b) -> b[0] - a[0]);
        HashSet<Integer> set = new HashSet<>();
        Deque<Integer> q = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            int profit = items[i][0], category = items[i][1];
            if (i < k) {
                sum += profit;
                if (!set.add(category)) q.push(profit);
            } else if (!q.isEmpty() && set.add(category)) {
                sum += profit - q.pop();
            }
            ans = Math.max(ans, sum + (long) set.size() * set.size());
        }
        return ans;
    }
}

复杂度分析

  • 时间复杂度：\(O(n\log n)\)。
  • 空间复杂度：\(O(n)\)。
发表更新算法 / LeetCode6 分钟读完 (大约832个字)

第 110 场力扣夜喵双周赛

取整购买后的账户余额

方法一：模拟

比赛时没看明白，写复杂了一点。

1
2
3
4
5
class Solution {
    public int accountBalanceAfterPurchase(int purchaseAmount) {
        return 100 - (purchaseAmount + 5) / 10 * 10;
    }
}

复杂度分析

  • 时间复杂度：\(O(1)\)。
  • 空间复杂度：\(O(1)\)。

在链表中插入最大公约数

方法一：模拟

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public ListNode insertGreatestCommonDivisors(ListNode head) {
        ListNode cur = head;
        while (cur.next != null) {
            cur.next = new ListNode(gcd(cur.val, cur.next.val), cur.next);
            cur = cur.next.next;
        }
        return head;
    }
    
    private int gcd(int a, int b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }
}

复杂度分析

  • 时间复杂度：\(O(n\log m)\)，其中 \(m\) 表示节点的最大值。
  • 空间复杂度：\(O(1)\)。

使循环数组所有元素相等的最少秒数

方法一：枚举

假设最后数组中的元素是 \(x\)，那么需要的最少秒数就是所有值为 \(x\) 的元素之间的最大间距的一半向上取整。由于数组是循环数组，我们可以在遍历时添加两次，或者在处理哈希表中的列表时特殊处理最后一个元素与第一个元素的间距。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int minimumSeconds(List<Integer> nums) {
        int n = nums.size();
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < 2 * n; i++) {
            map.computeIfAbsent(nums.get(i % n), k -> new ArrayList<>()).add(i);
        }
        int ans = Integer.MAX_VALUE;
        for (var list : map.values()) {
            int m = list.size(), max = 0;
            for (int i = 0; i < m - 1; i++) {
                max = Math.max(max, list.get(i + 1) - list.get(i) - 1);
            }
            ans = Math.min(ans, (max + 1) / 2);
        }
        return ans;
    }
}

复杂度分析

  • 时间复杂度：\(O(n)\)。
  • 空间复杂度：\(O(n)\)。

使数组和小于等于 x 的最少时间

方法一：动态规划

比赛时其实很多点都想到了，当时遇到的问题就是不知道如何对 \(nums1[i]+nums2[i]\times t\) 排序，没想到要用动态规划，而且动态规划的建模方式有点技巧性，利用了排序来确定选择的第 \(j\) 个数就是在时间 \(j\) 操作的数。

状态定义：\(dp[i][j]\) 表示从前 \(i\) 个数中选择 \(j\) 个数进行操作，可以使元素和减少的最大值（相对于不进行任何操作）。因为我们将 \(aux\) 按照 \(nums_{2}\) 从小到大排序，所以如果 \(i\) 是选择的第 \(j\) 个数，那么就表示在时间 \(j\) 操作 \(i\)，因此减少的时间为 \(nums_{1}[aux[i]]+nums_{2}[aux[i]]\times j\)。

状态转移方程：\(dp[i+1][j]=\max(dp[i][j],dp[i][j-1]+nums_{1}[aux[i]]+nums_{2}[aux[i]]\times j)\)。

可以将空间复杂度优化为 \(O(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
class Solution {
    public int minimumTime(List<Integer> nums1, List<Integer> nums2, int x) {
        int n = nums1.size(), sum1 =0, sum2 = 0;
        Integer[] aux = new Integer[n];
        for (int i = 0; i < n; i++) {
            aux[i] = i;
            sum1 += nums1.get(i);
            sum2 += nums2.get(i);
        }
        Arrays.sort(aux, (a, b) -> nums2.get(a) - nums2.get(b));
        // 动态规划
        int[][] dp = new int[n + 1][n + 1];
        for (int i = 0; i < n; i++) {
            for (int j = n; j > 0; j--) {
                dp[i + 1][j] = Math.max(dp[i][j], dp[i][j - 1] + nums1.get(aux[i]) + nums2.get(aux[i]) * j);
            }
        }
        // 枚举答案
        for (int i = 0; i <= n; i++) {
            if (sum1 + sum2 * i - dp[n][i] <= x) {
                return i;
            }
        }
        return -1;
    }
}

复杂度分析

  • 时间复杂度：\(O(n^{2})\)。
  • 空间复杂度：\(O(n^{2})\)。
关注我

链接

分类

最新文章

归档

标签

Debugging2
Draft1
Hexo1

链接

×