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

第 367 场力扣周赛

找出满足差值条件的下标 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
class Solution {
    public String shortestBeautifulSubstring(String s, int k) {
        int n = s.length();

        int lo = s.indexOf('1');
        if (lo < 0) {
            return "";
        }

        String ans = "";
        int hi = lo, cnt = 0;
        while (hi < n) {
            cnt += s.charAt(hi++) - '0';
            while (cnt > k || s.charAt(lo) == '0') {
                cnt -= s.charAt(lo++) - '0';
            }
            if (cnt == k) {
                String t = s.substring(lo, hi);
                if (ans.isEmpty() || t.length() < ans.length() || t.length() == ans.length() && t.compareTo(ans) < 0) {
                    ans = t;
                }
            }
        }
        return ans;
    }
}

找出满足差值条件的下标 II

维护最大值和最小值就行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int[] findIndices(int[] nums, int indexDifference, int valueDifference) {
        int n = nums.length;
        int minIndex = 0, maxIndex = 0;
        for (int j = indexDifference; j < n; j++) {
            int i = j - indexDifference;
            
            if (nums[i] > nums[maxIndex]) {
                maxIndex = i;
            } else if (nums[i] < nums[minIndex]) {
                minIndex = i;
            }

            if (nums[maxIndex] - nums[j] >= valueDifference) {
                return new int[]{maxIndex, j};
            }
            if (nums[j] - nums[minIndex] >= valueDifference) {
                return new int[]{minIndex, j};
            }
        }
        return new int[]{-1, -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
class Solution {
    private static final int MOD = 12345;

    public int[][] constructProductMatrix(int[][] grid) {
        int n = grid.length, m = grid[0].length;
        int[][] p = new int[n][m];

        long suf = 1;
        for (int i = n - 1; i >= 0; i--) {
            for (int j = m - 1; j >= 0; j--) {
                p[i][j] = (int) suf;
                suf = suf * grid[i][j] % MOD;
            }
        }

        long pre = 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                p[i][j] = (int) (p[i][j] * pre % MOD);
                pre = pre * grid[i][j] % MOD;
            }
        }

        return p;
    }
}
关注我

链接

分类

最新文章

归档

标签

Debugging2
Draft1
Hexo1

链接

×