发表更新算法 / 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);
}
发表更新算法 / AtCoder4 分钟读完 (大约652个字)

AtCoder Beginner Contest 324

Same

1
2
3
4
5
6
7
8
public static void solve() {
    int n = io.nextInt();
    Set<Integer> set = new HashSet<>();
    for (int i = 0; i < n; i++) {
        set.add(io.nextInt());
    }
    io.println(set.size() == 1 ? "Yes" : "No");
}

3-smooth Numbers

1
2
3
4
5
6
public static void solve() {
    long n = io.nextLong();
    while (n % 2 == 0) n /= 2;
    while (n % 3 == 0) n /= 3;
    io.println(n == 1 ? "Yes" : "No");
}

Error Correction

额，很简单的题，赛时花费很长时间，代码写得很乱。

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();
    String t = io.next();
    List<Integer> ans = new ArrayList<>();
    for (int k = 0; k < n; k++) {
        String s = io.next();

        int i = 0;
        for (; i < s.length() && i < t.length(); i++) {
            if (s.charAt(i) != t.charAt(i)) {
                break;
            }
        }

        int j = 0;
        for (; j < s.length() && j < t.length(); j++) {
            if (s.charAt(s.length() - 1 - j) != t.charAt(t.length() - 1 - j)) {
                break;
            }
        }

        boolean ok = s.length() == t.length() && i + j >= t.length() - 1;
        ok |= s.length() == t.length() + 1 && i + j >= t.length();
        ok |= s.length() == t.length() - 1 && i + j >= t.length() - 1;
        if (ok) {
            ans.add(k + 1);
        }
    }

    io.println(ans.size());
    ans.forEach(i -> io.print(i + " "));
    io.println();
}

Square Permutation

还是直接使用字符串更简单，要不然还要拆位。

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();
    char[] s = io.next().toCharArray();
    Arrays.sort(s);
    long max = (long) Math.pow(10, n);

    int ans = 0;
    for (long i = 0; i * i < max; i++) {
        StringBuilder sb = new StringBuilder(String.valueOf(i * i));
        while (sb.length() < n) {
            sb.append("0");
        }
        char[] t = sb.toString().toCharArray();
        Arrays.sort(t);
        if (Arrays.equals(s, t)) {
            ans++;
        }
    }
    io.println(ans);
}

Joint Two Strings

记录每个字符串的子序列匹配目标字符串的最大前后缀的长度，因为答案和下标无关，所以使用排序 + 二分计算答案。

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();
    String t = io.next();

    int[] prefix = new int[n];
    int[] suffix = new int[n];
    for (int k = 0; k < n; k++) {
        String s = io.next();

        for (int i = 0; i < s.length() && prefix[k] < t.length(); i++) {
            if (s.charAt(i) == t.charAt(prefix[k])) {
                prefix[k]++;
            }
        }

        for (int i = 0; i < s.length() && suffix[k] < t.length(); i++) {
            if (s.charAt(s.length() - 1 - i) == t.charAt(t.length() - 1 - suffix[k])) {
                suffix[k]++;
            }
        }
    }

    Arrays.sort(suffix);

    long ans = 0L;
    for (int i = 0; i < n; i++) {
        int lo = 0, hi = n - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (prefix[i] + suffix[mid] >= t.length()) hi = mid - 1;
            else lo = mid + 1;
        }
        ans += n - lo;
    }
    io.println(ans);
}

Beautiful Path

二分答案，将除法转化为乘法，因为顶点的边限制 \(u<v\)，所以从 \(1\) 到 \(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
public static void solve() {
    int n = io.nextInt(), m = io.nextInt();

    int[] in = new int[n];
    List<int[]>[] g = new List[n];
    Arrays.setAll(g, k -> new ArrayList<>());
    for (int i = 0; i < m; i++) {
        int u = io.nextInt() - 1, v = io.nextInt() - 1, b = io.nextInt(), c = io.nextInt();
        g[u].add(new int[]{v, b, c});
        in[v]++;
    }

    double lo = 0, hi = 1e4;
    while (hi - lo >= 1e-10) {
        double mid = lo + (hi - lo) / 2;
        if (check(g, in.clone(), mid)) lo = mid;
        else hi = mid;
    }
    io.println(lo);
}

private static boolean check(List<int[]>[] g, int[] in, double x) {
    int n = g.length;
    double[] dist = new double[n];
    Arrays.fill(dist, Long.MIN_VALUE);

    dist[0] = 0;
    for (int u = 0; u < n; u++) {
        for (int[] t : g[u]) {
            int v = t[0], b = t[1], c = t[2];
            if (dist[v] < dist[u] + b - c * x) {
                dist[v] = dist[u] + b - c * x;
            }
        }
    }

    return dist[n - 1] >= 0;
}
关注我

链接

分类

最新文章

归档

标签

Debugging2
Draft1
Hexo1

链接

×