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

Codeforces Round 904 (Div. 2)

Simple Design

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static void solve() {
    int x = io.nextInt(), k = io.nextInt();
    while (sum(x) % k != 0) {
        x++;
    }
    io.println(x);
}

private static int sum(int x) {
    int res = 0;
    while (x != 0) {
        res += x % 10;
        x /= 10;
    }
    return res;
}

Haunted House

好难啊，做得很慢。对于每个 \(i\)，如果它是满足条件的，那么 \([n-i,n-1]\) 需要全为 \(0\)，它的最少操作次数为 \([n-i,n-1]\) 中所有值为 \(1\) 的下标和，减去 \([0,n-i-1]\) 中最近的值为 \(0\) 的对应个数的下标和。我们可以使用双指针 \(O(n)\) 的计算所有 \(i\)，具体见代码。指针 \(j\) 枚举每个下标，同时求出后缀的下标和，指针 \(i\) 指向指针 \(j\) 需要的最远的 \(0\) 的下标位置，同时求出后缀值为 \(0\) 的下标和，它们的差值就是 \(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();
    String s = io.next();

    long sum = 0L;
    int i, j, cnt = 0;
    for (i = n - 1, j = n - 1; i >= 0; j--) {
        cnt++;
        sum += j;
        for (; i >= 0 && cnt > 0; i--) {
            if (s.charAt(i) == '0') {
                cnt--;
                sum -= i;
            }
        }
        io.print(cnt > 0 ? "-1 " : sum + " ");
    }
    io.println("-1 ".repeat(j + 1));
}

发现一个超级简单的写法，基本思路就是从低到高放置 \(0\)，操作次数即为 \(0\) 的移动次数，废话不多说，代码很好懂。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static void solve() {
    int n = io.nextInt();
    char[] s = io.next().toCharArray();

    long ans = 0L;
    int l = n - 1, r = n - 1;
    for (; l >= 0; l--) {
        if (s[l] == '0') {
            ans += r - l;
            r--;
            io.print(ans + " ");
        }
    }
    io.println("-1 ".repeat(r + 1));
}

Medium Design

最小值一定在位置 \(1\) 或位置 \(m\)，我们可以考虑处理区间不包含 \(1\) 和不包含 \(m\) 两种情况下，能够得到的最大值，根据简单的推导可以知道问题是等价的。如何计算最大值，根据题解所说似乎是扫描线算法，使用 \((l,1)\) 表示进入某个区间，\((r,-1)\) 表示离开某个区间，注意初始时我们将每个左端点减 \(1\)，表示从区间 \(0\) 开始算，\((l,r)\) 是左闭右开区间，所以 \(r\) 表示离开某个区间，然后每当处理完某个端点就更新答案。（其实也可以使用差分哈希表进行区间求和）

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
public static void solve() {
    int n = io.nextInt(), m = io.nextInt();
    int[] l = new int[n];
    int[] r = new int[n];
    for (int i = 0; i < n; i++) {
        l[i] = io.nextInt() - 1;
        r[i] = io.nextInt();
    }
    // 第一次扫描，不包含第一个位置
    List<int[]> list = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        if (l[i] != 0) {
            list.add(new int[]{l[i], 1});
            list.add(new int[]{r[i], -1});
        }
    }
    list.sort((a, b) -> a[0] - b[0]);
    int ans = sweep(list);
	// 第二次扫描，不包含最后一个位置
    list.clear();
    for (int i = 0; i < n; i++) {
        if (r[i] != m) {
            list.add(new int[]{l[i], 1});
            list.add(new int[]{r[i], -1});
        }
    }
    list.sort((a, b) -> a[0] - b[0]);
    ans = Math.max(ans, sweep(list));
    io.println(ans);
}

private static int sweep(List<int[]> list) {
    // cnt 表示在多少个区间内
    // lst 表示上次处理的端点
    int res = 0, cnt = 0, lst = 0;
    for (int[] t : list) {
        if (t[0] > lst) {
            res = Math.max(res, cnt);
        }
        cnt += t[1];
        lst = t[0];
    }
    return res;
}

Counting Rhyme

一对数 \(x,y\) 不能同时被数组中的数整除，即 \(\gcd(x,y)\) 不能被数组中的数整除。我们首先可以计算出数组中有多少对数它们的 \(\gcd=1,2,3\dots,n\)，然后排除掉能够被数组中的数整除的 \(\gcd\)，剩下的 \(\gcd\) 对应的对数之和就是答案。第一步可以使用动态规划求解，转移方程如下：

$$ sum = cnt[i]+cnt[2\times i]+\cdots+cnt[k\times i] \\ dp[i]= \frac{sum\times (sum-1)}{2}-(dp[2\times i]+dp[3\times i]+\cdots+dp[k\times i]) $$

第二步切记不能枚举数组中的数来排除，这样在所有值都为 \(1\) 的样例下时间复杂度会达到 \(O(n^{2})\)，除非将数组去重，或者像下面代码一样枚举。最后计算答案即可。本题的另一种解法是 GCD 卷积，暂时不学。

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

    long[] dp = new long[n + 1];
    for (int i = n; i > 0; i--) {
        long tot = 0L;
        for (int j = i; j <= n; j += i) {
            tot += cnt[j];
            dp[i] -= dp[j];
        }
        dp[i] += tot * (tot - 1) / 2;
    }

    for (int i = 1; i <= n; i++) {
        if (cnt[i] != 0) {
            for (int j = i; j <= n; j += i) {
                dp[j] = 0;
            }
        }
    }

    long ans = 0L;
    for (int i = 1; i <= n; i++) {
        ans += dp[i];
    }
    io.println(ans);
}
发表更新算法 / LeetCode3 分钟读完 (大约523个字)

第 368 场力扣周赛

元素和最小的山形三元组 I

同下。

元素和最小的山形三元组 II

前后缀分解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int minimumSum(int[] nums) {
        int n = nums.length;
        int[] pre = new int[n + 1], suf = new int[n + 1];
        pre[0] = suf[n] = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            pre[i + 1] = Math.min(pre[i], nums[i]);
        }
        for (int i = n - 1; i >= 0; i--) {
            suf[i] = Math.min(suf[i + 1], nums[i]);
        }
        int ans = Integer.MAX_VALUE;
        for (int i = 1; i < n - 1; i++) {
            if (nums[i] > pre[i] && nums[i] > suf[i + 1]) {
                ans = Math.min(ans, pre[i] + nums[i] + suf[i + 1]);
            }
        }
        return ans == Integer.MAX_VALUE ? -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
class Solution {
    public int minGroupsForValidAssignment(int[] nums) {
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int x : nums) {
            cnt.merge(x, 1, Integer::sum);
        }
        int k = nums.length;
        for (int x : cnt.values()) {
            k = Math.min(k, x);
        }
        
        for (; ; k--) {
            int ans = 0;
            for (int x : cnt.values()) {
                if (x / k < x % k) {
                    ans = 0;
                    break;
                }
                ans += (x + k) / (k + 1);
            }
            if (ans > 0) {
                return ans;
            }
        }
    }
}

得到 K 个半回文串的最少修改次数

直接记忆化搜索就能搞定，特别注意子字符串的长度要求至少为 \(2\)。当然还可以预处理出所有因子，也可以将记忆化搜索转化为自底向上的动态规划。

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
class Solution {
    public int minimumChanges(String s, int k) {
        int n = s.length();

        int[][] change = new int[n][n];
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                change[i][j] = calc(s.substring(i, j + 1));
            }
        }

        int[][] dp = new int[n][k];
        for (int i = 0; i < n; i++) {
            Arrays.fill(dp[i], -1);
        }
        return dfs(0, s, n, k - 1, change, dp);
    }

    private int calc(String s) {
        int n = s.length(), res = n;
        for (int d = 1; d < n; d++) {
            if (n % d == 0) {
                int cnt = 0;
                for (int k = 0; k < d; k++) {
                    for (int i = k, j = n - d + k; i < j; i += d, j -= d) {
                        if (s.charAt(i) != s.charAt(j)) {
                            cnt++;
                        }
                    }
                }
                res = Math.min(res, cnt);
            }
        }
        return res;
    }

    private int dfs(int i, String s, int n, int k, int[][] change, int[][] dp) {
        if (k == 0) {
            return change[i][n - 1];
        }

        if (dp[i][k] != -1) {
            return dp[i][k];
        }

        int res = n;
        for (int j = i + 1; j < n - 2 * k; j++) {
            res = Math.min(res, dfs(j + 1, s, n, k - 1, change, dp) + change[i][j]);
        }
        return dp[i][k] = res;
    }
}
发表更新算法 / AtCoder3 分钟读完 (大约379个字)

AtCoder Beginner Contest 325

Takahashi san

1
2
3
4
5
public static void solve() {
    String s = io.next();
    io.next();
    io.println(s + " san");
}

World Meeting

比赛时用滑窗没有做出来，原来要滑两倍的数组长度啊。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static void solve() {
    int n = io.nextInt();
    int[] cnt = new int[24];
    for (int i = 0; i < n; i++) {
        int w = io.nextInt(), x = io.nextInt();
        cnt[x] += w;
    }

    int ans = 0;
    for (int i = 0; i < 24; i++) {
        int sum = 0;
        for (int j = 0; j < 9; j++) {
            sum += cnt[(i + j) % 24];
        }
        ans = Math.max(ans, sum);
    }
    io.println(ans);
}

Sensors

直接 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
32
public static void solve() {
    int h = io.nextInt(), w = io.nextInt();
    boolean[][] g = new boolean[h][w];
    for (int i = 0; i < h; i++) {
        String s = io.next();
        for (int j = 0; j < w; j++) {
            if (s.charAt(j) == '#') {
                g[i][j] = true;
            }
        }
    }
    int ans = 0;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (g[i][j]) {
                ans++;
                dfs(i, j, g);
            }
        }
    }
    io.println(ans);
}

private static void dfs(int x, int y, boolean[][] g) {
    if (x < 0 || x >= g.length || y < 0 || y >= g[0].length || !g[x][y]) return;
    g[x][y] = false;
    for (int i = -1; i <= 1; i++) {
        for (int j = -1; j <= 1; j++) {
            dfs(x + i, y + j, g);
        }
    }
}

Printing Machine

贪心，对于每个时刻，我们选择已经进入传送带的，右端点最小的产品。

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
public static void solve() {
    int n = io.nextInt();
    long[][] aux = new long[n][];
    for (int i = 0; i < n; i++) {
        long t = io.nextLong(), d = io.nextLong();
        aux[i] = new long[]{t, t + d};
    }
    Arrays.sort(aux, (a, b) -> Long.compare(a[0], b[0]));

    int i = 0, ans = 0;
    Queue<Long> q = new PriorityQueue<>();
    for (long t = 0; ; t++) {
        if (q.isEmpty()) {
            if (i == n) break;
            t = aux[i][0];
        }
        while (i < n && aux[i][0] == t) {
            q.offer(aux[i++][1]);
        }
        while (!q.isEmpty() && q.peek() < t) {
            q.poll();
        }
        if (!q.isEmpty()) {
            ans++;
            q.poll();
        }
    }
    io.println(ans);
}
关注我

链接

分类

最新文章

归档

标签

Debugging2
Draft1
Hexo1

链接

×