发表更新算法 / 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})\)。
发表更新算法 / AtCoder5 分钟读完 (大约797个字)

AtCoder Beginner Contest 313

To Be Saikyo

简单模拟。

1
2
3
4
5
6
7
public static void solve() {
    int n = io.nextInt(), x = io.nextInt(), max = 0;
    for (int i = 1; i < n; i++) {
        max = Math.max(max, io.nextInt());
    }
    io.println(Math.max(max - x + 1, 0));
}

Who is Saikyo?

如果 \(A\) 比 \(B\) 强，则让 \(B\) 的入度加一，最后入度为零的程序员就是最强的，如果多于一个那么返回 \(-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();
    int[] in = new int[n + 1];
    for (int i = 0; i < m; i++) {
        int u = io.nextInt(), v = io.nextInt();
        in[v]++;
    }
    int ans = 0, cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (in[i] == 0) {
            ans = i;
            cnt++;
        }
    }
    io.println(cnt == 1 ? ans : -1);
}

Approximate Equalization 2

假设我们将数组 \(A\) 执行最少操作后得到数组 \(B\) ，那么 \(\frac{\sum_{i=1}^{N}|A_{i}-B{i}|}{2}\) 就是最小操作次数，因为必定有 \(\sum_{i=1}^{N}A_{i}=\sum_{i=1}^{N}B_{i}\) ，所以上述公式一定可以被二整除。题目要求 \(B\) 的最大值和最小值的差最多为一，那么 \(B\) 一定由 \(N-r\) 个 \(p\) ，以及 \(r\) 个 \(p+1\) 组成，其中 \(p=\frac{\sum_{i=1}^{N}B_{i}}{N},r=\sum_{i=1}^{N}B_{i}\bmod N\) 。然后问题就变为如何组织 \(A_{i}\) 和 \(B_{i}\) 的对应关系，使得 \(\frac{\sum_{i=1}^{N}|A_{i}-B{i}|}{2}\) 最小。显然对数组 \(A\) 进行升序排序，那么数组 \(B\) 的 \(N-r\) 个 \(p\) 对应 \(A\) 的前 \(N-r\) 个元素，数组 \(B\) 的 \(r\) 个 \(p+1\) 对应 \(A\) 的后 \(r\) 个元素，这样排列会使得操作次数最小。

PS：比赛时没什么思路，猜了个平均数，然后没有排序通过遍历比较大小来计算操作次数，结果和正解殊途同归了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static void solve() {
    int n = io.nextInt();
    long sum = 0L;
    int[] arr = new int[n];
    for (int i = 0; i < n; i++) {
        arr[i] = io.nextInt();
        sum += arr[i];
    }
    // 可以替换为快速选择
    Arrays.sort(arr);
    long ans = 0L, p = sum / n, r = sum % n;
    for (int i = 0; i < n; i++) {
        ans += Math.abs(arr[i] - (p + (i >= n - r ? 1 : 0)));
    }
    io.println(ans / 2);
}

Odd or Even

每次查询的返回值可以看作 \(A_{x_{1}}\oplus A_{x_{2}}\oplus \cdots \oplus A_{x_{k}}\) ，所以我们可以首先对前 \(k+1\) 个数进行 \(k+1\) 次查询，然后把所有查询结果异或，可以得到前 \(k+1\) 个数的异或值（因为在 \(k+1\) 次查询中，每个数出现 \(k\) 次，并且 \(k\) 是奇数），将该异或值分别与之前的查询结果异或，可以得到前 \(k+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
27
28
29
30
31
32
33
34
35
36
public static void solve() {
    int n = io.nextInt(), k = io.nextInt(), xor = 0;
    List<Integer> aux;
    int[] ans = new int[n];
    for (int i = 0; i <= k; i++) {
        aux = new ArrayList<>();
        for (int j = 0; j <= k; j++) {
            if (i != j) aux.add(j);
        }
        ans[i] = query(aux);
        xor ^= ans[i];
    }
    for (int i = 0; i <= k; i++) ans[i] ^= xor;
    xor ^= ans[k] ^ ans[k - 1];
    aux = new ArrayList<>();
    for (int i = 0; i < k; i++) aux.add(i);
    for (int i = k + 1; i < n; i++) {
        aux.set(k - 1, i);
        ans[i] = query(aux) ^ xor;
    }
    io.print("! ");
    for (int i = 0; i < n; i++) {
        io.print(ans[i] + " ");
    }
    io.println();
}

private static int query(List<Integer> aux) {
    io.print("? ");
    for (int x : aux) {
        io.print(x + 1 + " ");
    }
    io.println();
    io.flush();
    return io.nextInt();
}
发表更新算法 / Codeforces7 分钟读完 (大约1057个字)

Codeforces Round 889 (Div. 2)

Dalton the Teacher

如果伤心的学生有 \(x\) 个，则答案为 \(\lceil \frac{x}{2}\rceil\)。步骤如下：如果至少有两个伤心的学生，则交换他们的椅子；如果只有一个伤心的学生，则让他和任意其他学生交换椅子。

1
2
3
4
5
6
7
8
9
public static void solve() {
    int n = io.nextInt(), cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (i == io.nextInt()) {
            cnt++;
        }
    }
    io.println((cnt + 1) / 2);
}

Longest Divisors Interval

这道题感觉很妙啊，比赛时看到 \(n\) 的范围很大，所以猜了一个结论也没有细想，结果是对的。假设我们已经找到区间 \([l,r]\) 对每个满足 \(l\leq i\leq r\) 的 \(i\)，\(n\bmod i=0\)。然后我们可以将区间 \([l,r]\) 转化为区间 \([1,r-l+1]\)，因为对每个满足 \(1\leq x\leq r-l+1\) 的 \(x\)，在区间 \([l,r]\) 中总是可以找到一个数 \(y\)，使得 \(y\bmod x=0\)，因而也满足 \(n\bmod x=0\)。

为什么总是可以找到呢？因为一个连续的数列，对 \(x\) 取余得到的余数的周期为 \(x\)，所以一个长度为 \(x\) 的区间内，总是可以找到一个数 \(y\)，使得 \(y\bmod x=0\)。

时间复杂度 \(O(\log{(\max n)})\)，具体不知道怎么算的。

1
2
3
4
5
6
7
8
9
public static void solve() {
    long n = io.nextLong();
    for (int i = 1; ; i++) {
        if (n % i != 0) {
            io.println(i - 1);
            return;
        }
    }
}

Dual (Easy Version), Dual (Hard Version)

比赛时想到找最大或最小的数和倍增，但是没弄明白。首先，如果所有数都非负或非正，那么只要做前缀或后缀和就可以得到非递减的数组，最多操作 \(19\) 次。此时我们还剩下 \(31-19=12\) 次操作机会，我们考虑如何在 \(12\) 次操作内把数组中的数都变为非负或非正：

  • 当最大的正数加最小的负数大于等于零时：如果负数的数量小于等于 \(12\)，那么我们可以在 \(12\) 次操作内把所有负数变为正数；反之，我们可以选择一个负数让它倍增 \(5\) 次，它就会变为最小的负数，并且最大的正数加最小的负数一定小于零，然后我们就可以在 \(7\) 次操作内把所有正数变为负数（因为此时正数的数量小于 \(7\)）。
  • 当最大的正数加最小的负数小于等于零时：同理。
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
60
61
62
public static void solve() {
    int n = io.nextInt();
    int[] arr = new int[n];
    int minPos = 0, maxPos = 0, neg = 0, pos = 0;
    for (int i = 0; i < n; i++) {
        arr[i] = io.nextInt();
        if (arr[i] < 0) neg++;
        if (arr[i] > 0) pos++;
        if (arr[i] < arr[minPos]) minPos = i;
        if (arr[i] > arr[maxPos]) maxPos = i;
    }
    List<int[]> ans = new ArrayList<>();
    if (arr[minPos] + arr[maxPos] >= 0) {
        if (neg <= 12) {
            for (int i = 0; i < n; i++) {
                if (arr[i] < 0) {
                    ans.add(new int[]{i, maxPos});
                }
            }
            for (int i = 0; i < n - 1; i++) {
                ans.add(new int[]{(i + 1), i});
            }
        } else {
            for (int i = 0; i < 5; i++) {
                ans.add(new int[]{minPos, minPos});
            }
            for (int i = 0; i < n; i++) {
                if (arr[i] > 0) {
                    ans.add(new int[]{i, minPos});
                }
            }
            for (int i = n - 2; i >= 0; i--) {
                ans.add(new int[]{i, (i + 1)});
            }
        }
    } else {
        if (pos <= 12) {
            for (int i = 0; i < n; i++) {
                if (arr[i] > 0) {
                    ans.add(new int[]{i, minPos});
                }
            }
            for (int i = n - 2; i >= 0; i--) {
                ans.add(new int[]{i, (i + 1)});
            }
        } else {
            for (int i = 0; i < 5; i++) {
                ans.add(new int[]{maxPos, maxPos});
            }
            for (int i = 0; i < n; i++) {
                if (arr[i] < 0) {
                    ans.add(new int[]{i, maxPos});
                }
            }
            for (int i = 0; i < n - 1; i++) {
                ans.add(new int[]{(i + 1), i});
            }
        }
    }
    io.println(ans.size());
    ans.forEach(k -> io.println((k[0] + 1) + " " + (k[1] + 1)));
}

Earn or Unlock

每种方案都有一个可以到达的最远位置 \(x\)，对于该位置我们能够得到的点数是确定的，即为 \(\sum_{i=0}^{x}a_{i} - x\) 点。所以我们只需要枚举每一个最远位置就能够解决问题，如果使用 DFS 时间复杂度是指数级别的，通过使用状压 DP 可以降低时间复杂度。假设当前枚举到位置 \(i\)，当前的可达位置是 \(dp_{i}\)，那么下一个可达位置就是 \(dp_{i+1}=dp_{i}|(dp_{i}<<a_{i})\)，然后如果当前位置可达，我们计算完答案之后需要将当前位置置为 \(0\)，因为对于下一个位置来说，当前位置已经解锁。如果使用 C++ 实现可以直接使用 \(bitset\)，而使用 Java 实现则需要手动写位图，因为 Java 内置的位图没有移位操作。

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
public static void solve() {
    int n = io.nextInt();
    int[] arr = new int[2 * n + 1];
    for (int i = 0; i < n; i++) {
        arr[i] = io.nextInt();
    }
    // 位图
    int m = n * 2 / 64 + 1;
    long[] dp = new long[m];
    long[] dq = new long[m];
    dp[0] = 1L;
    long sum = 0L, ans = 0L;
    for (int i = 0; i < 2 * n; i++) {
        sum += arr[i];
        // 位图左移 arr[i] 位，并且或上它本身
        int p = arr[i] / 64, q = arr[i] % 64;
        for (int j = 0; j < m; j++) {
            dq[j] = dp[j];
            if (j >= p) {
                dq[j] |= dp[j - p] << q;
                if (j > p && q > 0) dq[j] |= dp[j - p - 1] >>> (64 - q);
            }
        }
        long[] tmp = dp;
        dp = dq;
        dq = tmp;
        // 判断当前位是否可达
        p = i / 64;
        q = i % 64;
        if (((dp[p] >> q) & 1) == 1) {
            dp[p] ^= 1L << q;
            ans = Math.max(ans, sum - i);
        }
    }
    io.println(ans);
}
关注我

链接

分类

最新文章

归档

标签

Debugging2
Draft1
Hexo1

链接

×