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

Codeforces Round 893 (Div. 2)

Buttons

优先选择公共按钮，当且仅当先手的按钮数量大于后手的按钮数量时，先手者胜。

1
2
3
4
5
public static void solve() {
    int a = io.nextInt(), b = io.nextInt(), c = io.nextInt();
    if (a + c % 2 > b) io.println("First");
    else io.println("Second");
}

The Walkway

模拟题，特别需要注意头尾的边界处理，加上哨兵真的会方便很多。可以假设位置 \(1-d\) 和位置 \(n+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
public static void solve() {
    int n = io.nextInt(), m = io.nextInt(), d = io.nextInt();
    int[] s = new int[m + 2];
    for (int i = 1; i <= m; i++) {
        s[i] = io.nextInt();
    }
    s[0] = 1 - d;
    s[m + 1] = n + 1;

    int ans = m - 1, delta = Integer.MAX_VALUE, cnt = 0;
    for (int i = 1; i <= m; i++) {
        int A = (s[i] - s[i - 1] - 1) / d;
        int B = (s[i + 1] - s[i] - 1) / d;
        int C = (s[i + 1] - s[i - 1] - 1) / d;
        int D = C - A - B;

        if (D < delta) {
            delta = D;
            cnt = 1;
        } else if (D == delta) {
            cnt++;
        }
        ans += A;
    }
    ans += (s[m + 1] - s[m] - 1) / d + delta - 1;
    io.println(ans + " " + cnt);
}

Yet Another Permutation Problem

构造题，首先需要发现什么公约数不可能出现，很明显不可能得到 \(d_{i}=\gcd (a_{i},a_{(i\bmod n)+1})> \lfloor \frac{n}{2}\rfloor\)。然后考虑所有小于等于 \(\lfloor \frac{n}{2}\rfloor\) 的数是否能被包含，可以发现对于每个 \(a_{i}=x\leq \lfloor \frac{n}{2}\rfloor\) 总有 \(a_{(i\bmod n)+1}=2\cdot x\leq n\)，所以我们可以枚举所有奇数乘以二的幂来构造答案。

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

Trees and Segments

难以描述，看代码吧，调试半天。。

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
public static void solve() {
    int n = io.nextInt(), k = io.nextInt();
    char[] s = io.next().toCharArray();
    int[][] prefix = new int[n + 1][k + 1];
    int[][] suffix = new int[n + 1][k + 1];
    // 枚举可以在 k 次操作内变为全 0 的子数组，并将其长度记录到所属的前后缀中
    for (int i = 0; i < n; i++) {
        int cnt1 = 0;
        for (int j = i; j < n; j++) {
            cnt1 += s[j] - '0';
            if (cnt1 > k) break;
            prefix[j + 1][cnt1] = Math.max(prefix[j + 1][cnt1], j - i + 1);
            suffix[i][cnt1] = Math.max(suffix[i][cnt1], j - i + 1);
        }
    }
    // 在前缀 [0, i] 中最多操作 j 次，可以得到的连续 0 的最长长度
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= k; j++) {
            prefix[i + 1][j] = Math.max(prefix[i + 1][j], prefix[i][j]);
            if (j > 0) prefix[i + 1][j] = Math.max(prefix[i + 1][j], prefix[i + 1][j - 1]);
        }
    }
    // 在后缀 [i, n - 1] 中最多操作 j 次，可以得到的连续 0 的最长长度
    for (int i = n - 1; i >= 0; i--) {
        for (int j = 0; j <= k; j++) {
            suffix[i][j] = Math.max(suffix[i][j], suffix[i + 1][j]);
            if (j > 0) suffix[i][j] = Math.max(suffix[i][j], suffix[i][j - 1]);
        }
    }
    // 枚举连续 1 的起点和终点，并记录该连续 1 的长度对应的连续 0 的最长长度（注意包含长度为 0 的情况）
    int[] max0by1 = new int[n + 1];
    Arrays.fill(max0by1, -1);
    max0by1[0] = suffix[0][k];
    for (int i = 0; i < n; i++) {
        int cnt0 = 0;
        for (int j = i; j < n; j++) {
            cnt0 += (s[j] - '0') ^ 1;
            if (cnt0 > k) break;
            max0by1[j - i + 1] = Math.max(max0by1[j - i + 1], prefix[i][k - cnt0]);
            max0by1[j - i + 1] = Math.max(max0by1[j - i + 1], suffix[j + 1][k - cnt0]);
        }
    }
    // 计算答案
    int[] ans = new int[n + 1];
    for (int a = 1; a <= n; a++) {
        for (int i = 0; i <= n; i++) {
            if (max0by1[i] == -1) continue;
            ans[a] = Math.max(ans[a], i + max0by1[i] * a);
        }
    }
    for (int i = 1; i <= n; i++) {
        io.print(ans[i] + " ");
    }
    io.println();
}
发表更新算法 / LeetCode7 分钟读完 (大约979个字)

第 358 场力扣周赛

数组中的最大数对和

赛时直接暴力做，赛后优化代码参考自灵神。就是维护每个最大数位对应的最大值，然后可以优化掉一个 \(n\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int maxSum(int[] nums) {
        int ans = -1;
        int[] maxVal = new int[10];
        Arrays.fill(maxVal, Integer.MIN_VALUE);
        for (int x : nums) {
            int maxD = 0;
            for (int y = x; y > 0; y /= 10) {
                maxD = Math.max(maxD, y % 10);
            }
            ans = Math.max(ans, x + maxVal[maxD]);
            maxVal[maxD] = Math.max(maxVal[maxD], x);
        }
        return ans;
    }
}

翻倍以链表形式表示的数字

做乘法惯性思维，就想着从最低位开始乘然后进位，结果可以从高位开始乘，因为乘二时低位最多就进一位。（如果从低位开始乘，就转数组或者反转链表吧）

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public ListNode doubleIt(ListNode head) {
        if (head.val > 4) head = new ListNode(0, head);
        for (ListNode cur = head; cur != null; cur = cur.next) {
            cur.val = cur.val * 2 % 10;
            if (cur.next != null && cur.next.val > 4) {
                cur.val++;
            }
        }
        return head;
    }
}

限制条件下元素之间的最小绝对差

一开始没反应过来，以为找最大值和最小值就行。结果发现是让绝对值最小，要找最接近当前值的那个值，那就可以使用 TreeSet。但是我又搞复杂了，其实只要维护一个方向就可以，但是我维护了左右方向距离为 \(x\) 的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int minAbsoluteDifference(List<Integer> nums, int x) {
        int n = nums.size(), ans = Integer.MAX_VALUE;
        TreeSet<Integer> set = new TreeSet<>();
        set.add(Integer.MAX_VALUE);
        set.add(Integer.MIN_VALUE / 2);
        for (int i = x; i < n; i++) {
            set.add(nums.get(i - x));
            int cur = nums.get(i);
            ans = Math.min(ans, Math.min(cur - set.floor(cur), set.ceiling(cur) - cur));
        }
        return ans;
    }
}

操作使得分最大

吐血吐血，赛后 Debug 发现分解质因数的代码打错一个变量，改了就能 AC。一开始也看错题目了，以为答案是乘质数分数，结果答案是乘数组中的值，那么优先选最大的数就是最优的。问题就变成给定某个数，选择它为目标值的数组有多少个。数组的个数等于左边质数分数小于当前值能到达的最远位置，乘右边质数分数大于等于当前值能到达的最远位置。所以我们可以先对质数分数降序排序，相同分数再对下标升序排序，按照这个顺序处理元素，使用 TreeSet 维护已处理的值，就可以比较方便的得到左右两边的边界，从而得到以当前值为目标值的数组个数。最后，按照值从大到小来做乘法。

计算每个位置有多少数组还可以使用单调栈（更快），详情见题解区。

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
class Solution {
    private static final int MOD = (int) 1e9 + 7;
    private static final int N = (int) 1e5 + 1;
    private static int[] f = new int[N];

    // 素数筛
    static {
        for (int i = 2; i < N; i++) {
            if (f[i] == 0) {
                for (int j = i; j < N; j += i) {
                    f[j]++;
                }
            }
        }
    }

    public int maximumScore(List<Integer> nums, int k) {
        // 计算每个位置有多少个数组
        int n = nums.size();
        TreeSet<Integer> set = new TreeSet<>();
        set.add(-1); set.add(n);
        var aux = new Integer[n];
        for (int i = 0; i < n; i++) aux[i] = i;
        Arrays.sort(aux, (a, b) -> {
            int x = nums.get(a), y = nums.get(b);
            return f[x] != f[y] ? f[y] - f[x] : a - b;
        });
        long[] cnt = new long[n];
        for (int i : aux) {
            long l = i - set.ceiling(i);
            long r = set.floor(i) - i;
            cnt[i] = l * r;
            set.add(i);
        }
        // 从大到小枚举值，计算答案
        long ans = 1L;
        for (int i = 0; i < n; i++) aux[i] = i;
        Arrays.sort(aux, (a, b) -> nums.get(b) - nums.get(a));
        for (int i = 0; k > 0; i++) {
            int t = (int) Math.min(cnt[aux[i]], k);
            ans = (ans * power(nums.get(aux[i]), t)) % MOD;
            k -= t;
        }
        return (int) ans;
    }
    
    private long power(long x, int n) {
        long res = 1L;
        while (n != 0) {
            if (n % 2 == 1) res = res * x % MOD;
            x = x * x % MOD;
            n >>= 1;
        }
        return res;
    }
}
发表更新算法 / Codeforces9 分钟读完 (大约1340个字)

Codeforces Round 892 (Div. 2)

United We Stand

要使数组 \(c_{j}\) 不是 \(b_{i}\) 的约数，只要让数组 \(b\) 中只存最小的数，或者让数组 \(c\) 中只存最大的数，就可以满足要求。特别的，如果所有数都相等，那么不存在解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static void solve() {
    int n = io.nextInt();
    int[] arr = new int[n];
    for (int i = 0; i < n; i++) {
        arr[i] = io.nextInt();
    }
    Arrays.sort(arr);
    if (arr[0] == arr[n - 1]) {
        io.println(-1);
        return;
    }
    int it = 0;
    while (arr[it] == arr[0]) it++;
    io.println(it + " " + (n - it));
    for (int i = 0; i < it; i++) io.print(arr[i] + " ");
    io.println();
    for (int i = it; i < n; i++) io.print(arr[i] + " ");
    io.println();
}

Olya and Game with Arrays

要最大化 \(\sum_{i=1}^{n}\min_{j=1}^{m_{i}}a_{i,j}\)，一开始想到最大化最小值，二分？但是有点不太对。然后发现规律，只需要关注数组的最小值和次小值就行。首先所有数组的最小值的最小值一定会被包含在内，这样只要把其他数组的最小值移动到该最最小值所属的数组就可以让答案最大。也就是说答案等于所有数组次小值的和加上最最小值，再减去最最小值对应的次小值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static void solve() {
    int n = io.nextInt();
    int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;
    long sum = 0;
    List<Integer>[] arr = new List[n];
    Arrays.setAll(arr, k -> new ArrayList<>());
    for (int i = 0; i < n; i++) {
        int m = io.nextInt();
        for (int j = 0; j < m; j++) {
            arr[i].add(io.nextInt());
        }
        // 可以不排序，直接遍历找
        Collections.sort(arr[i]);
        sum += arr[i].get(1);
        min1 = Math.min(min1, arr[i].get(0));
        min2 = Math.min(min2, arr[i].get(1));
    }
    io.println(sum - min2 + min1);
}

Another Permutation Problem

题目要求 \((\sum_{i=1}^{n}p_{i}\cdot i)-(\max_{j=1}^{n}p_{j}\cdot j)\) 的最大值，前半部分的最大值的情况就是从小到大排列，但是后半部分不好处理，所以考虑枚举后半部分。从大到小枚举 \(\max_{j=1}^{n}p_{j}\cdot j\) 的值，然后在不超过该值的情况下尽可能使 \(\sum_{i=1}^{n}p_{i}\cdot i\) 的值变大。要让求和的部分变大，也就是让大的 \(p\) 尽可能靠后，可以使用 \(\frac{\max_{j=1}^{n}p_{j}\cdot j}{p}\) 求得 \(p\) 可以放置的最大 \(i\) 是多少，然后如果该位置已经占用，那么就向左寻找第一个未占用的位置。我们可以使用并查集维护位置的占用情况，如果当前位置占用就将它和左边的位置合并，这样 find(Math.min(n, i)) 就是左边第一个的未占用的位置。如果可以放置的位置不存在，那么说明枚举值太小，终止枚举。（也可以使用栈来维护位置的占用情况）

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
private static int[] f;

private static int find(int x) {
    if (x != f[x]) f[x] = find(f[x]);
    return f[x];
}

public static void solve() {
    int n = io.nextInt(), ans = 0;
    // 枚举公式的后半部分的值
    for (int mx = n * n; mx >= 1; mx--) {
        int sum = 0;
        boolean ok = true;
        f = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            f[i] = i;
        }
        // 枚举排列的值
        for (int i = n; i >= 1; i--) {
            // 该值可以放置的最大位置
            int x = find(Math.min(n, mx / i));
            if (x == 0) {
                ok = false;
                break;
            }
            sum += i * x;
            // 当前位置已占用，f[x] 存储左边可以放置的第一个位置
            f[x] = f[x - 1];
        }
        if (!ok) break;
        ans = Math.max(ans, sum - mx);
    }
    io.println(ans);
}

还有一个解法，但是不知道如何证明正确性，也是可以过的。其实比赛的时候我就猜了这个结论，但是当时没试。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static void solve() {
    int n = io.nextInt(), ans = 0;
    // 枚举一个位置，然后反转它以及它后面的值
    for (int i = 1; i <= n; i++) {
        int sum = 0, max = 0;
        for (int j = 1; j <= n; j++) {
            int x = j < i ? j : n - j + i;
            sum += x * j;
            max = Math.max(max, x * j);
        }
        ans = Math.max(ans, sum - max);
    }
    io.println(ans);
}

Andrey and Escape from Capygrad

首先，显然向左传送不会比向右传送到达更远的地方。考虑只有一个区间的情况：如果起点在 \([l,b]\) 之间，那么可以最远到达 \(b\) 点；如果起点在 \((b,r]\) 之间（即不在 \([l,b]\) 之间），那么当前点就是最远的点。可以发现，能够到达的最远位置只与 \(l\) 和 \(b\)，以及起点位置有关。所以考虑将所有区间 \([l,b]\) 合并，对每个查询都查找当前起点所在的区间。如果在某个区间内，最远位置即为该区间的右端点；如果不在任何区间内，那么最远位置即为当前位置。

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[][] portals = new int[n][2];
    // 只需要考虑 l 和 b
    for (int i = 0; i < n; i++) {
        portals[i][0] = io.nextInt();
        io.nextInt();
        io.nextInt();
        portals[i][1] = io.nextInt();
    }
    // 区间合并
    Arrays.sort(portals, (a, b) -> a[0] - b[0]);
    List<int[]> intervals = new ArrayList<>();
    intervals.add(new int[]{Integer.MIN_VALUE, Integer.MIN_VALUE});
    for (int i = 0; i < n; i++) {
        int m = intervals.size();
        if (intervals.get(m - 1)[1] < portals[i][0]) {
            intervals.add(new int[]{portals[i][0], portals[i][1]});
        } else {
            intervals.get(m - 1)[1] = Math.max(intervals.get(m - 1)[1], portals[i][1]);
        }
    }
    // 二分找区间
    int q = io.nextInt();
    for (int i = 0; i < q; i++) {
        int x = io.nextInt();
        int lo = 0, hi = intervals.size() - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (intervals.get(mid)[0] > x) hi = mid - 1;
            else lo = mid + 1;
        }
        io.print(Math.max(x, intervals.get(hi)[1]) + " ");
    }
    io.println();
}
关注我

链接

分类

最新文章

归档

标签

Debugging2
Draft1
Hexo1

链接

×